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)
{
// BKDR
size_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; // 存储了多少个有效数据
};
}
到这里就结束啦，创作不易，如果对您有帮助的话，麻烦给一个一键三连，谢谢各位大佬~
