C++ 进阶：从理论到手撕 Unordered 系列容器（哈希表）

Unordered 系列容器概述

在 C++98 中，STL 提供了底层为红黑树的关联式容器（map/set），查询效率为 。为了追求极致的查找速度，C++11 引入了 unordered 系列容器，其底层采用哈希表结构，理论上查询效率可达到 O ( 1 ) O(1) O(1) 。

本文将模拟实现代码（HashBucket, UnorderedMap, UnorderedSet），深入剖析其底层原理与实现细节。

1. 哈希基础与冲突解决

1.1 哈希概念

哈希（Hash）通过一个哈希函数（HashFunc），将元素的关键码（Key）映射到存储位置，建立一一映射关系，从而实现不经过比较直接查找元素 。

公式： h a s h ( k e y ) = k e y % c a p a c i t y hash(key) = key \% capacity hash(key)=key%capacity

1.2 哈希冲突

当不同的关键字通过哈希函数计算出相同的哈希地址时，就会发生哈希冲突（Hash Collision）。解决冲突主要有两种方式：

A. 闭散列（开放定址法）

当发生冲突时，如果哈希表未满，将 key 存放到冲突位置的“下一个”空位置 。

线性探测：挨个往后找。容易产生“数据堆积” 。
二次探测：通过 跳转查找，缓解堆积 。

B. 开散列（链地址法/哈希桶）

这是 STL unordered_map 通常采用的方法，也是我们代码中实现的方法。

原理：将具有相同哈希地址的元素归于同一子集合（桶），每个桶通过单链表链接。哈希表中存储的是链表的头指针 。

2. 模拟实现：底层哈希桶 (HashBucket)

我们在 HashBucket.h 中实现了开散列的哈希表。

2.1 节点设计

使用模板结构体 HashNode，存储数据和下一个节点的指针。

template<classT>structHashNode{ T _data; HashNode* _next;// ... 构造函数};

2.2 哈希函数与字符串特化

为了支持 string 作为 Key，我们需要对哈希函数进行特化。代码中使用了类似 BKDRHash 的思路（乘数为 31）将字符串转化为整型 。

template<>structHashFunc<string>{constintoperator()(const string& str){int hashi =0;for(int i =0; i < str.size(); i++){ hashi += str[i]; hashi *=31;// 经典乘数，减少冲突}return hashi;}};

2.3 插入与扩容

插入 (Insert)：

1. 先查找元素是否存在，存在则返回 false。
2. 扩容检查：在开散列中，当元素个数 == 桶的个数（负载因子为 1）时，冲突概率变大，需要扩容 。
3. 头插法：计算下标 index，将新节点插入到 _table[index] 的头部（效率最高）。

复用节点：
在扩容时，代码没有创建新节点，而是直接将旧表的节点“搬运”到新表，节省了 new 和 delete 的开销。

if(_n == _table.size()){ vector<Node*> newHt; newHt.resize(_n *2);// 遍历旧表，重新计算 hash 值挂到新表// ... _table.swap(newHt);}

2.4 迭代器设计

unordered 容器的迭代器是单向迭代器（Forward Iterator）。

• 结构：迭代器需要持有 Node*（当前节点）和 HashBucket*（哈希表指针）。
• operator++ 实现逻辑：

1. 如果当前桶的链表还没走完 (_node->_next != nullptr)，则指向下一个节点。
2. 如果当前桶走完了，利用 _ht 指针计算当前桶的下标，并在哈希表中向后寻找第一个非空的桶

3. 封装：UnorderedSet 与 UnorderedMap

为了复用同一份 HashBucket 代码，我们利用模板参数采用了类似适配器模式的设计。

3.1 提取 Key 的策略 (KeyOfT)

HashBucket 存储的是 T，但不知道 T 中哪个部分是 Key。

• UnorderedSet：存储的是 Key，T 就是 K。SetOfT 仿函数直接返回 Key。
• UnorderedMap：存储的是 pair<K, V>。MapOfT 仿函数返回 pair.first 。

3.2 UnorderedMap 的 operator[]

map 的 [] 运算符非常强大：如果 Key 存在则查找，不存在则插入默认值。
实现逻辑是调用 Insert，利用其返回值 pair<iterator, bool> 来获取 Value 的引用 。

V&operator[](const K& key){auto it =Insert(make_pair(key,V())).first;return(*it).second;}

总结

以上就是对哈希相关内容的总结了,需要具体代码的可以查看我的gitee仓库: 传送门.