为什么 unordered_set / unordered_map 这么快？我用连地址法手写了一遍

发布时间：2026/10/28 9:39:01
为什么 unordered_set / unordered_map 这么快？我用连地址法手写了一遍

目录

一、unordered_set / unordered_map 与 set / map 的区别

二、unordered_set和unordered_map的模拟实现（包含迭代器实现）

插入

unordered_set

unordered_map

迭代器版本

unordered_set

unordered_map

查询

unordered_set

unordered_map

删除

unordered_set

unordered_map

unordered_map的[]访问

完整代码（修改一部分）

HashTable.h

unoredered_set.h

unoredered_map.h

一、unordered_set / unordered_map 与 set / map 的区别

unordere_set/unordered_map的使用与set/map的使用基本上类似的，这里可以参考之前博客（深入探索C++关联容器：Set、Map、Multiset与Multimap的终极指南及底层实现剖析-CSDN博客），其中一个区别在于unordered_set/unordered_map出了几个关于哈希桶的接口。以下举例是以unordered_set为例。

1.bucket_count:用于计算申请桶的数量(也就是开的总空间数量)

unordered_set<int> us1; us1.insert(3); us1.insert(213); us1.insert(21); us1.insert(909123); us1.insert(90913); us1.insert(9093); us1.insert(903); us1.insert(93); us1.insert(931); cout << "申请开的桶的数量:" << us1.bucket_count() << endl;

2.bucket:用于计算key的桶内编号（知道key来计算编号）

unordered_set<int> us1; us1.insert(3); us1.insert(213); us1.insert(21); us1.insert(909123); us1.insert(90913); us1.insert(9093); us1.insert(903); us1.insert(93); us1.insert(931); cout << "存储key为3的桶编号:" << us1.bucket(3) << endl;

3.bucket_size:计算编号内元素个数（通过编号知道该编号桶内元素个数）

unordered_set<int> us1; us1.insert(3); us1.insert(213); us1.insert(21); us1.insert(909123); us1.insert(90913); us1.insert(9093); us1.insert(903); us1.insert(93); us1.insert(931); cout << "编号6中桶内的元素个数:" << us1.bucket_size(6) << endl;

还有一个区别就是unordered_set和unordered_map底层是哈希表无序的（不追求排序），而set和map的底层是红黑树是有序的（追求排序），所以在查询和插入的效率unordered_set这一类要高效。

需求选谁
要排序set / map
要区间查询set / map
要排名set / map
要最快查询unordered_*
不关心顺序unordered_*
防 hash 攻击set / map
迭代器稳定set / map

二、unordered_set和unordered_map的模拟实现（包含迭代器实现）

根据上篇我们博客我们实现了哈希表（哈希王座：线性探测×二次探测×链式革命——冲突解决的终极博弈-CSDN博客），而unordered_set和unordered_map是无序的，不管任何顺序，只根据key计算到对应位置进行查询插入，所以这里毋庸置疑就是用的哈希表来进行模拟实现。

插入

//连地址法 namespace HashBucket { //将key转换为数字 template<class K> struct KeyNum { size_t operator()(const K& key)const { return (size_t)key; } }; //全特化 template<> struct KeyNum<string> { size_t operator()(const string& key)const { int hash = 0; for (auto& e : key) { hash += e; hash *= 131; } return hash; } }; template<class T> struct HashNode { T _data; HashNode<T>* _next; //初始化 HashNode(T data) :_data(data) ,_next(nullptr) { } }; template<class K,class T, class KeyOft/*将T（key/pair<key,value>）转换为key*/,class Num = KeyNum<K>/*key转换为数字*/> class HashTable { //内联提供素数函数 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; } typedef HashNode<T> Node; public: //初始化 HashTable() :_table(11,nullptr) ,_n(0) { } //插入 bool Insert(const T& data) { Num num; KeyOft keyoft; if (Find(keyoft(data))) return false; //空间不够扩容 if (_n == _table.size()) { vector<Node*> newtable(__stl_next_prime(_table.size() + 1), nullptr); for (auto& e : _table) { Node* cur = e;//避免开辟空间和释放空间 while (cur) { Node* next = cur->_next; size_t hashi = num(keyoft(cur->_data)) % newtable.size(); cur->_next = newtable[hashi]; newtable[hashi] = cur; cur = next; } } //交换指针，直接一次性释放没用的数据(newtable是局部变量，出了作用域直接调用析构函数) _table.swap(newtable); } //除留余数法 size_t hashi = num(keyoft(data)) % _table.size(); //头插 Node* newnode = new Node(data); newnode->_next = _table[hashi]; _table[hashi] = newnode; ++_n; return true; } private: vector<Node*> _table;//哈希数据 size_t _n; //元素个数 }; }

