从零实现STL哈希容器：unordered_map/unordered_set封装详解

本篇文章是对C++学习的STL哈希容器自主实现部分的学习分享

希望也能为你带来些帮助~

那咱们废话不多说，直接开始吧！

---

一、源码结构分析

1. SGISTL30实现剖析

// hash_set核心结构
template <class Value, class HashFcn, ...>
class hash_set {typedef hashtable<Value, Value, HashFcn, identity<Value>> ht;ht rep;  // 复用哈希表
};// hash_map核心结构
template <class Key, class T, ...>
class hash_map {typedef hashtable<pair<const Key, T>, Key, ...> ht;
};

不难看出无论是unordered_map还是unordered_set，内部的底层结构都是哈希表，基于这种事实我们可以用一句话来阐述这两个容器：

unordered_map和unordered_set是基于哈希表实现的、分别用于存储键值对和唯一键的、提供平均O(1)时间复杂度的快速查找、插入和删除操作但不保证元素的顺序性的无序关联容器。

2. HashTable关键设计

2.1 桶结构：vector<node*> buckets

核心作用
哈希表的底层存储是一个动态数组（vector），每个数组元素（称为“桶”）指向一个链表头节点（开链法解决冲突）。

• 数组下标：通过哈希函数将键（Key）映射到具体桶位置（hash(key) % buckets.size()）。

• 链表节点：同一桶内的元素以链表形式链接，解决哈希冲突（不同键映射到同一桶）。

vector<Node*> buckets;  // 如buckets[3]指向链表：NodeA -> NodeB -> nullptr

2.2 节点结构 _hashtable_node{ next; }

• 链表节点设计：每个节点需存储数据和指向下一节点的指针：

template<class T>
struct HashNode
{T _data;HashNode* _next;HashNode(const T& data):_data(data), _next(nullptr){}
};

• 开链法（Separate Chaining）：冲突时，新节点直接链接到桶对应的链表头部（头插法，O(1)时间）。

2.3 模板参数

在cplusplus上面两个容器的模板参数包含这几个：

模板参数	作用	示例（unordered_map场景）
Key	键的类型，用于哈希计算和比较	int、std::string
T	实际存储的数据类型（对unordered_set是Key，对unordered_map是pair）	pair<const int, string>
Hash（KeyOfT）	从Value中提取Key的仿函数（解决数据泛化问题）	从pair<const int, string>提取int
Pred	判断两个Key是否相等的仿函数（默认std::equal_to）	自定义字符串比较（如忽略大小写）
Alloc	内存分配器类型，用于管理pair<const Key, T>的内存分配（默认std::allocator）	自定义内存池分配器

为什么需要 Hash？

• 统一接口：哈希表本身不知道Value是Key（set）还是pair<Key, T>（map），需通过仿函数提取键。

// unordered_set的Hash（直接返回Key）
struct SetKeyOfT {const K& operator()(const K& key) { return key; }
};// unordered_map的Hash（返回pair.first）
struct MapKeyOfT {const K& operator()(const pair<K, V>& kv) { return kv.first; }
};

为什么需要Pred？

• 自定义比较规则：默认使用operator==，但某些场景需特殊处理（如字符串比较时忽略大小写）。

• struct CaseInsensitiveEqual {bool operator()(const string& a, const string& b) const {return tolower(a[0]) == tolower(b[0]);  // 仅比较首字母（示例）}
  };

2.4 工作流程示例（插入操作）

1. 提取Key：通过ExtractKey从Value中获取Key（如从pair<int,string>提取int）。

2. 计算桶位置：对Key调用哈希函数，取模得到桶下标。

3. 处理冲突：遍历桶对应的链表，用EqualKey比较是否已存在相同Key。

4. 插入节点：若不存在，将新节点插入链表头部。

2.5 设计优势

• 泛化性：一套哈希表实现通过模板参数同时支持unordered_map和unordered_set。

• 灵活性：允许用户自定义哈希函数（Hash）和键比较规则（EqualKey）。

• 高效性：开链法在负载因子合理时（如0.7~1.0）保证O(1)操作。

二、模拟实现核心架构

1. 容器-哈希表关系图

不难看出，两种容器的底层是哈希表，且哈希表的底层是哈希桶以及迭代器，

同时哈希桶的底层又是节点HashNode，

因此在我们完整实现出unordered_map以及unordered_set之前，先将这两个基本元素完成就显得至关重要了

2. 关键仿函数设计：

2.1 统一键值提取接口

• SetKeyOfT：K -> K

• MapKeyOfT：pair<K,V> -> K

• //unordered_map
  struct MapKeyOfT
  {const K& operator()(const pair<K, V>& kv){return kv.first;}
  };//unordered_set
  struct SetKeyOfT
  {const K& operator()(const K& key){return key;}
  };

2.2 哈希函数仿函数

• 作用：将键（Key）映射为一个 size_t 类型的哈希值
• （同时考虑到在unordered_map中有很多将string类型作为key的情况，我们可以为string类型做一个特化处理专门用来应对这种情况）

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};//特化
template<>
struct HashFunc<string>
{size_t operator()(const string& st){size_t hashi = 0;for (auto e : st){hashi += e;}return hashi;}
};

