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