【C++篇】STL的关联容器：unordered_map和unordered_set（上篇）：哈希表的模拟实现

---

一、unordered系列关联式容器

unordered系列容器包括：

• unordered_map和unordered_mutimap
• unordered_set和unordered_mutiset

它们的使用方法（接口）与map和set是几乎相同的，我们平移过来使用即可。
详见：
【C++篇】STL的关联容器：map和set（上篇）—— map和set的介绍和使用

它们与map和set的区别在于：

• unordered系列遍历出来是无序的
• unordered系列没有反向迭代器，而map和set有
• 底层的数据结构不同：
  • map和set是红黑树
  • unordered系列是哈希表
• 一般情况下，哈希表的性能优于红黑树（差别不大）

---

二、哈希表

1. 哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O($logN$)，搜索的效率取决于搜索过程中元素的比较次数。

那能否不经过任何比较，一次直接从表中得到要搜索的元素呢$O(1)$？

构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

这种函数被称作：哈希（散列）函数（HashFunc）

再向该结构中：

• 插入元素
  根据待插入元素的关键码，用哈希函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素
  对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
• 删除元素
  根据所给的关键码，搜索该元素，再进行删除

如此，就构造出来了一个数据结构——哈希表(Hash Table)(或称散列表)。

2. 常用的哈希函数

2.1 直接定址法

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找范围集中且连续的情况

过去我们实现的计数排序，用的就是这个方法：【初探数据结构】归并排序与计数排序的序曲

2.2 除留取余法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m)，将关键码转换成哈希地址。
使用场景：值的分布范围分散

例如：数据集合{1，7，6，4，5，9}
我们将哈希函数设置为hash(key) = key % capacity
使用vector数组结构来构造，初始空间设为10

3. 哈希冲突

但如果有两个不同的数据经过哈希函数计算后的值是相同的，那该如何处理呢？

这种情况，就是哈希冲突。

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

哈希冲突解决方案：

3.1 闭散列——开放定址法

具体逻辑如下：
如果当前位置被占用了，按规则找下一个位置（占用别人的位置）
介绍两种常见的规则：

1. 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
   • 线性探测优点：实现非常简单（后文会模拟实现）
   • 线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”。不同的关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。 如何缓解呢？
2. 二次探测：
   找下一个空位置的方法为：$H_i$ = ($H_0$ + $i^2$ )% m, 或者：$H_i$ = ($H_0$ - $i^2$ )% m。其中：i = 1,2,3…， $H_0$是通过函数进行计算得到的位置，m是表的大小。

可以避免线性探测的缺陷：缓解数据堆积

3.2 开散列——哈希桶

开散列法又叫链地址法，首先对关键码集合用哈希函数计算对应地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

每个桶中放的都是发生哈希冲突的元素。

3.3 开散列与闭散列比较

用哈希桶处理哈希冲突，需要增设链接指针，看似增加了存储开销。事实上：
由于开放定址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子（存储数据量与总空间的比值）a <= 0.7，而表项所占空间又比指针大的多，所以使用哈希桶反而比开地址法节省了存储空间。

一般情况下，开散列优于闭散列。

---

三、模拟实现哈希表

本文将通过开散列与闭散列的方式分别实现哈希表。

1. 开放定址法（线性探测）

我们以线性探测为查找规则，因此我们以顺序表为基础容器进行改造。

1.1 哈希函数设计

显然，这里选择除留取余法更为妥当。
但是问题来了，如果数据类型为string类，%就会出错。

我们可以用仿函数数据类型都转化为size_t类型，一方面可以解决string，另一方面也可以解决出现负数的问题。