三、哈希表详细实现

1. 基础结构

template<class T>
struct HashNode
{T _data;HashNode* _next; //开链法解决冲突HashNode(const T& data):_data(data), _next(nullptr){}
};template<class K, class T, class KeyOfT, class Hash >
class HashTable
{
private:vector<Node*> _tables; //桶数组size_t _n = 0; //插入元素计数
};

2. 迭代器系统实现

2.1 迭代器设计难点

• 跨桶遍历（核心：operator++实现）

• 结构设计：(当前节点指针, 哈希表指针)

2.2 关键代码

//迭代器
template<class K, class T, class Ref,class Ptr,class KeyOfT, class Hash >
struct HTIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef HTIterator<K, T, Ref, Ptr,KeyOfT, Hash> Self;//成员Node* _node;const HT* _ht;HTIterator(Node* node, const HT* ht):_node(node), _ht(ht){}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)) % _ht->_tables.size();++hashi;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else{++hashi;}}if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};

2.3 容器迭代器封装

//unordered_map
typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;//unordered_set
typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;

3. 哈希表核心操作实现

• Insert()：负载因子控制+扩容策略（素数表扩容）

pair<Iterator, bool> Insert(const T& data)
{Hash hs;KeyOfT kot;//若找得到，则已经插入过了，返回false//否则继续插入Iterator it = Find(data);if(it!=End())return {it,false};if (_n == _tables.size()){vector<Node*> newTables(__stl_next_prime(0), 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 = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return { {newnode,this},true };
}

• Find()：哈希定位+链表遍历

Iterator Find(const T& data)
{Hash hs;KeyOfT kot;size_t hashi = hs(kot(data)) % _tables.size();Node* cur = _tables[hashi];while (cur){if (hs(kot(cur->_data)) == hs(kot(data))){return Iterator(cur,nullptr);}cur = cur->_next;}return End();
}

• Erase()：链表节点删除

Iterator Erase(Iterator& it)
{if (it == End()){return End();}Hash hs;KeyOfT kot;Node* to_delete = it->_node;Node* prev = nullptr;size_t hashi = hs(kot(it->_data)) % _tables.size();Node* cur = _tables[hashi];//已经定位到目标哈希桶，找目标节点while (cur != to_delete && cur != nullptr){prev = cur;cur = cur->_next;}//通常情况下不会发生if (cur == nullptr){return End();}//删头节点if (prev == nullptr){_tables[hashi] = cur->_next;}//正常情况else{prev->_next = cur->_next;}//保存下一个迭代器Node* next_node = cur->_next;Iterator next_it({ next_node,this });delete cur;--_n;if (next_node != nullptr){return next_it;}else{++hashi;while (hashi < _tables.size() && _tables[hashi] != nullptr){++hashi;}if (hashi < _tables.size()){return Iterator({ _tables[hashi],this });}else{return End();}}
}

4. 素数扩容机制

static const int __stl_num_primes = 28;
static const unsigned long __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
};//取素数的函数
inline unsigned long __stl_next_prime(unsigned long n)
{const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}

四、容器接口封装

1. unordered_set实现

template<class K,class Hash = Hash_Bucket::HashFunc<K>>
class  unordered_set
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public://typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;//typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;//另一种用法，和上面的意思是一样的，但using有更多的一些用途using iterator = typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator;using const_iterator = typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator;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);}size_t count(const K& key){return _ht.Count(key);}size_t size(){return _ht.Size();}bool empty(){return _ht.Empty();}bool erase(const K& key){return _ht.Erase(key);}iterator erase(const iterator& it){return _ht.Erase(it);}size_t bucket_count(){return _ht.Bucket_Count();}size_t bucket_size(size_t i){return _ht.Bucket_Size(i);}private:Hash_Bucket::HashTable<K, const K,SetKeyOfT, Hash> _ht;
};

