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

目录一、unordered_set / unordered_map 与 set / map 的区别二、unordered_set和unordered_map的模拟实现包含迭代器实现插入unordered_setunordered_map迭代器版本unordered_setunordered_map查询unordered_setunordered_map删除unordered_setunordered_mapunordered_map的[]访问完整代码修改一部分HashTable.hunoredered_set.hunoredered_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_setint 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_setint 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_setint 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转换为数字 templateclass K struct KeyNum { size_t operator()(const K key)const { return (size_t)key; } }; //全特化 template struct KeyNumstring { size_t operator()(const string key)const { int hash 0; for (auto e : key) { hash e; hash * 131; } return hash; } }; templateclass T struct HashNode { T _data; HashNodeT* _next; //初始化 HashNode(T data) :_data(data) ,_next(nullptr) { } }; templateclass K,class T, class KeyOft/*将Tkey/pairkey,value转换为key*/,class Num KeyNumK/*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 HashNodeT 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()) { vectorNode* 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: vectorNode* _table;//哈希数据 size_t _n; //元素个数 }; }unordered_setnamespace HashBucket { templateclass 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: HashTableK, const K, SetKey, KeyNumK _ht; }; }unordered_mapnamespace HashBucket { templateclass K,class V class unordered_map { //仿函数转换为key struct MapKey { const K operator()(const pairconst K,V kv) { return kv.first; } }; public: //插入 bool insert(const pairconst K, V kv) { return _ht.Insert(kv); } private: HashTableK, pairconst K, V, MapKey,KeyNumK _ht; }; }这里主要是注意到传仿函数的方式在内部类中就不需要传模板而外部就需要特殊模板去实例化。然后再区分一下传对象和传类型对象对比维度传对象传实例传类型对象传类型 / 用类型构造传递的本质一个已经存在的对象对象的类型本身是否已有实例是否在函数/类内部构造典型形式f(obj)templateclass T fT()是否需要构造不一定一定在使用处构造是否可能发生拷贝可能值传递不会直接构造生命周期由调用者控制由当前作用域控制是否携带状态通常有通常无无状态使用目的传递数据 / 状态传递策略 / 行为规则是否影响运行时性能可能几乎不影响编译期确定是否利于模板编程一般非常有利典型应用场景业务数据、配置对象仿函数、策略类、traitsSTL 中常见用法push_back(value)std::lessT、std::hashT可替换性不可随意替换可通过模板参数灵活替换迭代器版本//迭代器 //当需要的类定义比需要的类要迟的就需要前置声明 templateclass K, class T, class KeyOft, class Num class HashTable; templateclass K,class T,class Ptr,class Ref,class KeyOft,class Num struct HashIterator { typedef HashNodeT Node; typedef HashTableK, T, KeyOft, Num Hash; typedef HashIteratorK, 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; //用于迭代器不参与影响哈希桶只是利用哈希桶来支持双选迭代器 }; templateclass K,class T, class KeyOft/*将Tkey/pairkey,value转换为key*/,class Num KeyNumK/*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 HashNodeT Node; //为了迭代器访问私有成员 //友元类 templateclass K,class T,class Ptr,class Ref ,class KeyOft,class Num friend struct HashIterator; public: //迭代器 typedef typename HashIteratorK, T,T*,T ,KeyOft, Num Iterator; typedef typename HashIteratorK, 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: vectorNode* _table;//哈希数据 size_t _n; //元素个数 }; }unordered_setnamespace HashBucket { templateclass K class unordered_set { //仿函数转换为key struct SetKey { const K operator()(const K key)const { return key; } }; public: //迭代器(这里记得要提示编译器不能把这里的类型当成静态成员/成员变量了) typedef typename HashTableK, const K, SetKey, KeyNumK::Iterator iterator; typedef typename HashTableK,const K, SetKey, KeyNumK::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: HashTableK,const K, SetKey, KeyNumK _ht; }; }unordered_mapnamespace HashBucket { templateclass K,class V class unordered_map { //仿函数转换为key struct MapKey { const K operator()(const pairconst K,V kv)const { return kv.first; } }; public: //迭代器 typedef typename HashTableK, pairconst K, V, MapKey, KeyNumK::Iterator iterator; typedef typename HashTableK, pairconst K, V, MapKey, KeyNumK::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: HashTableK, pairconst K, V, MapKey,KeyNumK _ht; }; }这里需要注意的是类型一定要匹配不然会出现很多类型转换不对的情况特别是迭代器那边写的时候必须重视传的模板是否一致还有一个细节就是在两个类都依赖对方的时候这就需要声明然后这里迭代器的使用又需要后面定义哈希桶的私有成员这里也需要友元类既能泛型迭代器还能访问私有成员。查询unordered_setunordered_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_setnamespace HashBucket { templateclass 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: HashTableK,const K, SetKey, KeyNumK _ht; }; }unordered_mapnamespace HashBucket { templateclass K,class V class unordered_map { //仿函数转换为key struct MapKey { const K operator()(const pairconst K,V kv)const { return kv.first; } }; //删除 bool erase(const K key) { return _ht.Erase(key); } private: HashTableK, pairconst K, V, MapKey,KeyNumK _ht; }; }unordered_map的[]访问namespace HashBucket { templateclass K,class V class unordered_map { //仿函数转换为key struct MapKey { const K operator()(const pairconst K,V kv)const { return kv.first; } }; public: //迭代器 typedef typename HashTableK, pairconst K, V, MapKey, KeyNumK::Iterator iterator; typedef typename HashTableK, pairconst K, V, MapKey, KeyNumK::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: //插入 pairiterator,bool insert(const pairconst K, V kv) { return _ht.Insert(kv); } //[]访问 V operator[](const K key) { return (_ht.Insert({key,V()}).first)-/*这里会调用迭代器实现的-*/second; } private: HashTableK, pairconst K, V, MapKey,KeyNumK _ht; }; }完整代码修改一部分HashTable.h#pragma once #includeiostream #includevector using namespace std; //连地址法 namespace HashBucket { //将key转换为数字 templateclass K struct KeyNum { size_t operator()(const K key)const { return (size_t)key; } }; //全特化 template struct KeyNumstring { size_t operator()(const string key)const { int hash 0; for (auto e : key) { hash e; hash * 131; } return hash; } }; templateclass T struct HashNode { T _data; HashNodeT* _next; //初始化 HashNode(T data) :_data(data) ,_next(nullptr) { } }; //迭代器 //当需要的类定义比需要的类要迟的就需要前置声明 templateclass K, class T, class KeyOft, class Num class HashTable; templateclass K,class T,class Ptr,class Ref,class KeyOft,class Num struct HashIterator { typedef HashNodeT Node; typedef HashTableK, T, KeyOft, Num Hash; typedef HashIteratorK, 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; //用于迭代器不参与影响哈希桶只是利用哈希桶来支持双选迭代器 }; templateclass K,class T, class KeyOft/*将Tkey/pairkey,value转换为key*/,class Num KeyNumK/*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 HashNodeT Node; //为了迭代器访问私有成员 //友元类 templateclass K,class T,class Ptr,class Ref ,class KeyOft,class Num friend struct HashIterator; public: //迭代器 typedef typename HashIteratorK, T,T*,T ,KeyOft, Num Iterator; typedef typename HashIteratorK, 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; } } //插入 pairIterator,bool Insert(const T data) { Num num; KeyOft keyoft; if (Find(keyoft(data)) ! End()) return { {nullptr,this},false }; //空间不够扩容 if (_n _table.size()) { vectorNode* 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: vectorNode* _table;//哈希数据 size_t _n; //元素个数 }; }unoredered_set.h#pragma once #includeHashTable.h namespace HashBucket { templateclass K class unordered_set { //仿函数转换为key struct SetKey { const K operator()(const K key)const { return key; } }; public: //迭代器(这里记得要提示编译器不能把这里的类型当成静态成员/成员变量了) typedef typename HashTableK,const K, SetKey, KeyNumK::Iterator iterator; typedef typename HashTableK,const K, SetKey, KeyNumK::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: //插入 pairiterator,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: HashTableK,const K, SetKey, KeyNumK _ht; }; }unoredered_map.h#pragma once #includeHashTable.h namespace HashBucket { templateclass K,class V class unordered_map { //仿函数转换为key struct MapKey { const K operator()(const pairconst K,V kv)const { return kv.first; } }; public: //迭代器 typedef typename HashTableK, pairconst K, V, MapKey, KeyNumK::Iterator iterator; typedef typename HashTableK, pairconst K, V, MapKey, KeyNumK::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: //插入 pairiterator,bool insert(const pairconst 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: HashTableK, pairconst K, V, MapKey,KeyNumK _ht; }; }

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

更多相关文章

使用Flask在本地调用树莓派摄像头

ok-ww 鸣潮自动战斗与一键日常使用指南：10 分钟跑通

基于Springboot旅游景点订票系统【附源码+文档】

Swisslog分拆战略解析：百年工业巨头的转型之路

2026年主流AI API技术特性与调用优化指南

大模型应用开发：2026年程序员高薪技术栈解析

大数据特征工程实战：核心技术与应用场景解析

GPU显存优化：Unified Memory与Tensor Offloading技术解析

SylixOS驱动开发实战：从模块加载到LCD点亮的完整链路

全国计算机二级C语言真题PDF高效刷题指南

requests+BeautifulSoup：爬虫抓取h1标题的入门实战指南

递推最小二乘参数辨识MATLAB编程：二阶系统与渐消记忆实现

Python股票自动交易系统源码解析：从行情获取到风控的完整链路

视酷酷信IM源码部署指南：Java 17+MySQL 8.0.33实战配置

Python爬取百度迁徙数据：接口解析、批量采集与避坑指南

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

还想了解更多？直接咨询顾问