如果正常使用字符串各个字符ASCALL码值之和的话，当数据量较大时，会出现大量相同的值，哈希冲突加剧。
BKDR哈希算法：每加上一个字符ASCALL码值前，乘以131，可以大量减少重复。

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){size_t ret = 0;for (auto e : str){//BKDR哈希算法ret += e;ret *= 131;}return ret;}
};template<class K, class V, class Hashfunc = DefaultHashfunc<K>>
class HashTable
{typedef HashData<K, V> Data;//定义数据节点
public://…………
private:vector<Data> _table;size_t _n;//存储有效数据的数量
};

1.2 哈希表节点结构

除了存储的数据外，我们还需要什么？
有下列几个问题需要解决：

• 如何判断空节点？设为0吗？如果有取余为0的数呢？
• 我们在删除数据时，我们可以将该节点置空吗？置空岂不导致了后面的同类节点无法找到？

为此，我们不妨用状态标记（STATE枚举）：

enum STATE
{EXIST,//节点存有有效数据EMPTY,//空节点（从未使用）DELETE//已删除节点（惰性删除标记）
};template<class K, class V>
struct HashData
{STATE _state = EMPTY;pair<K, V> _kv;
};

1.3 插入 (insert)

插入操作可以分为3个步骤：

1. 存在检查：如果键已然存在，返回失败
2. 扩容机制
   • 当负载因子大于等于0.7时（_n/_size >= 0.7）,就扩容。
   • 创建应该双倍大小的新表
   • 遍历旧表将 EXIST 节点重新哈希插入新表
   • 通过 vector::swap 高效替换存储
3. 插入数据
   • 未发生哈希冲突：直接插入即可
   • 发生哈希冲突：线性探测解决冲突
     • 计算初始位节点：hash(key) % size
     • 向后线性探测：线性探测：遇到EXIST节点位时顺序后移（循环遍历）
     • 插入到第一个 EMPTY/DELETE 节点位并标记为 EXIST

bool insert(const pair<K, V>& kv)
{if (find(kv.first))return false;//负载因子控制在0.7以内if (_n * 10 / _table.size() == 7){//扩容size_t NewSize = _table.size() * 2;HashTable<K, V> NewTable;NewTable._table.resize(NewSize);//遍历旧表，插入到新表中for (int i = 0; i < _table.size(); ++i){if (_table[i]._state == EXIST){NewTable.insert(_table[i]._kv);}}_table.swap(NewTable._table);}//线性探测Hashfunc hf;size_t hashi = hf(kv.first) % _table.size();while (_table[hashi]._state == EXIST){hashi++;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._state = EXIST;++_n;return true;
}

1.4 查找 (find) 和 删除 (erase)

查找步骤：

1. 计算初始节点位
2. 顺序遍历直到遇到 EMPTY：
   • 跳过 DELETE 状态桶位
   • 检查 EXIST 桶位的键是否匹配
3. 循环处理：到达末尾时回到数组开头

Data* find(const K& key)
{Hashfunc hf;size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST&& _table[hashi]._kv.first == key)return (Data*)&_table[hashi];hashi++;hashi %= _table.size();}return nullptr;
}

删除步骤：
4. 查找目标节点：没找到就返回失败
5. 惰性删除：仅标记 DELETE 状态（不实际移除数据）
6. 更新有效数据计数 （--_n）

bool erase(const K& key)
{Data* dele = find(key);if (dele){dele->_state = DELETE;--_n;return true;}return false;
}

---

2. 链地址法（哈希桶）

我们知道，哈希桶的底层结构是一个指针数组，每个指针都指向一个单链表。
对于哈希函数选择，也是选择除留余数法。

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://…………
private:vector<Node*> _table;// 桶数组（存储链表头指针）size_t _n = 0; // 有效节点计数器
};

2.1 插入操作（insert）

依旧三部曲./

1. 检查键是否已存在（使用 find）
2. 当负载因子 ≥1 时扩容：
   • 创建双倍大小的新表
   • 节点转移而非新建：遍历旧表节点，重新计算哈希后插入新表
   • 使用头插法保持 O(1) 插入效率
3. 计算桶位置后头插新节点

bool insert(const pair<K, V>& kv)
{if (find(kv.first))return false;Hashfunc hf;//当负载因子对于1时，扩容if (_n / _table.size() == 1){size_t NewSize = _table.size() * 2;HashTable<K, V> NewTable;NewTable._table.resize(NewSize, nullptr);//遍历旧表，将旧表上的节点迁到新表上（避免节点创建释放操作）for (int i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;int hashi = hf(cur->_kv.first) % NewTable._table.size();cur->_next = NewTable._table[hashi];NewTable._table[hashi] = cur;cur = next;}}_table.swap(NewTable._table);}Node* NewData = new Node(kv);int hashi = hf(kv.first) % _table.size();NewData->_next = _table[hashi];_table[hashi] = NewData;++_n;return true;
}