2. unordered_map实现

template<class K, class V, class Hash = Hash_Bucket::HashFunc<K>>
class  unordered_map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;iterator begin(){return _ht.Begin();}iterator end(){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);}const_iterator find(const K& key)const{return _ht.Find(key);}const V& operator[](const K& key) const{const_iterator it = _ht.Find({key,V()});if (it == _ht.End()){throw out_of_range("The key is out of range");}return it->second;}size_t count(const K& key){return _ht.Count({key,V()});}size_t size(){return _ht.Size();}bool empty(){return _ht.Empty();}bool erase(const K& key){return _ht.Erase(key);}iterator erase(iterator& it){return _ht.Erase(it);}size_t bucket_size(size_t i){return _ht.Bucket_Size(i);}size_t bucket_count(){return _ht.Bucket_Count();}private:Hash_Bucket::HashTable<K, pair<const K,V>,MapKeyOfT, Hash> _ht;
};

其中，operator[ ]为此容器的特殊支持

四、关键问题解决方案

1. 类型封装问题

通过KeyOfT仿函数屏蔽K/pair差异

2. 迭代器失效问题

扩容时整体迁移（不保留原指针，在Erase（）函数中尤为体现）

3. 哈希函数特化

满足字符串的哈希实现

五、总结

1. 设计亮点

• 单一哈希表支撑双容器

• 仿函数解决数据提取泛化

2. 性能分析

• O(1)平均复杂度 vs 最差O(n)

3. 扩展方向

• 多线程安全支持

• 更优哈希冲突策略

---

附录

完整代码文件结构：

• HashTable.h（哈希表/迭代器）

• MyUnorderedSet.h

• MyUnorderedMap.h

完整代码：

HashTable.h

#pragma once
#include<iostream>
#include<vector>
using namespace std;namespace Hash_Bucket
{static const int __stl_num_primes = 28;static const unsigned long __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};//取素数的函数inline unsigned long __stl_next_prime(unsigned long n){const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}template<class T>struct HashNode{T _data;HashNode* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K>struct HashFunc{size_t operator()(const K& key){return (size_t)key;}};//特化template<>struct HashFunc<string>{size_t operator()(const string& st){size_t hashi = 0;for (auto e : st){hashi += e;}return hashi;}};//前置声明template<class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >struct HTIterator;template<class K, class T, class KeyOfT, class Hash >class HashTable{//友元template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct HTIterator;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(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){return Iterator({_tables[i],this});}}return End();}Iterator End(){return Iterator({ nullptr,this });}//这里后面蓝色的const是修饰在_tables上的，但是这里的const _table传回给HashTable类的构造函数的时候，参数HT _ht会出现权限放大的问题//因此我们就在HashTable的第二个成员也就是HT _ht的类型前加上了个const，这样就避免了权限放大的问题ConstIterator Begin() const{for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){return ConstIterator({ _tables[i],this });}}return End();}ConstIterator End() const{return ConstIterator({ nullptr,this });}HashTable(size_t size = __stl_next_prime(0)):_tables(size, nullptr){}~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;}}bool Empty(){if (Size() == 0){return true;}return false;}size_t Size(){return _n;}pair<Iterator, bool> Insert(const T& data){Hash hs;KeyOfT kot;//若找得到，则已经插入过了，返回false//否则继续插入Iterator it = Find(data);if(it!=End())return {it,false};if (_n == _tables.size()){vector<Node*> newTables(__stl_next_prime(0), 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 = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return { {newnode,this},true };}Iterator Find(const T& data){Hash hs;KeyOfT kot;size_t hashi = hs(kot(data)) % _tables.size();Node* cur = _tables[hashi];while (cur){if (hs(kot(cur->_data)) == hs(kot(data))){return Iterator(cur,nullptr);}cur = cur->_next;}return End();}ConstIterator Find(const T& data)const{Hash hs;KeyOfT kot;size_t hashi = hs(kot(data)) % _tables.size();Node* cur = _tables[hashi];while (cur){if (hs(kot(cur->_data)) == hs(kot(data))){return ConstIterator(cur, nullptr);}cur = cur->_next;}return End();}size_t Count(const T& data){Hash hs;KeyOfT kot;size_t hashi = hs(kot(data)) % _tables.size();Node* cur = _tables[hashi];while (cur){if (hs(kot(cur->_data)) == hs(kot(data))){return 1;}cur = cur->_next;}return 0;}bool Erase(const K& key) {Hash hs;KeyOfT kot;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;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}Iterator Erase(Iterator& it){if (it == End()){return End();}Hash hs;KeyOfT kot;Node* to_delete = it->_node;Node* prev = nullptr;size_t hashi = hs(kot(it->_data)) % _tables.size();Node* cur = _tables[hashi];//已经定位到目标哈希桶，找目标节点while (cur != to_delete && cur != nullptr){prev = cur;cur = cur->_next;}//通常情况下不会发生if (cur == nullptr){return End();}//删头节点if (prev == nullptr){_tables[hashi] = cur->_next;}//正常情况else{prev->_next = cur->_next;}//保存下一个迭代器Node* next_node = cur->_next;Iterator next_it({ next_node,this });delete cur;--_n;if (next_node != nullptr){return next_it;}else{++hashi;while (hashi < _tables.size() && _tables[hashi] != nullptr){++hashi;}if (hashi < _tables.size()){return Iterator({ _tables[hashi],this });}else{return End();}}}size_t Bucket_Count(){return _tables.size();}size_t Bucket_Size(size_t i){if (_tables[i] == nullptr){return 0;}else{Node* cur = _tables[i];size_t count = 0;while (cur){++count;cur = cur->_next;}return count;}}private:vector<Node*> _tables;size_t _n = 0;};///迭代器template<class K, class T, class Ref,class Ptr,class KeyOfT, class Hash >struct HTIterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef HTIterator<K, T, Ref, Ptr,KeyOfT, Hash> Self;//成员Node* _node;const HT* _ht;HTIterator(Node* node, const HT* ht):_node(node), _ht(ht){}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)) % _ht->_tables.size();++hashi;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else{++hashi;}}if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};}

