跳到主要内容 C++ unordered 系列容器认识与模拟实现 | 极客日志
C++ 算法
C++ unordered 系列容器认识与模拟实现 介绍 C++ STL 中基于哈希表实现的 unordered_map 和 unordered_set 容器。阐述了其无序存储、O(1) 平均时间复杂度的特性，对比了与普通 map/set 的差异。重点讲解了底层哈希桶结构、冲突解决及自定义哈希函数方法。最后通过代码模拟实现了 unordered 系列的核心逻辑，包括迭代器单向遍历、扩容机制及插入删除操作。
蜜桃汽水 发布于 2026/3/30 更新于 2026/4/13 1. 了解 unordered 系列
在 C++ STL（标准模板库）中，unordered_map 和 unordered_set 是两种基于哈希表（Hash Table）实现的关联式容器，核心特点是 无序存储、平均时间复杂度 O(1) 的增删查操作 ，但需注意哈希冲突对性能的影响。二者设计目标不同（键值对存储 vs 单一值存储），但底层原理和核心特性高度相似。
1.1 初步认识
unordered_set：
unordered_set 的声明如下，Key 就是 unordered_set 底层关键字的类型：
template <class Key ,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator<Key>
class unordered_set;
unordered_set 默认要求 Key 支持转换为整形，如果不支持或者想按自己的需求走可以自行实现支持将 Key 转成整形的仿函数传给第二个模板参数；unordered_set 默认要求 Key 支持比较相等，如果不支持或者想按自己的需求走可以自行实现支持将 Key 比较相等的仿函数传给第三个模板参数；unordered_set 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第四个参数。
一般情况下，我们都不需要传后三个模板参数。unordered_set 迭代器遍历不再有序，为了跟 set 区分，所以取名 unordered_set。前面部分我们已经学习了 set 容器的使用，set 和 unordered_set 的功能高度相似，只是底层结构不同，有一些性能和使用上的差异，下面会讲它们的差异部分。
unordered_map：
unordered_map 的声明如下：
template <class Key ,
class T ,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator<pair<微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
const
class
unordered_map 和 unordered_set 共享相同的底层实现逻辑 —— 链式哈希表（哈希桶） ，这决定了它们的共同特性：
哈希数组（桶数组） ：数组的每个元素称为一个「桶（Bucket）」，桶的索引由「键的哈希值 % 桶数组大小」计算得出；解决哈希冲突 ：当两个不同的键计算出相同的桶索引时（哈希冲突），桶内会通过「链表」存储冲突元素（C++11 后部分实现会在链表长度超过阈值时转为红黑树，进一步优化查询效率）。 这种结构的核心优势是：平均情况下，增删查操作的时间复杂度为 O(1) （直接通过哈希值定位桶，再遍历桶内短链表）；最坏情况（所有键哈希冲突）下复杂度为 O(n)（退化为单链表遍历）。
与 map/set（基于红黑树实现，有序存储）不同，unordered_map/unordered_set 的元素不按键的大小排序 ，存储顺序完全由键的哈希值决定，因此遍历结果是'随机无序'的。
插入已存在的键时，insert 函数会返回 pair<iterator, bool>，其中 bool 为 false，表示插入失败，迭代器指向已存在的旧键；
无法通过任何接口修改已插入的键（unordered_map 的键被封装为 const K，unordered_set 的值本身就是键），只能删除后重新插入。
默认情况下，二者使用 STL 提供的 std::hash 模板计算键的哈希值（支持 int、string、double 等基础类型）；若存储自定义类型（如自定义结构体） ，需手动提供哈希函数（通过模板参数传入，如 unordered_map<MyStruct, int, MyHashFunc>），同时确保哈希函数满足：
相同的键必须生成相同的哈希值；
不同的键尽量生成不同的哈希值（减少冲突）。
1.2 核心差异 unordered_map 和 unordered_set 的本质区别在于存储的元素类型 ，这直接决定了它们的使用场景：
特性 unordered_map unordered_set 存储元素 键值对（std::pair<const K, V>） 单一值（const K，值即键） 核心功能 通过键快速查找对应的值（键值映射） 快速判断一个值是否存在（去重、判重） 关键接口差异 支持 operator[]（通过键访问 / 修改值） 无 operator[]（仅需判断值是否存在） 迭代器解引用结果 指向键值对（pair<const K, V>），可通过 ->first 访问键、->second 访问值 指向单一值（const K），解引用直接得到键 典型使用场景 字典（如单词 - 翻译映射）、缓存（如 ID - 用户信息映射） 去重（如统计数组中不重复元素）、快速判重（如判断用户是否在黑名单）
1.3 使用示例 #include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main ()
int > score_map;
score_map.insert ({"Alice" , 95 });
score_map.insert (pair <string, int >("Bob" , 88 ));
score_map["Charlie" ] = 92 ;
auto it = score_map.find ("Bob" );
if (it != score_map.end ())
{
cout << "Bob's score: " << it->second << endl;
}
score_map["Bob" ] = 90 ;
it->second = 90 ;
for (const auto & kv : score_map)
{
cout << kv.first << ": " << kv.second << endl;
}
score_map.erase ("Charlie" );
return 0 ;
}
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
int main ()
int > num_set;
vector<int > nums = {3 , 1 , 4 , 1 , 5 , 9 , 2 , 6 , 5 };
for (int num : nums)
{
auto ret = num_set.insert (num);
if (!ret.second)
{
cout << "值 " << num << " 已存在，插入失败" << endl;
}
}
if (num_set.count (5 ))
{
cout << "值 5 存在于集合中" << endl;
}
for (int num : num_set)
{
cout << num << " " ;
}
cout << endl;
num_set.erase (9 );
return 0 ;
}
1.4 与普通 map/set 的区别 在 C++ STL 中，unordered_map/unordered_set（统称「unordered 系列」）与 map/set（统称「普通有序系列」）是两组功能相似但设计原理完全不同的关联式容器，他们的底层差异是他们差异的根源：
容器系列 底层数据结构 核心设计目标 unordered 系列 链式哈希表（哈希桶） 追求「快速增删查」，以空间换时间 普通有序系列 红黑树（自平衡二叉搜索树） 追求「有序存储」，兼顾效率与排序
两组容器没有「绝对优劣」，选择的核心是匹配需求优先级 ，以下是典型场景的选择逻辑：
需求优先级 推荐容器 原因 追求增删查的效率 （O(1)） unordered_map/unordered_set 哈希表平均复杂度更低，适合数据量大、对效率敏感的场景 需要有序存储 （如按键排序遍历） map/set 红黑树天然有序，支持 lower_bound/upper_bound 等范围查询接口 存储自定义类型 且不愿写哈希函数 map/set 仅需重载 < 运算符（红黑树排序用），无需自定义哈希函数 内存占用敏感 map/set 哈希表需预留桶数组空间（通常有负载因子，如 0.7），内存利用率略低
2. 模拟实现 unordered 系列 我们已经对 unordered 系列有了了解，那么接下来我们就像之前用红黑树模拟实现 map/set 一样，我们使用哈希表来模拟实现一下 unordered 系列。
其次跟 map 和 set 相比而言 unordered 系列的模拟实现类结构更复杂一点，但是大框架和思路是完全类似的。因为 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 比较相等。这一点与前面的 map 和 set 是类似的。
其实大体的思路与之前的思路相同，只是在封装迭代器以及细节方面与之前有些差异。因此我们重点来看一看迭代器的实现。
2.1 迭代器 unordered 系列的 iterator 实现的大框架跟 list 的 iterator 思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为，要注意的是哈希表的迭代器是单向迭代器。这里的难点是 operator++ 的实现。iterator 中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点反而是结构设计的问题，因此在 iterator 中除了有结点的指针，还需要有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用 key 值计算出当前桶位置，依次往后找下一个不为空的桶即可。下面是代码实例：
template <class K , class T , class Ref , class Ptr , class KeyOfT , class Hash >
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _pht;
Self& operator ++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
KeyOfT kot;
Hash hs;
size_t hashi = hs (kot (_node->_data)) % _pht->_tables.size () + 1 ;
while (hashi < _pht->_tables.size ())
{
if (_pht->_tables[hashi])
{
_node = _pht->_tables[hashi];
break ;
}
hashi++;
}
if (hashi == _pht->_tables.size ())
{
_node = nullptr ;
}
}
return *this ;
}
};
begin() 返回第一个桶中第一个节点指针构造的迭代器，这里 end() 返回迭代器可以用空表表示。
至于其他的小细节例如通过模板参数 Ref 和 Ptr 来实现 iterator 和 const_iterator 以及使用模板参数 T 来代表底层的数据类型，模板参数 K 来进行 find 和 erase 等等细节与我们使用红黑树实现 map 和 set 是几乎完全一样的，这里就不再赘述，下面直接给出完整的代码实现：
#pragma once
#include "hash_bucket.h"
namespace hcy {
template <class K , class Hash = 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;
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 (); }
bool erase (const K& key) return _ht.Erase (); }
private :
hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
}
#pragma once
#include "hash_bucket.h"
namespace hcy {
template <class K , class V , class Hash = 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 (); }
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); }
iterator find (const K& key) { return _ht.Find (); }
bool erase (const K& key) return _ht.Erase (); }
V& operator [](const K& key)
{
pair<iterator, bool > ret = _ht.Insert ({ key, V () });
return ret.first->second;
}
private :
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
#pragma once
#include <iostream>
#include <string>
#include <vector>
using namespace std;
template <class K >
struct HashFunc
{
size_t operator () (const K& key) return (size_t )key; }
};
template <>
struct HashFunc <string>
{
size_t operator () (const string& s)
size_t ret = 0 ;
for (auto e : s)
{
ret *= 31 ;
ret += e;
}
return ret;
}
};
namespace hash_bucket {
template <class T >
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode (const T& data) :_data(data), _next(nullptr ) {}
};
template <class K , class T , class KeyOfT , class Hash >
class HashTable ;
template <class K , class T , class Ref , class Ptr , class KeyOfT , class Hash >
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _pht;
HTIterator (Node* node, const HashTable<K, T, KeyOfT, Hash>* 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 () + 1 ;
while (hashi < _pht->_tables.size ())
{
if (_pht->_tables[hashi])
{
_node = _pht->_tables[hashi];
break ;
}
hashi++;
}
if (hashi == _pht->_tables.size ())
{
_node = nullptr ;
}
}
return *this ;
}
bool operator !=(const Self& self) { return self._node != _node; }
bool operator ==(const Self& self) { return self._node == _node; }
};
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;
inline unsigned long __stl_next_prime(unsigned long n)
{
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
};
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;
}
public :
typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
HashTable () { _tables.resize (__stl_next_prime(0 ), nullptr ); }
~HashTable ()
{
for (size_t i = 0 ; i < _tables.size (); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* tmp = cur;
cur = cur->_next;
delete tmp;
}
_tables[i] = nullptr ;
}
}
Iterator End () { return Iterator (nullptr , this ); }
Iterator Begin ()
{
if (_n == 0 ) { return End (); }
for (int i = 0 ; i < _tables.size (); i++)
{
if (_tables[i]) { return Iterator (_tables[i], this ); }
}
return End ();
}
ConstIterator End () const { return Iterator (nullptr , this ); }
ConstIterator Begin () const
{
if (_n == 0 ) { return End (); }
for (int i = 0 ; i < _tables.size (); i++)
{
if (_tables[i]) { return Iterator (_tables[i], this ); }
}
return End ();
}
pair<Iterator, bool > Insert (const T& data)
{
KeyOfT kot;
Hash hs;
Iterator it = Find (kot (data));
if (it != End ()) { return { it, false }; }
if ((double )_n / _tables.size () >= 0.75 )
{
vector<Node*> newtables (__stl_next_prime(_tables.size() + 1 ), nullptr ) ;
for (int 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.swap (newtables);
}
size_t hash_i = hs (kot (data)) % _tables.size ();
Node* newnode = new Node (data);
newnode->_next = _tables[hash_i];
_tables[hash_i] = newnode;
++_n;
return { Iterator (newnode, this ), true };
}
Iterator Find (const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs (key) % _tables.size ();
Node* cur = _tables[hashi];
while (cur)
{
if (kot (cur->_data) == key) { return Iterator (cur, this ); }
cur = cur->_next;
}
return End ();
}
bool Erase (const K& key)
size_t hashi = hs (key) % _tables.size ();
Node* cur = _tables[hashi];
Node* prev = nullptr ;
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 ;
}
private :
vector<Node*> _tables;
size_t _n = 0 ;
};
}
#include "unordered_set.h"
#include "unordered_map.h"
void test_map ()
insert ({"sort" , "排序" });
dict.insert ({"left" , "左边" });
dict.insert ({"right" , "右边" });
dict["left" ] = "左边" ;
dict["insert" ] = "插入" ;
dict["string" ];
hcy::unordered_map<string, string>::iterator it = dict.begin ();
while (it != dict.end ())
{
it->second += 'x' ;
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
void test_set ()
int > s;
int a[] = {4 , 2 , 6 , 1 , 3 , 5 , 15 , 7 , 16 , 14 , 3 , 3 , 15 };
for (auto e : a)
{
s.insert (e);
}
for (auto e : s)
{
cout << e << " " ;
}
cout << endl;
hcy::unordered_set<int >::iterator it = s.begin ();
while (it != s.end ())
{
cout << *it << " " ;
++it;
}
cout << endl;
}
int main ()
test_set ();
cout << endl;
test_map ();
return 0 ;
}
运行结果符合预期。这就是 unordered 系列的模拟实现。