2.2 查找操作 (find)

1. 计算键的哈希值确定桶位置

2. 遍历对应链表进行线性搜索

3. 找到匹配键时返回节点指针，否则返回 nullptr

Node* find(const K& key)
{Hashfunc hf;int hashi = hf(key) % _table.size();Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key)return cur;cur = cur->_next;}return nullptr;
}

2.3 删除操作 (erase)

1. 定位目标桶

2. 遍历链表处理两种情况：

   • 目标节点是头节点：更新桶指针

   • 目标节点在链表中间：更新前驱节点指针

3. 释放目标节点内存

bool erase(const K& key)
{Hashfunc hf;int hashi = hf(key) % _table.size();Node* dele = _table[hashi];Node* prev = nullptr;while (dele){if (dele->_kv.first == key){if (prev)prev->_next = dele->_next;else_table[hashi] = dele->_next;delete dele;return true;}prev = dele;dele = dele->_next;}return false;
}

---

四、模拟实现的哈希表源码

线性探测

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){size_t ret = 0;for (auto e : str){ret += e;ret *= 131;}return ret;}
};namespace open_address
{enum STATE{EXIST,EMPTY,DELETE};template<class K, class V>struct HashData{STATE _state = EMPTY;pair<K, V> _kv;};template<class K, class V, class Hashfunc = DefaultHashfunc<K>>class HashTable{typedef HashData<K, V> Data;public:HashTable():_n(0){_table.resize(10);}bool insert(const pair<K, V>& kv){if (find(kv.first))return false;//负载因子控制在0.7以内if (_n * 10 / _table.size() == 7){//扩容size_t NewSize = _table.size() * 2;HashTable<K, V> NewTable;NewTable._table.resize(NewSize);//遍历旧表，插入到新表中for (int i = 0; i < _table.size(); ++i){if (_table[i]._state == EXIST){NewTable.insert(_table[i]._kv);}}_table.swap(NewTable._table);}//线性探测Hashfunc hf;size_t hashi = hf(kv.first) % _table.size();while (_table[hashi]._state == EXIST){hashi++;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._state = EXIST;++_n;return true;}Data* find(const K& key){Hashfunc hf;size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST&& _table[hashi]._kv.first == key)return (Data*)&_table[hashi];hashi++;hashi %= _table.size();}return nullptr;}bool erase(const K& key){Data* dele = find(key);if (dele){dele->_state = DELETE;--_n;return true;}return false;}private:vector<Data> _table;size_t _n;//存储有效数据的数量};}

哈希桶

namespace hash_bucket
{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(const HashTable<K, V, Hashfunc>& ht): _table(ht._table.size(), nullptr), _n(ht._n){for (size_t i = 0; i < ht._table.size(); ++i){Node* cur = ht._table[i];Node* tail = nullptr;while (cur){Node* newNode = new Node(cur->_data);if (!_table[i]){_table[i] = newNode;}else{tail->_next = newNode;}tail = newNode;cur = cur->_next;}}}//赋值重载HashTable<K, V, Hashfunc>& operator=(const HashTable<K, V, Hashfunc>& ht){_table = ht._table;_n = ht._n;return *this;}//析构~HashTable(){for (int 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;//当负载因子对于1时，扩容if (_n / _table.size() == 1){size_t NewSize = _table.size() * 2;HashTable<K, V> NewTable;NewTable._table.resize(NewSize, nullptr);//遍历旧表，将旧表上的节点迁到新表上（避免节点创建释放操作）for (int i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;int hashi = hf(cur->_kv.first) % NewTable._table.size();cur->_next = NewTable._table[hashi];NewTable._table[hashi] = cur;cur = next;}}_table.swap(NewTable._table);}Node* NewData = new Node(kv);int hashi = hf(kv.first) % _table.size();NewData->_next = _table[hashi];_table[hashi] = NewData;++_n;return true;}Node* find(const K& key){Hashfunc hf;int 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;int hashi = hf(key) % _table.size();Node* dele = _table[hashi];Node* prev = nullptr;while (dele){if (dele->_kv.first == key){if (prev)prev->_next = dele->_next;else_table[hashi] = dele->_next;delete dele;return true;}prev = dele;dele = dele->_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;};
}