C++ Unordered 系列容器及哈希表底层原理实现
C++11 引入 unordered 系列容器,底层基于哈希表实现 O(1) 查询效率。模拟实现了 HashBucket、UnorderedMap 和 UnorderedSet,详细讲解了哈希冲突解决(开散列/链地址法)、节点设计、扩容机制及迭代器实现。通过模板特化支持 string 作为 Key,并封装了 Map 的 [] 运算符重载逻辑。

C++11 引入 unordered 系列容器,底层基于哈希表实现 O(1) 查询效率。模拟实现了 HashBucket、UnorderedMap 和 UnorderedSet,详细讲解了哈希冲突解决(开散列/链地址法)、节点设计、扩容机制及迭代器实现。通过模板特化支持 string 作为 Key,并封装了 Map 的 [] 运算符重载逻辑。


微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
在 C++98 中,STL 提供了底层为红黑树的关联式容器(map/set),查询效率为 O(logN)。为了追求极致的查找速度,C++11 引入了 unordered 系列容器,其底层采用哈希表结构,理论上查询效率可达到 O(1)。
本文将模拟实现代码(HashBucket, UnorderedMap, UnorderedSet),深入剖析其底层原理与实现细节。
哈希(Hash)通过一个哈希函数(HashFunc),将元素的关键码(Key)映射到存储位置,建立一一映射关系,从而实现不经过比较直接查找元素。
公式:hash(key) = key % capacity
当不同的关键字通过哈希函数计算出相同的哈希地址时,就会发生哈希冲突(Hash Collision)。解决冲突主要有两种方式:
当发生冲突时,如果哈希表未满,将 key 存放到冲突位置的'下一个'空位置。
线性探测:挨个往后找。容易产生'数据堆积'。
二次探测:通过跳转查找,缓解堆积。
这是 STL unordered_map 通常采用的方法,也是我们代码中实现的方法。
原理:将具有相同哈希地址的元素归于同一子集合(桶),每个桶通过单链表链接。哈希表中存储的是链表的头指针。
我们在 HashBucket.h 中实现了开散列的哈希表。
使用模板结构体 HashNode,存储数据和下一个节点的指针。
template <class T>
struct HashNode {
T _data;
HashNode* _next;
// ... 构造函数
};
为了支持 string 作为 Key,我们需要对哈希函数进行特化。代码中使用了类似 BKDRHash 的思路(乘数为 31)将字符串转化为整型。
template <>
struct HashFunc<string> {
const int operator()(const string& str) {
int hashi = 0;
for (int i = 0; i < str.size(); i++) {
hashi += str[i];
hashi *= 31; // 经典乘数,减少冲突
}
return hashi;
}
};
插入 (Insert):
index,将新节点插入到 _table[index] 的头部(效率最高)。复用节点:
在扩容时,代码没有创建新节点,而是直接将旧表的节点'搬运'到新表,节省了 new 和 delete 的开销。
if (_n == _table.size()) {
vector<Node*> newHt;
newHt.resize(_n * 2);
// 遍历旧表,重新计算 hash 值挂到新表
// ...
_table.swap(newHt);
}
unordered 容器的迭代器是单向迭代器(Forward Iterator)。
结构:迭代器需要持有 Node*(当前节点)和 HashBucket*(哈希表指针)。
operator++ 实现逻辑:
_node->_next != nullptr),则指向下一个节点。_ht 指针计算当前桶的下标,并在哈希表中向后寻找第一个非空的桶。为了复用同一份 HashBucket 代码,我们利用模板参数采用了类似适配器模式的设计。
HashBucket 存储的是 T,但不知道 T 中哪个部分是 Key。
T 就是 K。SetOfT 仿函数直接返回 Key。pair<K, V>。MapOfT 仿函数返回 pair.first。map 的 [] 运算符非常强大:如果 Key 存在则查找,不存在则插入默认值。
实现逻辑是调用 Insert,利用其返回值 pair<iterator, bool> 来获取 Value 的引用。
V& operator[](const K& key) {
auto it = Insert(make_pair(key, V())).first;
return (*it).second;
}
以上就是对哈希相关内容的总结了。