MyUnorderedSet.h

#pragma once
#include"HashTable.h"namespace sp
{//注意这里在加上自己写的仿函数时，因为命名空间不同，需要在前面加上命名空间template<class K,class Hash = Hash_Bucket::HashFunc<K>>class  unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public://typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;//typedef typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;//另一种用法，和上面的意思是一样的，但using有更多的一些用途using iterator = typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator;using const_iterator = typename Hash_Bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator;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);}size_t count(const K& key){return _ht.Count(key);}size_t size(){return _ht.Size();}bool empty(){return _ht.Empty();}bool erase(const K& key){return _ht.Erase(key);}iterator erase(const iterator& it){return _ht.Erase(it);}size_t bucket_count(){return _ht.Bucket_Count();}size_t bucket_size(size_t i){return _ht.Bucket_Size(i);}void Print(const unordered_set<int>& s){unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}private:Hash_Bucket::HashTable<K, const K,SetKeyOfT, Hash> _ht;};
}

MyUnorderedMap.h

#pragma once
#include"HashTable.h"namespace sp
{template<class K, class V, class Hash = Hash_Bucket::HashFunc<K>>class  unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename Hash_Bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;iterator begin(){return _ht.Begin();}iterator end(){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);}const_iterator find(const K& key)const{return _ht.Find(key);}const V& operator[](const K& key) const{const_iterator it = _ht.Find({key,V()});if (it == _ht.End()){throw out_of_range("The key is out of range");}return it->second;}size_t count(const K& key){return _ht.Count({key,V()});}size_t size(){return _ht.Size();}bool empty(){return _ht.Empty();}bool erase(const K& key){return _ht.Erase(key);}iterator erase(iterator& it){return _ht.Erase(it);}size_t bucket_size(size_t i){return _ht.Bucket_Size(i);}size_t bucket_count(){return _ht.Bucket_Count();}private:Hash_Bucket::HashTable<K, pair<const K,V>,MapKeyOfT, Hash> _ht;};
}

---

那么本次关于STL容器自主实现的知识分享就此结束了~

非常感谢你能够看到这里~

如果感觉对你有些许的帮助也请给我三连 这会给予我莫大的鼓舞！

之后依旧会继续更新C++学习分享

那么就让我们

下次再见~