- 使用 Spring Initializr 创建 Spring Boot 应用程序
- 在Spring Boot中配置Cassandra
- 在 Spring Boot 上配置 Tomcat 连接池
- 将Camel消息路由到嵌入WildFly的Artemis上
namespace bucket_hash
{
template<class K, class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K, V>& kv)
:_kv(kv)
, _next(nullptr)
{}
};
size_t GetNextPrime(size_t prime)
{
const int PRIMECOUNT = 28;
static const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i];
}
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
// 拷贝 和 赋值 需要自己实现桶的拷贝
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
_n = 0;
}
bool Erase(const K& key)
{
if (_tables.size() == 0)
{
return false;
}
Hash hf;
// 素数
size_t index = hf(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[index];
while (cur)
{
if (cur->_kv.first == key)
{
// 1、cur是头结点
// 2、非头节点
if (prev == nullptr)
{
_tables[index] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
Node* Find(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}
Hash hf;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;
}
bool Insert(const pair<K, V>& kv)
{
Hash hf;
//当负载因子到1时,进行扩容
if (_n == _tables.size())
{
//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
size_t newSize = GetNextPrime(_tables.size());
//HashTable<K, V> newHT;
vector<Node*> newtables;
newtables.resize(newSize, nullptr);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf(cur->_kv.first) % newSize;
cur->_next = newtables[index];
newtables[index] = cur;
cur = next;
}
_tables[i] = nullptr;
}
newtables.swap(_tables);
}
size_t index = hf(kv.first) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (cur->_kv.first == kv.first)
{
return false;
}
else
{
cur = cur->_next;
}
}
Node* newnode = new Node(kv);
newnode->_next = _tables[index];
_tables[index] = newnode;
++_n;
return true;
}
private:
vector<Node*> _tables;
size_t _n = 0; // 存储多少有效数据
};
}
我们以KV模型的哈希表进行改造实现unordered_set和unordered_map:
template<class K, class T, class KeyOfT, class Hash = HashFunc<T> >
class HashBucket;
K:关键码类型
T: 不同容器T的类型不同,如果是unordered_map,T代表一个键值对,如果是unordered_set,T为 K
KeyOfT: 在哈希表中需要取到value,因为T的类型不同,通过value取key的方式就不同,详细见unordered_map/set的实现
Hash: 哈希函数仿函数对象类型,哈希函数使用除留余数法,如果是Key为string类型,需要将Key转换为整形数字才能取模
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
如果是unordered_map,T代表一个键值对,如果是unordered_set,T为 K
哈希表的迭代器我们应该怎么实现呢?
哈希表的迭代器也是对节点指针进行了封装,我们想一想++操作怎么实现呢?一个桶遍历完了如何跳转到下一个桶?为了实现桶的跳转,我们在迭代器中还需要一个哈希表的指针
当下一个节点不为空时,后的节点就在当前桶,返回即可,当下一个节点为空时,我们需要找下一个桶,首先通过当前节点计算找到当前节点所在桶的位置index,计算出后,index即找到了下一个桶,当下一个桶存在时,如果下一个桶里面有数据(即不为空),则将第一个数据给当前节点,就实现了,否则继续找下一个桶,当循环出来时,有可能是找到后的节点了,也有可能说明走完了后面没有桶了,所以循环出来需要判断是不是没有桶了,没有桶则返回nullptr
Self operator++()
{
if (_node->_next) // 在当前桶迭代
{
_node = _node->_next;
}
else // 找下一个桶
{
KeyOfT kot;
const K& key = kot(_node->_data);
Hash hf;
size_t index = hf(key) % _ht->_tables.size();
++index;
_node = nullptr;
while (index < _ht->_tables.size())
{
if (_ht->_tables[index])
{
_node = _ht->_tables[index];
break;
}
else
{
++index;
}
}
// 后面没有桶了
if (index == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
返回节点的数据的引用即可
T& operator*()
{
return _node->_data;
}
返回节点数据的地址即可
T* operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
// 前置声明
template<class K, class T, class KeyOfT,class Hash>
class HashTable;
template<class K, class T, class Hash, class KeyOfT>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef HTIterator<K, T, Hash, KeyOfT> Self;
Node* _node;
HT* _ht;
HTIterator(Node* node, HT* ht)
:_node(node)
, _ht(ht)
{}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self operator++()
{
if (_node->_next) // 在当前桶迭代
{
_node = _node->_next;
}
else // 找下一个桶
{
KeyOfT kot;
const K& key = kot(_node->_data);
Hash hf;
size_t index = hf(key) % _ht->_tables.size();
++index;
_node = nullptr;
while (index < _ht->_tables.size())
{
if (_ht->_tables[index])
{
_node = _ht->_tables[index];
break;
}
else
{
++index;
}
}
// 后面没有桶了
if (index == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
};
然后在哈希表中实现迭代器的相关函数:
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
friend struct HTIterator<K, T, Hash, KeyOfT>;//将迭代器设置成友元,让迭代器访问哈希表的私有
public:
typedef HTIterator<K, T, Hash, KeyOfT> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return end();//没有数据
}
iterator end()
{
return iterator(nullptr, this);
}
private:
vector<Node*> _table;
size_t _n = 0;
};
namespace bucket_hash
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
size_t GetNextPrime(size_t prime)
{
const int PRIMECOUNT = 28;
static const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i];
}
// 前置声明
template<class K, class T, class Hash, class KeyOfT>
class HashTable;
template<class K, class T, class Hash, class KeyOfT>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, Hash, KeyOfT> HT;
typedef HTIterator<K, T, Hash, KeyOfT> Self;
Node* _node;
HT* _ht;
HTIterator(Node* node, HT* ht)
:_node(node)
, _ht(ht)
{}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self operator++()
{
if (_node->_next) // 在当前桶迭代
{
_node = _node->_next;
}
else // 找下一个桶
{
KeyOfT kot;
const K& key = kot(_node->_data);
Hash hf;
size_t index = hf(key) % _ht->_tables.size();
++index;
_node = nullptr;
while (index < _ht->_tables.size())
{
if (_ht->_tables[index])
{
_node = _ht->_tables[index];
break;
}
else
{
++index;
}
}
// 后面没有桶了
if (index == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
};
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
//template<class K, class T, class Hash, class KeyOfT>
friend struct HTIterator<K, T, Hash, KeyOfT>;
public:
typedef HTIterator<K, T, Hash, KeyOfT> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
// 拷贝 和 赋值 需要自己实现桶的拷贝
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
_n;
}
bool Erase(const K& key)
{
if (_tables.size() == 0)
{
return false;
}
Hash hf;
KeyOfT kot;
// 素数
size_t index = hf(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[index];
while (cur)
{
if (kot(cur->_data) == key)
{
// 1、cur是头结点
// 2、非头节点
if (prev == nullptr)
{
_tables[index] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
Node* Find(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}
Hash hf;
KeyOfT kot;
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (kot(cur->_data) == key)
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;
}
bool Insert(const T& data)
{
Hash hf;
KeyOfT kot;
//当负载因子到1时,进行扩容
if (_n == _tables.size())
{
//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
size_t newSize = GetNextPrime(_tables.size());
//HashTable<K, V> newHT;
vector<Node*> newtables;
newtables.resize(newSize, nullptr);
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
const K& key = kot(cur->_data);
size_t index = hf(key) % newSize;
cur->_next = newtables[index];
newtables[index] = cur;
cur = next;
}
_tables[i] = nullptr;
}
newtables.swap(_tables);
}
const K& key = kot(data);
size_t index = hf(key) % _tables.size();
Node* cur = _tables[index];
while (cur)
{
if (kot(cur->_data) == kot(data))
{
return false;
}
else
{
cur = cur->_next;
}
}
Node* newnode = new Node(data);
newnode->_next = _tables[index];
_tables[index] = newnode;
++_n;
return true;
}
private:
vector<Node*> _tables;
size_t _n = 0; // 存储多少有效数据
};
}
实现unordered_set只需要调用底层哈希表对应的接口即可:
#pragma once
#include "HashTable.h"
namespace Z
{
template<class K>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key) const
{
return key;
}
};
public:
typedef typename bucket_hash::HashTable<K, K,SetKeyOfT>::iterator iterator;
//没有实例化,没办法去哈希表中去找iterator,typename这就是告诉编译器这就是个类型,等实例化后再去找
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
//插入
pair<iterator,bool> insert(const pair<const K, V>& kv)
{
return _ht.Insert(kv);
}
//删除
bool erase(const K& key)
{
return _ht.Erase(key);
}
//查找
iterator find(const K& key)
{
return _ht.Find(key);
}
private:
bucket_hash::HashTable<K, K, SetKeyOfT> _ht;
};
实现unordered_map只需要调用底层哈希表对应的接口即可,和unordered_set不一样的是它需要实现[]运算符重载:
#pragma once
#include "HashTable.h"
namespace bit
{
template<class K, class V>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv) const
{
return kv.first;
}
};
public:
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
//插入
pair<iterator,bool> insert(const pair<const K, V>& kv)
{
return _ht.Insert(kv);
}
//[]运算符重载
V& operator[](const K& key)
{
pair<iterator,bool> ret = insert(make_pair(key,V()));
iterator it = ret.first;
return it->second;
}
//删除
bool erase(const K& key)
{
return _ht.Erase(key);
}
//查找
iterator find(const K& key)
{
return _ht.Find(key);
}
private:
bucket_hash::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}
我想创建一个容器来存储唯一的整数集。 我想创建类似的东西 std::unordered_set> 但是 g++ 不允许我这样做并说: invalid use of incomplete type 's
我是 C++ 的新手,被要求将 Java 程序转换为 C++。我正在尝试编写一种方法来检查一个 unordered_set 中的所有元素是否存在于另一个 unordered_set 中。我发现下面的示
我想为我正在编写的类创建一个散列函数,我想让散列函数成为类的 friend ,这样我就不必编写不必要的 getter 方法。为此,我遵循了 this SO post 中接受的答案.但我希望能够将对象插
我想使用 std::pmr::unordered_map与 std::pmr::monotonic_buffer_resource .两者配合得很好,因为集合的节点是稳定的,所以我不会通过重新分配在缓
我有一个每帧创建的项目列表,需要对其进行排序。每个 Item 的第一个排序依据的成员变量是 unordered_set。 我已将其移动到系统中各处的有序集合中,以便我可以在项目列表中对其进行排序。但是
是否有将 std::unordered_set 与实现 operator== 和 hash 的类一起使用的捷径?具体来说,有没有一种方法可以 (1) 避免创建独立的 operator==(const
我正在将 C 文件转换为 C++。由于这些函数仍会从 C 代码中调用,因此我会将整个文件放在 extern "C" block 中。该文件包含以下代码- struct node{ char*
我有一个关于在 unordered_set 中插入的问题。我想建立一个最坏情况插入的例子。我有 30000 个字符串(len string my_set; 关于c++ - Unordered_set
我已经从 C 转向 C++,并且最近学习了 STL。 最后一行在 STL 样式中给出了很长的错误(无助)或者也许我是模板的新手,这就是为什么我觉得它无能为力。 int insert(Forest *f
我正在使用 unordered_set 来实现哈希表。我不知道如何使用查找功能。运行此代码时,我不断遇到段错误。我知道这是因为 find() 没有找到元素,但它应该找到。我的问题是如何通过我提供的自定
这个问题在这里已经有了答案: C++11 initializer list fails - but only on lists of length 2 (2 个答案) 关闭 8 年前。 当我使用包含
这个问题在这里已经有了答案: Subtracting map iterators (2 个答案) 关闭 5 年前。 尝试在无序集中查找元素的索引。发现迭代器的减法(运算符“-”)是一种方法。 vec
我注意到当我使用无序集时 unordered_set theSet;为了保存大量整数,即使调用 clear() 或 rehash(0),它也不会释放内存。即使我在函数中本地定义了集合,并且函数完成执行
谁能解释一下无序集是如何工作的?我也不确定一套是如何工作的。我的主要问题是它的查找功能的效率如何。 例如,这个大 O 的总运行时间是多少? vector theFirst; vecto
我一直在阅读 cplusplus.com 网站并尝试确保我的 unordered_set 号码不会以任何方式被修改。该站点表示容器的元素未排序,普通 set 就是这种情况。 该网站还说: Intern
我有: std::unordered_set _buttons; std::unordered_set _sprites; std::unordered_set _someOtherSprites;
缩小范围:我目前正在使用 Boost.Unordered .我看到两种可能的解决方案: 定义我自己的Equality Predicates and Hash Functions并利用模板(可能是 is
我有一个类需要一个 std::unordered_set它持有不可复制、不可移动的实体对象,并且其哈希函数对实例的地址进行哈希处理。类似于以下内容: class A { public: A()
我正在尝试散列一个 Edge 结构,以便我可以拥有一个具有唯一边的 unordered_set。在我的例子中,如果一条边的两个端点的组合在之前的集合中没有遇到,则该边被认为是唯一的。 虽然我的代码适用
我已经成功地为自定义类创建了一个散列函数(和 == 覆盖),因此我可以在 unordered_set 中使用它。但是,理想情况下,我想在要使用的类附近为我的类定义模板特化。这可以通过以下方式完成,效果
我是一名优秀的程序员,十分优秀!