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 = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return true;

其次，如果需要扩容的话，需要遍历_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不为空——涉及到前后的链接

在这里插入图片描述

bool Erase(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;return true;}else{prev = cur;cur = cur->_next;}}return false;}

六、查找

这里的查找比较简单，遍历整个_table就可以啦~
在这里插入图片描述

七、链地址法代码实现总结

#pragma once
#include<vector>namespace hash_bucket
{template<class K>struct DefaultHashFunc{size_t operator() (const K& key){return (size_t)key;}};template<>struct DefaultHashFunc<string>{size_t operator() (const string& str){// BKDRsize_t hash = 0;for (auto ch : str){hash *= 131;hash += ch;}return hash;}};template<class K, class V>struct HashData{pair<K, V> _kv;HashData<K, V>* _next;HashData(const pair<K, V>& kv): _kv(kv), _next(nullptr){}};template<class K, class V, class HashFunc = DefaultHashFunc<K>>class HashTable{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;}}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}// 仿函数控制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 = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return true;}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;}return nullptr;}bool Erase(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;return true;}else{prev = cur;cur = cur->_next;}}return false;}void Print(){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;            // 存储了多少个有效数据};
}