哈希表封装 myunordered_map/myunordered_set 实战：底层原理 + 完整实现

🔥草莓熊Lotso：个人主页
❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受！

🎬 博主简介：

文章目录

• 前言：
• 一. 源码及框架分析
• 二. 核心设计思路：哈希表的泛型复用
  • 2.1 哈希表模板参数设计
• 三. 实现出复用哈希表的框架，并支持insert
• 四. 实现iterator和map支持[]的功能
  • 4.1 迭代器实现：支持哈希桶遍历
  • 4.2 map支持[]
• 五. 完整代码实现
  • 5.1 HashTable.h
  • 5.2 unordered_set.h
  • 5.3 unordered_map.h
  • 5.4 测试代码(test.cpp)
• 结尾：

前言：

STL 中的 unordered_map 和 unordered_set 以高效的增删查性能（平均 O (1) 时间复杂度）成为高频使用的关联式容器，其底层核心是哈希表（哈希桶）。但很多开发者只知其然不知其所以然 —— 如何基于哈希表封装出支持 key-value 存储和 key-only 存储的两种容器？如何解决哈希冲突？如何保证 key 的唯一性？本文结合核心思路，从哈希表的泛型设计入手，一步步拆解 myunordered_map 和 myunordered_set 的封装逻辑，包括哈希函数适配、冲突解决、迭代器实现、key 约束等关键细节，附完整可运行代码，帮你吃透哈希表在容器封装中的实战应用。

一. 源码及框架分析

SGI-STL30版本源代码中没有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL
版本，这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表，只容器的名字是hash_map
和hash_set，他是作为非标准的容器出现的，非标准是指非C++标准规定必须实现的，源代码在
hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中

hash_map和hash_set的实现结构框架核心部分截取出来如下：

// stl_hash_settemplate<classValue,classHashFcn= hash<Value>,classEqualKey= equal_to<Value>,classAlloc= alloc>classhash_set{private:typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht; ht rep;public:typedeftypenameht::key_type key_type;typedeftypenameht::value_type value_type;typedeftypenameht::hasher hasher;typedeftypenameht::key_equal key_equal;typedeftypenameht::const_iterator iterator;typedeftypenameht::const_iterator const_iterator; hasher hash_funct()const{return rep.hash_funct();} key_equal key_eq()const{return rep.key_eq();}};// stl_hash_maptemplate<classKey,classT,classHashFcn= hash<Key>,classEqualKey= equal_to<Key>,classAlloc= alloc>classhash_map{private:typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T>>, EqualKey, Alloc> ht; ht rep;public:typedeftypenameht::key_type key_type;typedef T data_type;typedef T mapped_type;typedeftypenameht::value_type value_type;typedeftypenameht::hasher hasher;typedeftypenameht::key_equal key_equal;typedeftypenameht::iterator iterator;typedeftypenameht::const_iterator const_iterator;};// stl_hashtable.htemplate<classValue,classKey,classHashFcn,classExtractKey,classEqualKey,classAlloc>classhashtable{public:typedef Key key_type;typedef Value value_type;typedef HashFcn hasher;typedef EqualKey key_equal;private: hasher hash; key_equal equals; ExtractKey get_key;typedef __hashtable_node<Value> node; vector<node*, Alloc> buckets; size_type num_elements;public:typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator; pair<iterator,bool>insert_unique(const value_type& obj); const_iterator find(const key_type& key)const;};template<classValue>struct__hashtable_node{ __hashtable_node* next; Value val;};

• 这里我们就不再画图分析了，通过源码可以看到，结构上hash_map和hash_set跟map和set的完全类似，复用同一个hashtable实现key和key/value结构，hash_set传给hash_table的是两个key，hash_map传给hash_table的是pair<const key,value>
• 需要注意的是源码里面跟map/set源码类似，命名风格比较乱，这里比map和set还乱，hash_set模板参数居然用的Value命名，hash_map用的是Key和T命名。

二. 核心设计思路：哈希表的泛型复用

myunordered_map 和 myunordered_set 复用同一哈希表底层，核心通过模板参数抽象和仿函数提取 key，实现 “一颗哈希表适配两种存储场景”：

• myunordered_set：存储单个 key（去重 + 无序），需提取 key 本身进行哈希和比较；
• myunordered_map：存储 key-value 对（key 去重 + 无序），需提取 pair 中的 first 作为 key 进行哈希和比较。

