C++：探索哈希表秘密之哈希桶实现哈希
文章目录
前言
前面我们用开放定址法代码实现了哈希表：
C++：揭秘哈希：提升查找效率的终极技巧_1
对于开放定址法来说，包含以下两种探测插入节点位置方法：
- 线性探测
- 二次探测
但是开放定址法的缺点也很明显，开放定址法容易很多数据堆积在一起，大大减少了效率。
为了解决上述问题，引入了第二种方法实现哈希表
——链地址法（哈希桶法）
一、链地址法概念
开放定址法中，所有的元素都放到哈希表里。
链地址法中，所有的数据不再直接存储在哈希表中。哈希表中存储一个指针，没有数据映射到这个位置时，这个指针为空；有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面。链地址法也叫做拉链法或者哈希桶。
下⾯演⽰ {19,30,5,36,13,20,21,12,24,96} 等这⼀组值映射到M=11的表中。
二、哈希表扩容
开放定址法的负载因子必须小于 1，而链地址法的负载因子则没有限制，可以大于 1。
负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低。
STL 中 unordered_xxx 的最大负载因子基本控制在 1，当负载因子大于 1 时会扩容。我们下面的实现也使用这种方式。
也就是说，我们期望基本每个节点下面都挂一个桶，有那么一两个数据，如下图：
三、哈希桶插入逻辑
首先，如果不需要扩容，我们需要将一个节点挂上去，因为每一个哈希桶类似于链表，而链表的头插效率是十分高的，因此我们采用头插。
// 如果不需要扩容 size_t hashi =hf(kv.first)% _table.size();// 头插 Node* newnode =newNode(kv); newnode->_next = _table[hashi]; _table[hashi]= newnode;++_n;returntrue;其次，如果需要扩容的话，需要遍历_table取每一个哈希桶的每一个结点重新插入到新表，但是这样的话还牵扯到了旧表资源的释放。因此我们使用顺手牵羊，直接将旧表的节点迁过来头插，解决资源释放的问题。
// 遍历旧表，顺手牵羊，把节点牵下来挂到新表for(size_t i =0; i < _table.size(); i++){ Node* cur = _table[i];while(cur){ Node* next = cur->_next;// 头插到新表 size_t newhashi =hf(cur->_kv.first)% newSize; cur->_next = newTable[newhashi]; newTable[newhashi]= cur; cur = next;} _table[i]=nullptr;} _table.swap(newTable);}四、析构函数
因为我们vector中存储的是自定义类型，因此我们需要显示写析构函数。
遍历整个哈希表，删除每一个节点，最后将其置空。
~HashTable(){for(size_t i =0; i < _table.size(); i++){ Node* cur = _table[i];while(cur){ Node* next = cur->_next;delete cur; cur = next;} _table[i]=nullptr;}}五、删除逻辑
删除就比较简单了，它分两种情况：
删除的值prev为空——直接删除它，把_table[i] = cur
删除的值prev不为空——涉及到前后的链接
boolErase(const K& key){ HashFunc hf; size_t hashi =hf(key)% _table.size(); Node* cur = _table[hashi]; Node* prev =nullptr;while(cur){if(cur->_kv.first == key){if(prev ==nullptr){ _table[hashi]= cur->_next;}else{ prev->_next = cur->_next;}delete cur;returntrue;}else{ prev = cur; cur = cur->_next;}}returnfalse;}六、查找
这里的查找比较简单，遍历整个_table就可以啦~
七、链地址法代码实现总结
#pragmaonce#include<vector>namespace hash_bucket {template<classK>structDefaultHashFunc{ size_t operator()(const K& key){return(size_t)key;}};template<>structDefaultHashFunc<string>{ size_t operator()(const string& str){// BKDR size_t hash =0;for(auto ch : str){ hash *=131; hash += ch;}return hash;}};template<classK,classV>structHashData{ pair<K, V> _kv; HashData<K, V>* _next;HashData(const pair<K, V>& kv):_kv(kv),_next(nullptr){}};template<classK,classV,classHashFunc= DefaultHashFunc<K>>classHashTable{typedef HashData<K, V> Node;public:HashTable(){ _table.resize(10,nullptr);}~HashTable(){for(size_t i =0; i < _table.size(); i++){ Node* cur = _table[i];while(cur){ Node* next = cur->_next;delete cur; cur = next;} _table[i]=nullptr;}}boolInsert(const pair<K, V>& kv){if(Find(kv.first)){returnfalse;}// 仿函数控制 HashFunc hf;// 如果需要扩容if(_n == _table.size()){ size_t newSize = _table.size()*2; vector<Node*> newTable; newTable.resize(newSize,nullptr);// 遍历旧表，顺手牵羊，把节点牵下来挂到新表for(size_t i =0; i < _table.size(); i++){ Node* cur = _table[i];while(cur){ Node* next = cur->_next;// 头插到新表 size_t newhashi =hf(cur->_kv.first)% newSize; cur->_next = newTable[newhashi]; newTable[newhashi]= cur; cur = next;} _table[i]=nullptr;} _table.swap(newTable);}// 如果不需要扩容 size_t hashi =hf(kv.first)% _table.size();// 头插 Node* newnode =newNode(kv); newnode->_next = _table[hashi]; _table[hashi]= newnode;++_n;returntrue;} Node*Find(const K& key){ HashFunc hf; size_t hashi =hf(key)% _table.size(); Node* cur = _table[hashi];while(cur){if(cur->_kv.first == key){return cur;} cur = cur->_next;}returnnullptr;}boolErase(const K& key){ HashFunc hf; size_t hashi =hf(key)% _table.size(); Node* cur = _table[hashi]; Node* prev =nullptr;while(cur){if(cur->_kv.first == key){if(prev ==nullptr){ _table[hashi]= cur->_next;}else{ prev->_next = cur->_next;}delete cur;returntrue;}else{ prev = cur; cur = cur->_next;}}returnfalse;}voidPrint(){for(size_t i =0; i < _table.size(); i++){printf("[%d]->", i); Node* cur = _table[i];while(cur){ cout << cur->_kv.first <<":"<< cur->_kv.second <<"->"; cur = cur->_next;}printf("NULL\n");} cout << endl;}private: vector<Node*> _table;// 指针数组 size_t _n =0;// 存储了多少个有效数据};}到这里就结束啦，创作不易，如果对您有帮助的话，麻烦给一个一键三连，谢谢各位大佬~
