【C++进阶篇】哈希表的模拟实现（赋源码）
【C++进阶篇】哈希表的模拟实现（赋源码）
前言
哈希表的核心思想就是映射，通过将key值以某种算法映射成不大于哈希表长度的哈希值，从而实现存储数据。上篇提到解决哈希冲突有 闭散列 和 开散列，本文将用这两种理论思想实现哈希表。 代码位置：哈希模拟的实现源码
一. 开放地址法实现哈希表
1.1 闭散列结构定义
该闭散列哈希表使用vector数组，其中数组里面包含一个结构体，该结构存储pair类型数据及当前位置的状态，是否为空，不为空，或者有数据然后被删除了的三个状态，伪代码如下：
//节点可能的三种状态
enum State
{
EXIST,
EMPTY,
DELETE
};
//哈希表中存储的数据
template<class K, class V>
struct HashData
{
pair<K, V> _kv;//存放数据类型
State _state = EMPTY;//当前位置的状态，默认为空，即表示此位置没有数据
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;//表中实际存储的数据个数
};- 仿函数作用：
因为里面是数组，通过key值映射成哈希值后，哈希值不能超过哈希表的长度，需要取模，所以同时也要传入仿函数，将任意类型数据不能取模转换成整数，本来就可以进行取模运算的，就无需借助额外的仿函数，所以就可以给一个默认的仿函数，该仿函数给本来是整数去使用的。
//默认的仿函数
template<class K>
class HashFunc
{
public:
size_t operator()(const K& key)
{
return (size_t)key;
}
};1.2 构造函数
给vector数组开一定的空间，为了防止2的幂次方的数，底层给了一定合理的素数，下面给代码即可。
inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
HashTable()
{
_tables.resize(__stl_next_prime(1));
}1.3 插入（线性探测）
插入之前判断该key值是否在存在，存在直接返回即可。对插入的key值映射成哈希值，然后进行探测，探测规则：当前位置为空，继续向后探测，跳出循环后，将该位置插入数据并将该位置的状态设置为存在，_n++(表示存储的数据个数+1)，这里有一个问题：扩容？？？
- 问题：如何扩容
1.3.1 传统写法
创建一个数组（数组已经扩容后），将旧表中的vector数组中的数据重新进行映射成新开的数组（这里的一个优势在于：原来在旧表中冲突的数据可能在新表中就不冲突了），也需进行探测，过程基本与插入过程一致，将旧数据完成探测之后，在新表与旧表进行交换。伪代码如下：
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
//扩容
if ((double)_n / (double)_tables.size() >= 0.7)
{
// 获取素数表里面比当前表大的下一个素数
size_t newSize = __stl_next_prime(_tables.size() + 1);
vector<HashData<K, V>> newTables(newSize);
//遍历旧表，将数据都映射到新表
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
size_t hash0 = _tables[i].kv.first % newSize;
size_t i = 1;
size_t hashi = hash0;
while (newTables[hashi]._state == EXIST)
{
//冲突探测
hashi = (hash0 + i) % newSize;
i++;
}
newTables[hashi]._kv = kv;
newTables[hashi]._state = EXIST;
//_n++;需不需要写？？？思考一下
}
}
_tables.swap(newTables);
}
Hash hs;
size_t hash0 = hs(kv.first) % _tables.size();
size_t i = 1;
size_t hashi = hash0;
while (_tables[hashi]._state == EXIST)
{
//冲突探测
hashi = (hash0 + i) % _tables.size();
i++;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
_n++;
return true;
}- 细节1：
重新寻找哈希值，需要对新的哈希表的长度进行取余，不要依然对旧表中的哈希表长度进行取余，否则会导致新表中新增加的长度没有被使用，冲突概率未减少。
- 细节2：
_n++需不需要写？？？不需要，因为是将旧表中的数据重新映射至新表，数据并没有增加。
注意：可以看出上述代码有点冗余，特别是插入过程与重新建立映射关系的代码很相似。 下面这种写法很巧妙，且代码量少。
1.3.2 现代写法
思想：建立一个新表，然后给新表中的哈希表开一定足够的空间，然后将旧表中的数据直接插入新表中即可，插入的过程同时也完成探测过程。很优雅的写法，建议采用它。
- 伪代码：
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
//扩容
if ((double)_n / (double)_tables.size() >= 0.7)
{
size_t newSize = __stl_next_prime(_tables.size() + 1);
HashTable<K, V, Hash> newHT;
newHT._tables.resize(newSize);
//遍历旧表，将数据都映射到新表
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newHT.Insert(_tables[i]._kv);//此行为已经将旧数据映射到了新表中，同时进行线性探测和冲突探测，可能原来在旧表中的数据冲突，在新表中它就不冲突了
}
}
_tables.swap(newHT._tables);//将新表与旧表进行交换
}
Hash hs;
size_t hash0 = hs(kv.first) % _tables.size();
size_t i = 1;
size_t hashi = hash0;
while (_tables[hashi]._state == EXIST)
{
//冲突探测
hashi = (hash0 + i) % _tables.size();
i++;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
_n++;
return true;
}该实现是一个功能完整的线性探测哈希表，适合学习用途。
1.4 查找
查找过程很简单，首先对要查找的key值转化成映射后的哈希值，对应位置状态为！EXIST，进行查询当前位置状态不为空，且不为删除直接返回该指针即可，否则继续往后探测，当探测为空，说明不存在，直接返回nullptr即可。
- 伪代码：
HashData<K, V>* Find(const K& key)
{
Hash hs;
size_t hash0 = hs(key) % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi]._state != EMPTY)
{
if (_tables[hashi]._state == EXIST
&& _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
hashi = (hash0 + i) % _tables.size();
++i;
}
return nullptr;
}1.5 删除
直接调用接口Find即可，接收返回值，判断返回值是否为空，为空直接返回false；不为空将该位置的状态设置为删除即可，然后返回true即可。
- 伪代码：
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
--_n;
ret->_state = DELETE;
return true;
}
}标记删除操作时间复杂度为 O(1)，无数据迁移开销。 声明：上述做法了解一下即可，下面这个才是王炸，需重点关注及掌握。
二. 链地址法实现哈希表（哈希桶）
2.1 开散列结构定义
该开散列哈希表使用vector数组，其中数组里面包含一个哈希表节点，该节点存储pair类型数据及下一个哈希表数据的指针。伪代码如下：
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) {} // 构造函数
};
template<class K, class V>
class HashTable {
typedef HashNode<K, V> Node;
vector<Node*> _tables; // 哈希槽数组（存储链表头指针）
size_t _n = 0; // 当前元素总数
};该代码提供了链地址法哈希表的核心骨架。
2.2 构造函数
构造函数与上述闭散列一致。
inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
HashTable()
{
_tables.resize(__stl_next_prime(1), nullptr);
}2.3 插入
创建一个数组，扩容时，将旧表中的节点挪动至新表中，需重新建立映射关系，也需要进行探测，过程与插入过程一致，将旧数据完成探测之后，在新表与旧表进行交换。伪代码如下： **插入数据时有个问题，**进行尾插还是头插，两者都可以，但头插很简单，尾插相对较复杂，需要找尾，当前桶挪动完毕，需要将当前桶只为nullptr，本文以头插为示例。
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
if (_n == _tables.size())
{
size_t newSize = __stl_next_prime(_tables.size() + 1);
vector<Node*> newtables(newSize, nullptr);
//遍历旧表，将旧表的节点挪动到新表
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = cur->_kv.first % newSize;
cur->_next = newtables[hashi];
newtables[hashi] = cur;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = kv.first % _tables.size();
Node* newnode = new Node(kv);
//头插，尾插也行，找尾麻烦,需要找尾
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}2.4 查找
查找过程很简单，将要查找的key值转换成哈希值，然后对该桶进行遍历，判断桶中的数据key值是否与要查找的key值是否相等，相等返回该节点指针即可，找到空还未找到，返回nullptr即可。
- 伪代码如下：
Node* Find(const K& key)
{
size_t hashi = key % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}2.5 删除
删除需要前驱指针（默认为空）将删除后的节点连接起来，删除过程相对来说较复杂，也需要要删除的key值转换成哈希值，然后遍历该桶，判断桶中节点的数据key值与要查找的key值是否相等，相等进行删除，返回true即可，里面有细节 -> :
- 细节一：
当删除头结点时，头结点没有前驱指针，会对空指针进1行解引用，所以需要分情况讨论。
- 前驱指针不为空，和为空两种状态。
- 不相等继续往后找，当前桶找完还未找到，返回false即可。
- 伪代码：
bool Erase(const K& key)
{
size_t hashi = key % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
//删除
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
_n--;
return true;
}
//不相等继续往后找
prev = cur;
cur = cur->_next;
}
return false;
}代码正确处理了链表节点的删除，维护了计数器_n，但未处理重复键（若允许存在）。
三. 最后
本文详述了哈希表的两种实现方式：开放地址法（闭散列）与链地址法（开散列）。开放地址法通过线性探测解决冲突，采用标记删除优化性能，扩容时重建哈希表；链地址法以链表处理冲突，头插法简化操作，扩容时重新映射所有节点。两者均使用素数表优化哈希分布，核心操作包括插入、查找、删除，适用于不同场景，是高效键值存储的关键技术。
腾讯云开发者