unordered_set

namespace HashBucket { template<class K> class unordered_set { //仿函数（转换为key） struct SetKey { const K& operator()(const K& key) { return key; } }; public: //插入 bool insert(const K& key) { return _ht.Insert(key); } private: HashTable<K, const K, SetKey, KeyNum<K>> _ht; }; }

unordered_map

namespace HashBucket { template<class K,class V> class unordered_map { //仿函数（转换为key） struct MapKey { const K& operator()(const pair<const K,V>& kv) { return kv.first; } }; public: //插入 bool insert(const pair<const K, V>& kv) { return _ht.Insert(kv); } private: HashTable<K, pair<const K, V>, MapKey,KeyNum<K>> _ht; }; }

这里主要是注意到传仿函数的方式，在内部类中就不需要传模板，而外部就需要特殊模板去实例化。然后再区分一下传对象和传类型对象

对比维度传对象（传实例）传类型对象（传类型 / 用类型构造）
传递的本质一个已经存在的对象对象的类型本身
是否已有实例是否（在函数/类内部构造）
典型形式f(obj)template<class T> f<T>()
是否需要构造不一定一定（在使用处构造）
是否可能发生拷贝可能（值传递）不会（直接构造）
生命周期由调用者控制由当前作用域控制
是否携带状态通常有通常无（无状态）
使用目的传递数据 / 状态传递策略 / 行为规则
是否影响运行时性能可能几乎不影响（编译期确定）
是否利于模板编程一般非常有利
典型应用场景业务数据、配置对象仿函数、策略类、traits
STL 中常见用法push_back(value)std::less<T>、std::hash<T>
可替换性不可随意替换可通过模板参数灵活替换

迭代器版本

//迭代器 //当需要的类定义比需要的类要迟的就需要前置声明 template<class K, class T, class KeyOft, class Num> class HashTable; template<class K,class T,class Ptr,class Ref,class KeyOft,class Num> struct HashIterator { typedef HashNode<T> Node; typedef HashTable<K, T, KeyOft, Num> Hash; typedef HashIterator<K, T, Ptr, Ref, KeyOft, Num> Self; //初始化 HashIterator(Node* node,const Hash* ht ) :_node(node) ,_ht(ht) { } //*解引用(unordered_set) Ref operator*() { return _node->_data; } //->解引用(unordered_map) Ptr operator->() { return &(_node->_data); } //++前置 Self& operator++() { KeyOft key; Num num; //判断当前_table[node*]中的node->_next是否为空(用于++) //不为空 if (_node->_next) { _node = _node->_next;//前置++ } //为空（当前这个哈希桶已经结束了） else { //计算当前的哈希桶编号 size_t hashi = num(key(_node->_data)) % _ht->_table.size(); ++hashi;//提前++，是因为这里已经结束了，前往下一个桶 //再判断哈希桶是否为空(前提是得知道不越界) while (hashi < _ht->_table.size() && _ht->_table[hashi] == nullptr) { ++hashi; } //这一步说明有哈希桶内不为空了/hashi越界了 if (hashi == _ht->_table.size()) { _node = nullptr; } //说明不为空 else { _node = _ht->_table[hashi];//++到该不为空的头结点 } } return *this; } //判断相等 bool operator==(const Self& h)const { return _node == h._node; } bool operator!=(const Self& h)const { return _node != h._node; } private: Node* _node; const Hash* _ht; //用于迭代器不参与影响哈希桶，只是利用哈希桶来支持双选迭代器 }; template<class K,class T, class KeyOft/*将T（key/pair<key,value>）转换为key*/,class Num = KeyNum<K>/*key转换为数字*/> class HashTable { //内联提供素数函数 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; } typedef HashNode<T> Node; //为了迭代器访问私有成员 //友元类 template<class K,class T,class Ptr,class Ref ,class KeyOft,class Num> friend struct HashIterator; public: //迭代器 typedef typename HashIterator<K, T,T*,T& ,KeyOft, Num> Iterator; typedef typename HashIterator<K, T,const T*,const T&, KeyOft, Num> Const_Iterator; Iterator Begin() { for (size_t i = 0; i < _table.size(); i++) { if (_table[i]) return { _table[i], this }; } return { nullptr,this }; } Iterator End() { return { nullptr,this }; } const Const_Iterator CBegin()const { for (size_t i = 0; i < _table.size(); i++) { if (_table[i]) return { _table[i], this }; } return { nullptr,this }; } const Const_Iterator CEnd()const { return { nullptr,this }; } private: vector<Node*> _table;//哈希数据 size_t _n; //元素个数 }; }

unordered_set

namespace HashBucket { template<class K> class unordered_set { //仿函数（转换为key） struct SetKey { const K& operator()(const K& key)const { return key; } }; public: //迭代器(这里记得要提示编译器不能把这里的类型当成静态成员/成员变量了) typedef typename HashTable<K, const K, SetKey, KeyNum<K>>::Iterator iterator; typedef typename HashTable<K,const K, SetKey, KeyNum<K>>::Const_Iterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const const_iterator cbegin()const { return _ht.cbegin(); } const const_iterator cend()const { return _ht.cend(); } private: HashTable<K,const K, SetKey, KeyNum<K>> _ht; }; }

unordered_map

namespace HashBucket { template<class K,class V> class unordered_map { //仿函数（转换为key） struct MapKey { const K& operator()(const pair<const K,V>& kv)const { return kv.first; } }; public: //迭代器 typedef typename HashTable<K, pair<const K, V>, MapKey, KeyNum<K>>::Iterator iterator; typedef typename HashTable<K, pair<const K, V>, MapKey, KeyNum<K>>::Const_Iterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const const_iterator cbegin()const { return _ht.CBegin(); } const const_iterator cend()const { return _ht.CEnd(); } private: HashTable<K, pair<const K, V>, MapKey,KeyNum<K>> _ht; }; }

这里需要注意的是类型 一定要匹配，不然会出现很多类型转换不对的情况，特别是迭代器那边写的时候必须重视传的模板是否一致，还有一个细节就是，在两个类都依赖对方的时候，这就需要声明，然后这里迭代器的使用又需要后面定义哈希桶的私有成员，这里也需要友元类既能泛型迭代器还能访问私有成员。

查询

unordered_set

unordered_map

删除

bool Erase(const K& key) { if (_table.empty()) return false; Num num; KeyOft keyoft; size_t hashi = num(key) % _table.size(); Node* cur = _table[hashi]; Node* prev = nullptr; while (cur) { Node* next = cur->_next; //寻找到并删除 if (keyoft(cur->_data) == key) { //为头结点 if (prev == nullptr) _table[hashi] = next; else prev->_next = next; --_n; delete cur; cur = nullptr; return true; } prev = cur; cur = next; } return false; }

unordered_set

namespace HashBucket { template<class K> class unordered_set { //仿函数（转换为key） struct SetKey { const K& operator()(const K& key)const { return key; } }; //删除 bool erase(const K& key) { return _ht.Erase(key); } private: HashTable<K,const K, SetKey, KeyNum<K>> _ht; }; }

unordered_map

namespace HashBucket { template<class K,class V> class unordered_map { //仿函数（转换为key） struct MapKey { const K& operator()(const pair<const K,V>& kv)const { return kv.first; } }; //删除 bool erase(const K& key) { return _ht.Erase(key); } private: HashTable<K, pair<const K, V>, MapKey,KeyNum<K>> _ht; }; }

unordered_map的[]访问

namespace HashBucket { template<class K,class V> class unordered_map { //仿函数（转换为key） struct MapKey { const K& operator()(const pair<const K,V>& kv)const { return kv.first; } }; public: //迭代器 typedef typename HashTable<K, pair<const K, V>, MapKey, KeyNum<K>>::Iterator iterator; typedef typename HashTable<K, pair<const K, V>, MapKey, KeyNum<K>>::Const_Iterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const const_iterator cbegin()const { return _ht.CBegin(); } const const_iterator cend()const { return _ht.CEnd(); } public: //插入 pair<iterator,bool> insert(const pair<const K, V>& kv) { return _ht.Insert(kv); } //[]访问 V& operator[](const K& key) { return (_ht.Insert({key,V()}).first)->/*这里会调用迭代器实现的->*/second; } private: HashTable<K, pair<const K, V>, MapKey,KeyNum<K>> _ht; }; }

完整代码（修改一部分）

HashTable.h

#pragma once #include<iostream> #include<vector> using namespace std; //连地址法 namespace HashBucket { //将key转换为数字 template<class K> struct KeyNum { size_t operator()(const K& key)const { return (size_t)key; } }; //全特化 template<> struct KeyNum<string> { size_t operator()(const string& key)const { int hash = 0; for (auto& e : key) { hash += e; hash *= 131; } return hash; } }; template<class T> struct HashNode { T _data; HashNode<T>* _next; //初始化 HashNode(T data) :_data(data) ,_next(nullptr) { } }; //迭代器 //当需要的类定义比需要的类要迟的就需要前置声明 template<class K, class T, class KeyOft, class Num> class HashTable; template<class K,class T,class Ptr,class Ref,class KeyOft,class Num> struct HashIterator { typedef HashNode<T> Node; typedef HashTable<K, T, KeyOft, Num> Hash; typedef HashIterator<K, T, Ptr, Ref, KeyOft, Num> Self; //初始化 HashIterator(Node* node,const Hash* ht ) :_node(node) ,_ht(ht) { } //*解引用(unordered_set) Ref operator*() { return _node->_data; } //->解引用(unordered_map) Ptr operator->() { return &(_node->_data); } //++前置 Self& operator++() { KeyOft key; Num num; //判断当前_table[node*]中的node->_next是否为空(用于++) //不为空 if (_node->_next) { _node = _node->_next;//前置++ } //为空（当前这个哈希桶已经结束了） else { //计算当前的哈希桶编号 size_t hashi = num(key(_node->_data)) % _ht->_table.size(); ++hashi;//提前++，是因为这里已经结束了，前往下一个桶 //再判断哈希桶是否为空(前提是得知道不越界) while (hashi < _ht->_table.size() && _ht->_table[hashi] == nullptr) { ++hashi; } //这一步说明有哈希桶内不为空了/hashi越界了 if (hashi == _ht->_table.size()) { _node = nullptr; } //说明不为空 else { _node = _ht->_table[hashi];//++到该不为空的头结点 } } return *this; } //判断相等 bool operator==(const Self& h)const { return _node == h._node; } bool operator!=(const Self& h)const { return _node != h._node; } private: Node* _node; const Hash* _ht; //用于迭代器不参与影响哈希桶，只是利用哈希桶来支持双选迭代器 }; template<class K,class T, class KeyOft/*将T（key/pair<key,value>）转换为key*/,class Num = KeyNum<K>/*key转换为数字*/> class HashTable { //内联提供素数函数 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; } typedef HashNode<T> Node; //为了迭代器访问私有成员 //友元类 template<class K,class T,class Ptr,class Ref ,class KeyOft,class Num> friend struct HashIterator; public: //迭代器 typedef typename HashIterator<K, T,T*,T& ,KeyOft, Num> Iterator; typedef typename HashIterator<K, T,const T*,const T&, KeyOft, Num> Const_Iterator; Iterator Begin() { for (size_t i = 0; i < _table.size(); i++) { if (_table[i]) return { _table[i], this }; } return { nullptr,this }; } Iterator End() { return { nullptr,this }; } const Const_Iterator CBegin()const { for (size_t i = 0; i < _table.size(); i++) { if (_table[i]) return { _table[i], this }; } return { nullptr,this }; } const Const_Iterator CEnd()const { return { nullptr,this }; } public: //初始化 HashTable() :_table(11,nullptr) ,_n(0) { } //析构 ~HashTable() { for (auto& e : _table) { Node* cur = e; while (cur) { Node* next = cur->_next; delete cur; cur = next; } e = nullptr; } } //插入 pair<Iterator,bool> Insert(const T& data) { Num num; KeyOft keyoft; if (Find(keyoft(data)) != End()) return { {nullptr,this},false }; //空间不够扩容 if (_n == _table.size()) { vector<Node*> newtable(__stl_next_prime(_table.size() + 1), nullptr); for (auto& e : _table) { Node* cur = e;//避免开辟空间和释放空间 while (cur) { Node* next = cur->_next; size_t hashi = num(keyoft(cur->_data)) % newtable.size(); cur->_next = newtable[hashi]; newtable[hashi] = cur; cur = next; } } //交换指针，直接一次性释放没用的数据(newtable是局部变量，出了作用域直接调用析构函数) _table.swap(newtable); } //除留余数法 size_t hashi = num(keyoft(data)) % _table.size(); //头插 Node* newnode = new Node(data); newnode->_next = _table[hashi]; _table[hashi] = newnode; ++_n; return { {newnode,this},true }; } //查找 Iterator Find(const K& key) { //防止出现未定义行为 if (_table.empty()) return { nullptr ,this}; Num num; KeyOft keyoft; size_t hashi = num(key) % _table.size(); Node* cur = _table[hashi]; while (cur) { //寻找到 if (keyoft(cur->_data) == key) return { cur ,this}; cur = cur->_next; } return {nullptr,this};//没找到 } bool Erase(const K& key) { if (_table.empty()) return false; Num num; KeyOft keyoft; size_t hashi = num(key) % _table.size(); Node* cur = _table[hashi]; Node* prev = nullptr; while (cur) { Node* next = cur->_next; //寻找到并删除 if (keyoft(cur->_data) == key) { //为头结点 if (prev == nullptr) _table[hashi] = next; else prev->_next = next; --_n; delete cur; cur = nullptr; return true; } prev = cur; cur = next; } return false; } private: vector<Node*> _table;//哈希数据 size_t _n; //元素个数 }; }

unoredered_set.h

#pragma once #include"HashTable.h" namespace HashBucket { template<class K> class unordered_set { //仿函数（转换为key） struct SetKey { const K& operator()(const K& key)const { return key; } }; public: //迭代器(这里记得要提示编译器不能把这里的类型当成静态成员/成员变量了) typedef typename HashTable<K,const K, SetKey, KeyNum<K>>::Iterator iterator; typedef typename HashTable<K,const K, SetKey, KeyNum<K>>::Const_Iterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const const_iterator cbegin()const { return _ht.CBegin(); } const const_iterator cend()const { return _ht.CEnd(); } public: //插入 pair<iterator,bool> insert(const K& key) { return _ht.Insert(key); } //查询 iterator find(const K& key) { return _ht.Find(key); } //删除 bool erase(const K& key) { return _ht.Erase(key); } private: HashTable<K,const K, SetKey, KeyNum<K>> _ht; }; }

unoredered_map.h

#pragma once #include"HashTable.h" namespace HashBucket { template<class K,class V> class unordered_map { //仿函数（转换为key） struct MapKey { const K& operator()(const pair<const K,V>& kv)const { return kv.first; } }; public: //迭代器 typedef typename HashTable<K, pair<const K, V>, MapKey, KeyNum<K>>::Iterator iterator; typedef typename HashTable<K, pair<const K, V>, MapKey, KeyNum<K>>::Const_Iterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const const_iterator cbegin()const { return _ht.CBegin(); } const const_iterator cend()const { return _ht.CEnd(); } public: //插入 pair<iterator,bool> insert(const pair<const K, V>& kv) { return _ht.Insert(kv); } //查询 iterator find(const K& key) { return _ht.Find(key); } //删除 bool erase(const K& key) { return _ht.Erase(key); } //[]访问 V& operator[](const K& key) { return (_ht.Insert({key,V()}).first)->/*这里会调用迭代器实现的->*/second; } private: HashTable<K, pair<const K, V>, MapKey,KeyNum<K>> _ht; }; }