2.1 哈希表模板参数设计

哈希表需支持三种核心抽象，通过模板参数暴露接口，适配不同容器需求：

template<classK,classT,classKeyofT,classHash>classHashTable{// K：哈希和查找时的key类型（myunordered_set为K，myunordered_map为K）// T：哈希表节点存储的实际数据类型（myunordered_set为K，myunordered_map为pair<const K, V>）// Hash：哈希函数仿函数（将K转为整形用于计算桶位置）// KeyOfT：从T中提取K的仿函数（适配T的不同类型）};

三. 实现出复用哈希表的框架，并支持insert

• 参考源码框架，unordered_set 和 unordered_map 复用之前我们实现的哈希表。
• 我们这里相比源码调整一下，key参数就用K，value参数就用V，哈希表中的数据类型，我们使用T
• 其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂⼀点，但是⼤框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数导致是K，还是pair<K, V>，那么insert内部进⾏插⼊时要⽤K对象转换成整形取模和K⽐较相等，因为pair的value不参与计算取模，且默认⽀持的是key和value⼀起⽐较相等，我们需要时的任何时候只需要⽐较K对象，所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成整形取模和K⽐较相等，具体细节参考如下代码实现。

// MyUnorderedSet.hnamespace Lotso {template<classK,classHash= HashFunc<K>>classunordered_set{structSetKeyofT{// 仿函数：从T（pair<const K, V>）中提取keyconst K&operator()(const K& key){return key;}};public:boolinsert(const K& key){return _ht.Insert(key);}private: hash_bucket::HashTable<K,const K, SetKeyofT, Hash> _ht;};}

// MyUnorderedMap.hnamespace Lotso {template<classK,classV,classHash= HashFunc<K>>classunordered_map{structMapKeyofT{// 仿函数：从T（pair<const K, V>）中提取keyconst K&operator()(const pair<const K, V>& kv){return kv.first;}};public:boolinsert(const pair<K, V>& kv){return _ht.Insert(kv);}private: hash_bucket::HashTable<K, pair<const K, V>, MapKeyofT, Hash> _ht;};}

// HashTable.h// 质数表(SGI STL 同款，用于扩容)staticconstint __stl_num_primes =28;staticconstunsignedlong __stl_prime_list[__stl_num_primes]={53,97,193,389,769,1543,3079,6151,12289,24593,49157,98317,196613,393241,786433,1572869,3145739,6291469,12582917,25165843,50331653,100663319,201326611,402653189,805306457,1610612741,3221225473,4294967291};inlineunsignedlong__stl_next_prime(unsignedlong n){constunsignedlong* first = __stl_prime_list;constunsignedlong* last = __stl_prime_list + __stl_num_primes;// >= nconstunsignedlong* pos =lower_bound(first, last, n);return pos == last ?*(last -1):*pos;}// 哈希函数仿函数template<classK>structHashFunc{ size_t operator()(const K& key){return(size_t)key;// 默认直接转换}};// 特化string类型的哈希函数template<>structHashFunc<string>{// BKDR字符串哈希算法 size_t operator()(const string& key){ size_t hash =0;for(auto ch : key){ hash += ch;// 累加字符ASCII码 hash *=131;// 乘质数131，减少冲突}return hash;}};namespace hash_bucket {template<classT>structHashNode{ T _data; HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}};template<classK,classT,classKeyofT,classHash= HashFunc<K>>classHashTable{typedef HashNode<T> Node;HashTable():_tables(__stl_next_prime(1),nullptr),_n(0){}~HashTable(){for(size_t i =0; i < _tables.size(); i++){ Node* cur = _tables[i];while(cur){ Node* next = cur->_next;delete cur; cur = next;} _tables[i]=nullptr;} _n =0;}boolInsert(const T& data){ KeyofT kot; Hash hs;// 先查找，避免重复插入if(Find(kot(data)))returnfalse;// 负载因子 == 1 就开始扩容if(_n == _tables.size()){ std::vector<Node*>newtables(__stl_next_prime(_tables.size()+1),nullptr);for(size_t i =0; i < _tables.size(); i++){// 遍历旧表，旧表节点重新映射，挪动到新表 Node* cur = _tables[i];while(cur){ Node* next = cur->_next;// 头插 size_t hashi =hs(kot(cur->_data))% newtables.size(); cur->_next = newtables[hashi]; newtables[hashi]= cur; cur = next;} _tables[i]=nullptr;} _tables.swap(newtables);} size_t hashi =hs(kot(data))% _tables.size();// 头插 Node* newnode =newNode(data); newnode->_next = _tables[hashi]; _tables[hashi]= newnode;++_n;returntrue;}private: std::vector<Node*> _tables; size_t _n;};}

四. 实现iterator和map支持[]的功能

4.1 迭代器实现：支持哈希桶遍历

iterator实现思路分析：

• iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算
  符实现，迭代器像指针⼀样访问的⾏为，要注意的是哈希表的迭代器是单向迭代器。
• 这⾥的难点是operator++的实现。iterator中有⼀个指向结点的指针，如果当前桶下⾯还有结点，则结点的指针指向下⼀个结点即可。如果当前桶⾛完了，则需要想办法计算找到下⼀个桶。这⾥的难点是反⽽是结构设计的问题，参考上⾯的源码，我们可以看到iterator中除了有结点的指针，还有哈希表对象的指针，这样当前桶⾛完了，要计算下⼀个桶就相对容易多了，⽤key值计算出当前桶位置，依次往后找下⼀个不为空的桶即可。
• begin()返回第⼀个桶中第⼀个节点指针构造的迭代器，这⾥end()返回迭代器可以⽤空表⽰。
• unordered_set的iterator也不⽀持修改，我们把unordered_set的第⼆个模板参数改成const K即可， HashTable<K, const K, SetKeyOfT, Hash> _ht;
• unordered_map的iterator不⽀持修改key但是可以修改value，我们把unordered_map的第⼆个模板参数pair的第⼀个参数改成const K即可，HashTable<K, pair<const K, V>,MapKeyOfT, Hash> _ht;
• ⽀持完整的迭代器还有很多细节需要修改，具体参考最后的代码。

// 哈希表迭代器template<classK,classT,classHash,classKeyOfT,classEqual>structHashTableIterator{typedef HashNode<T> Node;typedef HashTable<K, T, Hash, KeyOfT, Equal> HashTable;typedef HashTableIterator Self; Node* _node;// 当前指向的节点 HashTable* _ht;// 指向哈希表，用于桶切换// 构造函数HashTableIterator(Node* node, HashTable* ht):_node(node),_ht(ht){}// 解引用运算符（返回节点数据引用） T&operator*(){return _node->_data;}// 箭头运算符（支持->访问成员，如map的first/second） T*operator->(){return&_node->_data;}// 前置++（核心：遍历当前桶所有节点后，切换到下一个非空桶） Self&operator++(){if(_node->_next){// 当前桶还有下一个节点，直接移动 _node = _node->_next;}else{// 当前桶遍历完毕，找下一个非空桶 K key = _ht->_kot(_node->_data); size_t hashi = _ht->_hash(key)% _ht->_tables.size();// 从当前桶的下一个桶开始查找++hashi;while(hashi < _ht->_tables.size()){if(_ht->_tables[hashi]){ _node = _ht->_tables[hashi];return*this;}++hashi;}// 所有桶遍历完毕，迭代器失效（指向nullptr） _node =nullptr;}return*this;}// 相等判断booloperator==(const Self& s)const{return _node == s._node;}// 不相等判断booloperator!=(const Self& s)const{return _node != s._node;}};

4.2 map支持[]

• unordered_map要⽀持[]主要需要修改insert返回值⽀持，修改HashTable中的insert返回值为pair<Iterator, bool> Insert(const T& data)
• 有了insert⽀持[]实现就很简单了，具体参考下⾯代码实现

五. 完整代码实现

5.1 HashTable.h

#pragmaonce#include<iostream>#include<vector>#include<algorithm>usingnamespace std;// 质数表(SGI STL 同款，用于扩容)staticconstint __stl_num_primes =28;staticconstunsignedlong __stl_prime_list[__stl_num_primes]={53,97,193,389,769,1543,3079,6151,12289,24593,49157,98317,196613,393241,786433,1572869,3145739,6291469,12582917,25165843,50331653,100663319,201326611,402653189,805306457,1610612741,3221225473,4294967291};inlineunsignedlong__stl_next_prime(unsignedlong n){constunsignedlong* first = __stl_prime_list;constunsignedlong* last = __stl_prime_list + __stl_num_primes;// >= nconstunsignedlong* pos =lower_bound(first, last, n);return pos == last ?*(last -1):*pos;}// 哈希函数仿函数template<classK>structHashFunc{ size_t operator()(const K& key){return(size_t)key;// 默认直接转换}};// 特化string类型的哈希函数template<>structHashFunc<string>{// BKDR字符串哈希算法 size_t operator()(const string& key){ size_t hash =0;for(auto ch : key){ hash += ch;// 累加字符ASCII码 hash *=131;// 乘质数131，减少冲突}return hash;}};namespace hash_bucket {template<classT>structHashNode{ T _data; HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}};// 前置声明template<classK,classT,classKeyofT,classHash>classHashTable;template<classK,classT,classRef,classPtr,classKeyofT,classHash>structHTIterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyofT, Hash> HT;typedef HTIterator<K, T, Ref, Ptr, KeyofT, Hash> Self; Node* _node;const HT* _pht;HTIterator(Node* node,const HT* pht):_node(node),_pht(pht){} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;} Self&operator++(){if(_node->_next)//当前桶没走完{ _node = _node->_next;}else//当前桶走完了，找到下一个桶的第一个结点{ KeyofT kot; Hash hs;// 算出当前位置 size_t hashi =hs(kot(_node->_data))% _pht->_tables.size();// ++到下一个位置++hashi;while(hashi < _pht->_tables.size()){if(_pht->_tables[hashi])// 找到下一个不为空的桶{ _node = _pht->_tables[hashi];break;}else{++hashi;}}if(hashi == _pht->_tables.size())// 最后一个桶走完了，要++到end()位置{// end() 中_node是空 _node =nullptr;}}return*this;}booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};template<classK,classT,classKeyofT,classHash= HashFunc<K>>classHashTable{// 友元声明template<classK,classT,classRef,classPtr,classKeyofT,classHash>friendstructHTIterator;typedef HashNode<T> Node;public:typedef HTIterator<K, T, T&, T*, KeyofT, Hash> Iterator;typedef HTIterator<K, T,const T&,const T*, KeyofT, Hash> ConstIterator; Iterator Begin(){if(_n ==0){returnEnd();}for(size_t i =0; i < _tables.size(); i++){if(_tables[i]){returnIterator(_tables[i],this);}}returnEnd();} Iterator End(){returnIterator(nullptr,this);} ConstIterator Begin()const{if(_n ==0){returnEnd();}for(size_t i =0; i < _tables.size(); i++){if(_tables[i]){returnConstIterator(_tables[i],this);}}returnEnd();} ConstIterator End()const{returnConstIterator(nullptr,this);}HashTable():_tables(__stl_next_prime(1),nullptr),_n(0){}~HashTable(){for(size_t i =0; i < _tables.size(); i++){ Node* cur = _tables[i];while(cur){ Node* next = cur->_next;delete cur; cur = next;} _tables[i]=nullptr;} _n =0;} pair<Iterator,bool>Insert(const T& data){ KeyofT kot; Hash hs;// 先查找，避免重复插入if(auto it =Find(kot(data));it!=End())return{it,false};// 负载因子 == 1 就开始扩容if(_n == _tables.size()){ std::vector<Node*>newtables(__stl_next_prime(_tables.size()+1),nullptr);for(size_t i =0; i < _tables.size(); i++){// 遍历旧表，旧表节点重新映射，挪动到新表 Node* cur = _tables[i];while(cur){ Node* next = cur->_next;// 头插 size_t hashi =hs(kot(cur->_data))% newtables.size(); cur->_next = newtables[hashi]; newtables[hashi]= cur; cur = next;} _tables[i]=nullptr;} _tables.swap(newtables);} size_t hashi =hs(kot(data))% _tables.size();// 头插 Node* newnode =newNode(data); newnode->_next = _tables[hashi]; _tables[hashi]= newnode;++_n;return{Iterator(newnode,this),true};} Iterator Find(const K& key){ KeyofT kot; Hash hs; size_t hashi =hs(key)% _tables.size(); Node* cur = _tables[hashi];while(cur){if(kot(cur->_data)== key){return{ cur ,this};} cur = cur->_next;}return{nullptr,this};}boolErase(const K& key){ KeyofT kot; Hash hs; size_t hashi =hs(key)% _tables.size(); Node* prev =nullptr; Node* cur = _tables[hashi];while(cur){if(kot(cur->_data)== key){// 删除if(prev ==nullptr){// 桶中第一个节点 _tables[hashi]= cur->_next;}else{ prev->_next = cur->_next;}--_n;delete cur;returntrue;} prev = cur; cur = cur->_next;}returnfalse;}private: std::vector<Node*> _tables; size_t _n;};}

5.2 unordered_set.h

#pragmaonce#include"HashTable.h"namespace Lotso {template<classK,classHash= HashFunc<K>>classunordered_set{structSetKeyofT{// 仿函数：从T（pair<const K, V>）中提取keyconst K&operator()(const K& key){return key;}};public:typedeftypenamehash_bucket:: HashTable<K,const K, SetKeyofT, Hash>::Iterator iterator;typedeftypenamehash_bucket::HashTable<K,const K, SetKeyofT, Hash>::ConstIterator const_iterator; iterator begin(){return _ht.Begin();} iterator end(){return _ht.End();} const_iterator begin()const{return _ht.Begin();} const_iterator end()const{return _ht.End();} pair<iterator,bool>insert(const K& key){return _ht.Insert(key);} iterator find(const K& key){return _ht.Find(key);}boolerase(const K& key){return _ht.Erase(key);}private: hash_bucket::HashTable<K,const K, SetKeyofT, Hash> _ht;};}

5.3 unordered_map.h

#pragmaonce#include"HashTable.h"namespace Lotso {template<classK,classV,classHash= HashFunc<K>>classunordered_map{structMapKeyofT{// 仿函数：从T（pair<const K, V>）中提取keyconst K&operator()(const pair<const K, V>& kv){return kv.first;}};public:typedeftypenamehash_bucket::HashTable<K, pair<const K,V>, MapKeyofT, Hash>::Iterator iterator;typedeftypenamehash_bucket::HashTable<K, pair<const K,V>, MapKeyofT, Hash>::ConstIterator const_iterator; iterator begin(){return _ht.Begin();} iterator end(){return _ht.End();} const_iterator begin()const{return _ht.Begin();} const_iterator end()const{return _ht.End();} pair<iterator,bool>insert(const pair<K, V>& kv){return _ht.Insert(kv);} V&operator[](const K& key){ pair <iterator,bool> ret =insert({ key,V()});return ret.first->second;} iterator find(const K& key){return _ht.Find(key);}boolerase(const K& key){return _ht.Erase(key);}private: hash_bucket::HashTable<K, pair<const K, V>, MapKeyofT, Hash> _ht;};}

5.4 测试代码(test.cpp)

#define_CRT_SECURE_NO_WARNINGS1#include"HashTable.h"#include"unordered_set.h"#include"unordered_map.h"voidPrint(const Lotso::unordered_set<int>& s){ Lotso::unordered_set<int>::const_iterator it = s.begin();while(it != s.end()){// *it = 1; cout <<*it <<" ";++it;} cout << endl;}intmain(){ Lotso::unordered_set<int> us; us.insert(3); us.insert(1000); us.insert(2); us.insert(102); us.insert(2111); us.insert(22); Lotso::unordered_set<int>::iterator it = us.begin();while(it != us.end()){//*it = 1; cout <<*it <<" ";++it;} cout << endl;Print(us); Lotso::unordered_map<string, string> dict; dict.insert({"string","字符串"}); dict.insert({"string","字符串"}); dict.insert({"left","左边"}); dict.insert({"right","右边"});// 修改 dict["left"]="左边,剩余";// 插入 dict["insert"];// 插入+修改 dict["map"]="地图";for(auto&[k, v]: dict){//k += 'x';//v += 'x'; cout << k <<":"<< v << endl;}return0;}

结尾：

🍓 我是草莓熊 Lotso！若这篇技术干货帮你打通了学习中的卡点： 👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长 ❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量 ⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用 💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑 🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解 技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！ 

结语：myunordered_map 和 myunordered_set 的封装核心是 “哈希表泛型复用 + 仿函数解耦”—— 通过模板参数抽象不同容器的存储需求，用仿函数屏蔽 key 提取、哈希计算、相等比较的差异，最终实现 “一套底层哈希表，支撑两种容器功能”。掌握这套封装逻辑，不仅能理解 STL unordered 系列容器的底层实现，更能学会 “泛型编程 + 接口抽象” 的设计思想，在实际开发中灵活适配不同存储场景。如果需要扩展功能（如支持自定义哈希函数、解决极端哈希冲突），可基于本文代码进一步优化。

✨把这些内容吃透超牛的！放松下吧✨ʕ˘ᴥ˘ʔづきらど