C++ 手写 unordered_map & unordered_set — 从零实现哈希表
本项目从头实现了 C++ 标准库中的无序关联容器 std::unordered_map 和 std::unordered_set，涵盖哈希表的两种核心冲突解决策略。适合学习哈希表原理、C++ 模板编程和 STL 容器设计的同学阅读。
整体架构
使用者代码
│
┌──────────┼──────────┐
▼ ▼ ▼
unordered_map unordered_set (上层封装)
│ │
└────┬─────┘
▼
Hash_ChaniAddress (拉链法哈希表)
↕ 模板参数选择
Hash_OpenAddress (开放定址法哈希表)
│
▼
HashFunc (哈希函数 + 质数表)核心思想：底层哈希表与上层容器解耦。hash.h 提供通用的哈希表数据结构，unorderedMap.h / unorderedSet.h 通过模板适配出 STL 风格的容器接口。
hash.h — 哈希表底层实现
哈希函数
template<class K>
class HashFunc
{
public:
size_t operator()(const K& key)
{
return size_t(key); // 整型直接转型
}
};对于大多数内置类型（int、char、指针等），直接通过 size_t(key) 转型得到哈希值。这是最简单的哈希方式。
字符串特化：BKDR 哈希
template<>
class HashFunc<std::string>
{
public:
size_t operator()(const std::string& key)
{
size_t i = 0;
for (auto& e : key)
{
i = size_t(e) + i * 131; // 多项式哈希，基数为 131
}
return i;
}
};对 std::string 使用 BKDR 哈希算法：
-
将字符串视为一个 131 进制的大数，每一位字符的 ASCII 码作为该位的数值
-
hash = hash * 131 + char
-
选择 131 是因为它是一个质数，能有效减少哈希碰撞（经验值，类似 GDIFF 的 33、Java 的 31）
💡 为什么基数是质数？ 质数能保证乘法运算后各位字符的权重分布均匀，不同排列的字符串更容易得到不同的哈希值。
📝 注释掉的 i /= 13 是尝试引入除法打散分布，但除法的效率远低于乘法，且可能破坏哈希质量，因此被保留为实验痕迹。
质数表与扩容策略
static const unsigned long __stl_prime_list[28] = {
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
};-
预置 28 个质数，相邻之间大约呈 2 倍增长
-
__stl_next_prime(n) 通过二分查找找到 >= n 的最小质数
-
来源：SGI STL，已被 GCC libstdc++ 长期使用
为什么表大小要是质数？
以 hash % table_size 取模时，如果 table_size 是合数（尤其是 2 的幂），哈希值的低位分布不均会导致大量冲突。质数能降低模式冲突的概率。
方案一：开放定址法（线性探测）
位于 namespace Hash1，类 Hash_OpenAddress。
核心数据结构
enum stuta {
Empty,
Exist,
Delete
}; // 三种状态
template<class K, class V>
struct hashstruct
{
std::pair<K, V> _kv; // 键值对
stuta _stu; // 当前槽位状态
};每个槽位维护一个状态标记，解决"删除后找不到后续元素"的问题：
-
Empty — 从未使用，查找到此为止
-
Exist — 存储了有效数据
-
Delete — 曾被使用但已删除，插入时可覆盖，查找时仍需继续
插入流程
bool insert(const std::pair<K, V> kv)
{
// 1️⃣ 负载因子 > 0.7 → 扩容
if ((double)_sz / (double)_table.size() > 0.7)
{
Hash_OpenAddress<K, V> newtable;
newtable._table.resize(__stl_next_prime(_table.size() + 1));
for (auto& e : _table)
if (e._stu == Exist)
newtable.insert(e._kv); // 重新插入
_table.swap(newtable._table);
}
// 2️⃣ 线性探测：从预期位置开始，遇到非 Empty 就继续往后找
size_t i = Key(kv.first) % _table.size();
while (_table[i]._stu != Empty)
{
if (_table[i]._kv.first == kv.first)
return false; // key 已存在，插入失败
i++;
if (i >= _table.size()) i = 0; // 绕回开头
}
// 3️⃣ 找到空位，写入
_table[i] = hashstruct(kv, Exist);
_sz++;
return true;
}关键点：
-
负载因子 0.7 — 开放定址法需要较低的负载因子，否则冲突链过长，性能急剧下降
-
线性探测 — i++ 简单向后扫描，可能导致一次聚集（连续冲突区域不断扩大）
-
扩容重建 — 创建新表 → 重新哈希全部元素 → 交换，保证旧数据不受影响
查找与删除
hashstruct<K, V>* find(const K& key)
{
int i = key % _table.size();
while (_table[i]._kv.first != key && _table[i]._stu != Empty)
i++; // 线性探测直到找到或遇到空位
if (_table[i]._stu == Exist)
return &_table[i];
return nullptr;
}
bool Erase(const K& key)
{
hashstruct<K, V>* n = find(key);
if (n == nullptr) return true;
n->_stu = Delete; // 标记为 Delete，而非 Empty
n->_kv = std::pair<K, V>(K(), V());
_sz--;
return true;
}删除为什么标记 Delete 而不是 Empty？
如果直接标记为 Empty，后续查找本应经过此槽位的元素时，会在此处误认为"没找到"而提前终止。Delete 状态告诉查找"这里之前有元素，请继续向后探测"。
方案二：拉链法（哈希桶 + 链表）
位于 namespace Hash2，类 Hash_ChaniAddress。
这是 unordered_map 和 unordered_set 实际采用的方案，也是 C++ 标准库的实现方式。
核心数据结构
template<class T>
struct Hash_Chani {
T _data;
struct Hash_Chani* next; // 单链表指针
};_table (vector<Node*>)
┌──────┐
│ 0 │ → Node → Node → Node
├──────┤
│ 1 │ → nullptr
├──────┤
│ 2 │ → Node → Node
├──────┤
│ ... │
└──────┘每个桶就是一个单链表的头指针。插入时通过 hash(key) % size 定位到桶，然后头插到链表中。
插入流程
std::pair<Iterator, bool> insert(T data)
{
HashFun key;
// 1️⃣ 负载因子 == 1 时扩容（元素数 == 桶数）
if (_n == _table.size())
{
vector<Node*> newNode;
newNode.resize(__stl_next_prime(_table.size() + 1));
for (size_t i = 0; i < _table.size(); i++)
{
Node* C = _table[i];
while (C)
{
Node* P = C;
C = C->next;
size_t x = key(Kval(P->_data)) % newNode.size();
P->next = newNode[x]; // 头插到新桶
newNode[x] = P;
}
_table[i] = nullptr;
}
_table.swap(newNode);
}
// 2️⃣ 去重检查
if (find(Kval(data)) != Iterator(this, nullptr))
return { find(Kval(data)), false };
// 3️⃣ 头插
size_t x = key(Kval(data)) % _table.size();
Node* cur = new Node(data);
cur->next = _table[x];
_table[x] = cur;
_n++;
return { Iterator(this, cur), true };
}扩容细节
扩容发生在 _n == _table.size()（即桶均负载为 1）时：
-
计算新容量：__stl_next_prime(旧容量 + 1)，比如 11 → 53
-
分配新桶数组（全 nullptr）
-
遍历旧桶所有节点，重新计算哈希取模新容量，头插到新桶
-
交换新旧桶数组
注意：扩容时必须"重新哈希"而非简单复制，因为 hash % new_size 的结果与 hash % old_size 不同。
查找
Iterator find(K Key)
{
HashFun key;
size_t x = key(Key) % _table.size();
Node* cur = _table[x];
while (cur)
{
if (Kval(cur->_data) == Key)
return Iterator(this, cur);
cur = cur->next;
}
return Iterator(this, cur); // 返回 end()
}删除
bool Erase(const K& Key)
{
HashFun key;
size_t x = key(Key) % _table.size();
Node* cur = _table[x], *P = cur;
while (cur)
{
if (Kval(cur->_data) != Key)
{
P = cur;
cur = cur->next;
}
else
{
if (cur == _table[x]) // 删除头节点
_table[x] = cur->next;
else // 删除中间节点
P->next = cur->next;
delete cur;
--_n;
return true;
}
}
return false;
}需要保存前驱 P 以维护链表完整性。
迭代器设计
迭代器是哈希表对外暴露遍历能力的核心。这里实现了正向迭代器（只支持 ++）。
template<class K, class T, class Ref, class Ptr, class KeyOft, class HashFun>
struct iterator
{
Node* _data; // 当前指向的链表节点
const HT* HashAble; // 所属哈希表，用于跨桶跳转
Ref operator*() { return _data->_data; }
Ptr operator->() { return &(_data->_data); }
Seft& operator++()
{
if (_data->next)
{
// 本桶内还有下一个节点
_data = _data->next;
}
else
{
// 本桶遍历完毕，跳到下一个非空桶
size_t x = HashFun()(KeyOft()(_data->_data)) % HashAble->_table.size();
x++;
while (x < HashAble->_table.size())
{
if (HashAble->_table[x])
{
_data = HashAble->_table[x];
return *this;
}
x++;
}
// 都遍历完了，指向 nullptr（end）
}
_data = _data->next; // 这里会指向 nullptr
return *this;
}
bool operator!=(const Seft& t) const
{
return t._data != _data;
}
};++ 运算符的核心逻辑：
当前节点有下一个节点? ──是──→ _data = _data->next
│
否
▼
计算当前桶索引 x
x++，从下一个桶开始扫描
┌─────────────────────┐
│ 找到非空桶? │──是──→ _data = 该桶头节点
└─────────────────────┘
│
否
▼
_data = nullptr (end)📌 迭代器中保存了 HashAble（指向所属哈希表的指针），这使得迭代器能够跨越不同的桶进行遍历。
unorderedMap.h — unordered_map 封装
类型适配
template<class K, class V>
class unordered_map
{
struct mapKeyOft {
const K& operator()(const std::pair<const K, V>& key) {
return key.first; // 从 pair 中提取 key
}
};
// 底层容器：拉链法哈希表，数据类型为 std::pair<const K, V>
typedef Hash2::Hash_ChaniAddress<K, std::pair<const K, V>, mapKeyOft> HashNode;
};mapKeyOft 的作用：告诉哈希表"如何从存储的数据中提取 key"。对于 map，存储的是 pair<const K, V>，key 就是 pair.first。
核心接口
| 方法 | 实现 | 说明 |
|---|---|---|
| insert | _t.insert(k) | 插入 pair，返回 pair<iterator, bool> |
| find | _t.find(k) | 返回迭代器 |
| erase | _t.Erase(k) | 删除元素 |
| operator[] | _t.insert({k, V()}).first->second | 关键技巧：用 insert 实现"不存在则插入默认值，然后返回引用" |
operator[] 的巧妙实现
V& operator[](const K& k)
{
return (_t.insert({ k, V() }).first)->second;
}一行代码同时完成了两件事：
-
如果 key 不存在 → 插入 (k, V())，返回新插入节点的 second 引用
-
如果 key 已存在 → insert 返回现有节点，直接拿到 second 引用
迭代器类型重命名
typedef typename HashNode::Iterator iterator;
typedef typename HashNode::const_Iterator const_iterator;📌 typename 关键字必不可少！因为 HashNode::Iterator 是一个依赖类型（dependent type），编译器在模板实例化之前无法确定它是类型还是静态成员，需要 typename 显式声明。
unorderedSet.h — unordered_set 封装
与 map 类似，但更简单——因为 set 只存 key，没有 value。
类型适配
template<class T>
class unordered_set
{
struct setKeyOft
{
const T& operator()(const T& key)
{
return key; // 数据本身就是 key
}
};
// 注意第二个模板参数是 const T，因为 set 的元素不可修改
typedef Hash2::Hash_ChaniAddress<T, const T, setKeyOft> HashNode;
};与 unordered_map 的对比
| 对比项 | unordered_map | unordered_set |
|---|---|---|
| 存储数据 | pair<const K, V> | T |
| KeyOft | 取 pair.first | 返回自身 |
| 元素是否可修改 | value 可改，key 不可改 | 均不可改（存储 const T） |
| operator[] | ✅ 支持 | ❌ 不支持 |
📌 Set 存储 const T 是为了防止用户通过迭代器修改元素，否则会导致哈希表内部状态不一致（修改后的元素可能已经不再属于当前桶）。
小结
开放定址法 vs 拉链法
| 特性 | 开放定址法（线性探测） | 拉链法（哈希桶） |
|---|---|---|
| 实现复杂度 | 较低 | 稍高（需管理链表） |
| 空间利用率 | 较低（需要预留空位） | 较高 |
| 负载因子上限 | ~0.7-0.8 | ~1（可更高） |
| 冲突处理 | 占用后续空位（一次聚集） | 挂到桶的链表 |
| 删除 | 需标记 Delete，不可直接清空 | 直接删除链表节点 |
| 缓存局部性 | 好（连续内存） | 差（链表节点分散） |
| 实际应用 | 不常用（标准库未采用） | ✅ C++ 标准库采用 |
可以继续优化的方向
-
二次探测 / 双重哈希 — 缓解开放定址法的一次聚集
-
红黑树升级 — 当链表过长时，将链表转为红黑树（Java 8+ HashMap 的做法，C++ 标准库未采用但可作练习）
-
移动语义 — 插入时使用 std::move 减少拷贝
-
完美转发 — insert 支持 std::pair 的不同构造形式
-
异常安全 — 扩容时如果 new 失败，确保原数据不丢失
-
const 正确性 — 更多接口的 const 重载
本项目代码旨在学习，保留了开发过程中的查错痕迹（如注释的 i /= 13、friend ostream 等），供参考。
更多推荐
7
0- 0
已为社区贡献14条内容
所有评论(0)