深入剖析：C++ 手写实现 unordered_map 与 unordered_set 全流程指南
目录
一、前言：STL 容器的魔法揭示
二、STL 哈希容器的历史与演进
2.1 SGI STL 的哈希家族
2.2 C++11 引入 unordered 容器
三、深入源码：SGI STL 的 hashtable 架构
3.1 冲突解决方式
四、手写哈希表核心结构
4.1 HashNode：链表节点
4.2 HashFunc：泛型哈希函数
4.3 HashTable 模板定义
五、Insert 插入函数 + 自动扩容
六、自定义 unordered_set 封装
七、自定义 unordered_map 封装
八、自定义迭代器支持
九、operator[] 与 key const 限定
9.1 为什么 key 不可修改？
9.2 operator[] 实现
十、总结与建议
一、前言：STL 容器的魔法揭示
在现代 C++ 开发中，unordered_map 和 unordered_set 是开发者高频使用的数据结构。它们底层使用哈希表（hash table）实现，提供O(1) 平均复杂度的插入和查找，性能极高。
但作为工程师，不能只做容器的使用者，更要理解其背后的实现机制。
本文将从底层原理、SGI STL 源码出发，手动模拟并完整实现一套泛型、可扩展、支持迭代器的 unordered_map 与 unordered_set 容器。
二、STL 哈希容器的历史与演进
2.1 SGI STL 的哈希家族
早期 C++ 标准未引入哈希表类容器，SGI STL 率先推出 hash_map 与 hash_set，底层封装自定义 hashtable 类，广受欢迎。
但它们并非 C++ 标准的一部分，也不具备跨平台稳定性。
2.2 C++11 引入 unordered 容器
C++11 正式将 unordered_map、unordered_set 纳入 STL，头文件分别是：
#include <unordered_map>
#include <unordered_set>
标准库中 unordered_* 使用开放寻址或拉链法实现，底层逻辑与 SGI STL 类似。
三、深入源码：SGI STL 的 hashtable 架构
SGI STL 的 hash_map 与 hash_set 都建立在 hashtable 基础上。
// hash_map
class hash_map {typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T>>, EqualKey, Alloc> ht;ht rep;
};
核心结构体 __hashtable_node：
struct __hashtable_node {__hashtable_node* next; // 链表结构Value val;
};
hashtable 用链式结构（拉链法）处理哈希冲突，使用 vector<node*> 作为桶数组。
3.1 冲突解决方式
-
拉链法：每个桶中是一个链表，冲突项插入链表头部。
-
开放寻址法：若冲突则探测下一个空桶。
我们本次采用拉链法实现。
四、手写哈希表核心结构
4.1 HashNode：链表节点
template<class T>
struct HashNode {T _data;HashNode<T>* _next;HashNode(const T& data) : _data(data), _next(nullptr) {}
};
4.2 HashFunc：泛型哈希函数
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 (auto ch : key) hash = hash * 131 + ch;return hash;}
};
4.3 HashTable 模板定义
template<class K, class T, class KeyOfT, class Hash>
class HashTable {std::vector<HashNode<T>*> _tables;size_t _n; // 元素个数public:bool Insert(const T& data);bool Erase(const K& key);Iterator Begin();Iterator End();void Expand();
};
五、Insert 插入函数 + 自动扩容
插入操作步骤：
-
使用哈希函数计算桶索引
-
遍历该桶链表判断是否已存在
-
若不存在则头插节点
template<class K, class T, class KeyOfT, class Hash>
bool HashTable<K, T, KeyOfT, Hash>::Insert(const T& data) {KeyOfT kot;Hash hs;size_t index = hs(kot(data)) % _tables.size();for (HashNode<T>* cur = _tables[index]; cur; cur = cur->_next) {if (kot(cur->_data) == kot(data)) return false;}if (_n >= _tables.size()) Expand();HashNode<T>* node = new HashNode<T>(data);node->_next = _tables[index];_tables[index] = node;++_n;return true;
}
扩容策略：
void Expand() {static const size_t primes[] = {53, 97, 193, 389, 769, 1543, 3079, ...};size_t newSize = NextPrime(_tables.size() * 2);std::vector<HashNode<T>*> new_table(newSize, nullptr);for (auto head : _tables) {for (HashNode<T>* cur = head; cur; ) {HashNode<T>* next = cur->_next;size_t newIdx = hs(kot(cur->_data)) % newSize;cur->_next = new_table[newIdx];new_table[newIdx] = cur;cur = next;}}_tables.swap(new_table);
}
六、自定义 unordered_set 封装
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); }};
}
测试用例：
bit::unordered_set<int> uset;
uset.insert(3);
uset.insert(7);
七、自定义 unordered_map 封装
namespace bit {template<class K, class V, class Hash = HashFunc<K>>class unordered_map {struct MapKeyOfT {const K& operator()(const std::pair<K, V>& kv) const { return kv.first; }};hash_bucket::HashTable<K, std::pair<K, V>, MapKeyOfT, Hash> _ht;public:bool insert(const std::pair<K, V>& kv) { return _ht.Insert(kv); }V& operator[](const K& key) {std::pair<K, V> kv(key, V());auto ret = _ht.Insert(kv);return const_cast<V&>(ret.first->_data.second);}};
}
用法示例：
bit::unordered_map<std::string, int> umap;
umap["apple"] = 5;
八、自定义迭代器支持
迭代器功能：
-
支持
for(auto it = begin(); it != end(); ++it) -
封装当前节点和哈希表指针
template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
struct HTIterator {HashNode<T>* _node;const HashTable<K, T, KeyOfT, Hash>* _pht;Ref operator*() const { return _node->_data; }Self& operator++() {if (_node->_next) _node = _node->_next;else 查找下一个桶...return *this;}
};
九、operator[] 与 key const 限定
9.1 为什么 key 不可修改？
key 决定元素的哈希位置，修改后会导致元素定位混乱。STL 使用 pair<const K, V> 来防止 key 被误改。
9.2 operator[] 实现
V& operator[](const K& key) {pair<K, V> kv(key, V());auto ret = _ht.Insert(kv);return const_cast<V&>(ret.first->_data.second);
}
十、总结与建议
本文从 STL 历史入手，完整实现了通用哈希表，并基于此分别封装了 unordered_map 和 unordered_set。
通过本项目，你掌握了：
-
哈希表的链式冲突处理
-
泛型模板 + 仿函数提取 key
-
插入、查找、扩容的底层实现
-
迭代器与 const 设计的注意事项
推荐练习：实现 erase()、支持 load_factor、自定义 load 控制、支持迭代器 range-for 等
欢迎评论区与我交流！