C++ 手写实现 unordered_map 和 unordered_set：深入解析与源码实战
STL 哈希容器的演进
2.1 SGI STL 与 C++11
早期的 SGI STL 中并没有unordered_map和unordered_set，而是提供了hash_map和hash_set作为扩展容器。它们并不属于 C++ 标准委员会制定的 STL 标准库，而是由 SGI 组织实现并广泛流传。
随着 C++11 的到来，unordered_map和unordered_set正式成为标准容器，被纳入<unordered_map>与<unordered_set>头文件中。
2.2hash_map和unordered_map对比
虽然名字不同，但结构设计和使用方式高度类似，都依赖底层的哈希表实现。不过由于unordered_map是 C++11 正式标准的一部分，因此更具可移植性和规范性。
三、SGI STL 哈希容器源码结构分析
SGI STL 的hash_map和hash_set都基于通用模板类hashtable实现，示例如下：
代码语言：javascript
AI代码解释
// hash_set class hash_set { typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht; ht rep; }; // hash_map class hash_map { typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T>>, EqualKey, Alloc> ht; ht rep; };底层哈希表结构：
代码语言：javascript
AI代码解释
struct __hashtable_node { __hashtable_node* next; Value val; }; class hashtable { vector<node*> buckets; size_t num_elements; };SGI STL 使用链表处理冲突，即“拉链法”。
四、从零构建哈希表框架
4.1 哈希节点结构
代码语言：javascript
AI代码解释
template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) : _data(data), _next(nullptr) {} };4.2 哈希函数定义
代码语言：javascript
AI代码解释
template<class K> struct HashFunc { size_t operator()(const K& key) const { return static_cast<size_t>(key); } }; // 特化版本支持 string template<> struct HashFunc<std::string> { size_t operator()(const std::string& key) const { size_t hash = 0; for (char ch : key) hash = hash * 131 + ch; return hash; } };4.3 哈希表接口结构
代码语言：javascript
AI代码解释
template<class K, class T, class KeyOfT, class Hash> class HashTable { vector<HashNode<T>*> _tables; size_t _n; public: bool Insert(const T& data); Iterator Begin(); Iterator End(); };五、实现插入逻辑与扩容机制
插入的基本步骤如下：
- 用哈希函数求出索引
- 查找是否已存在该 key
- 若不存在则头插法插入
- 若负载因子达到阈值，执行扩容
扩容逻辑采用“下一个质数原则”，以尽可能减少冲突。
六、封装 unordered_set 与 unordered_map
代码语言：javascript
AI代码解释
namespace bit { template<class K, class Hash = HashFunc<K>> class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) const { return key; } }; hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht; public: bool insert(const K& key) { return _ht.Insert(key); } }; }代码语言：javascript
AI代码解释
namespace bit { template<class K, class V, class Hash = HashFunc<K>> class unordered_map { struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) const { return kv.first; } }; hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht; public: bool insert(const pair<K, V>& kv) { return _ht.Insert(kv); } V& operator[](const K& key) { pair<K, V> kv(key, V()); auto ret = _ht.Insert(kv); return const_cast<V&>(ret.first->_data.second); } }; }七、自定义迭代器的设计与实现
unordered_*的迭代器是单向的（ForwardIterator）。其逻辑包括：
- 遍历链表节点
_next - 若当前桶走完，跳到下一个非空桶
定义如下：
代码语言：javascript
AI代码解释
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash> struct HTIterator { Node* _node; const HashTable<K, T, KeyOfT, Hash>* _pht; HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht); Ref operator*() const; Ptr operator->() const; Self& operator++(); bool operator!=(const Self& s) const; };配合Begin()和End()实现遍历：
代码语言：javascript
AI代码解释
for (auto it = s.begin(); it != s.end(); ++it) cout << *it << endl;八、operator[] 的支持与 Key 不可修改约束
8.1 为什么 key 不可修改？
哈希表中 key 决定了数据的桶位置，如果允许修改 key，可能导致哈希结构紊乱。因此标准库中使用pair<const K, V>。
8.2 operator[] 的实现逻辑
代码语言：javascript
AI代码解释
V& operator[](const K& key) { pair<K, V> kv(key, V()); auto ret = _ht.Insert(kv); return const_cast<V&>(ret.first->_data.second); }8.3 对比 insert 与 []
特性 | insert(kv) | operator[] |
|---|---|---|
功能 | 插入（存在返回 false） | 查找或插入 |
返回值 | pair<it, bool> | value 引用 |
修改 key | 否 | 否 |
修改 value | 需要迭代器访问 second | 支持 |
九、扩容机制与性能调优建议
9.1 扩容策略：质数数组
采用质数作为哈希桶数量有助于减少哈希冲突。
代码语言：javascript
AI代码解释
static const size_t prime_list[] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613 };9.2 负载因子 (load factor)
常设阈值为 1.0，当元素个数达到桶总数时扩容，可动态调整：
代码语言：javascript
AI代码解释
if (_n >= _tables.size()) Expand();9.3 哈希冲突优化
- 自定义哈希函数（如 BKDRHash）
- 增加桶数量，减少冲突链长度
- 使用链表以外的冲突解决（如开放定址）
十、总结
本博客从 STL 哈希容器的历史出发，逐步带你实现unordered_map和unordered_set，涵盖了：
- 哈希表的构建逻辑
- 模板泛型与仿函数提取 key
- insert、[] 和迭代器的完整支持
- key 不可修改原则与性能优化建议