【C++指南】哈希驱动的封装：如何让unordered_map/set飞得更快更稳？【上】

Ne0inhk

— 16 min read
【C++指南】哈希驱动的封装：如何让unordered_map/set飞得更快更稳？【上】


🌟 各位看官好，我是egoist2023！

🌍 种一棵树最好是十年前，其次是现在！

💬 注意：本文在哈希函数中主讲除法散列法，乘法散列法、全域散列法、双重散列等自行了解。

🚀 今天来学习哈希表的相关知识，为之后unordered_map/set的封装打下基础。

👍 如果觉得这篇文章有帮助，欢迎您一键三连，分享给更多人哦

引入 ：直接定址法

在现实生活中，我们往往会将一类东西跟另一种东西进行绑定，且这种关系具有一定的联系。在计算机当中也是必然，如“left”的中文意思是“左边”，“string”的中文意思是“字符串”等等。而对于每个数字都有对应存储的下标。当关键字的范围⽐较集中时，⽐如⼀组关键字都在[0,99]之间，那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。但是如果一组关键字比较分散，如只出现了1、20、99时，此时要开100空间的数组有97个空间会被浪费，这显然不是我们期望的。因此，关于一段哈希的故事就此展开。

哈希

哈希(hash)又称散列，是⼀种组织数据的⽅式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找。

哈希函数

⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到。因此我们要尽量往这个⽅向去考量设计。

除法散列法（除留余数法）

当数据比较分散的情况下，用直接定址法是无法很好地处理问题的，那是否能仅用较小地空间让保证所有的值都映射到该空间上来呢(保证空间大于值数量)？于是有人提出了除法散列法的概念并对此进行了说明。

除法散列法也叫做除留余数法，假设哈希表的大小为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。（这样即能保证所有的值都在这个空间上）

哈希冲突和负载因子

当使⽤除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等。如果是 ，那么key %2 ^X 本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了。如：{63 , 31}看起来没有关联的值，如果M是16，即2^4，保留后4位，因为63的⼆进制后8位是 00111111，31的⼆进制后8位是 00011111，后四位都是相同的，那么都会映射到同一个空间上去，这样就产生了冲突，即哈希冲突。因此当使⽤除法散列法时，建议M取不太接近2的整数次幂的⼀个质数(素数)。负载因子：假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，M一定要大于，那么负载因子 = N/M，保证负载因子小于1。负载因⼦越⼤，说明M是接近于N的，则空间利⽤率越⾼，相对地哈希冲突的概率越⾼；负载因⼦越⼩，说明M的空间很大，则空间利用率低，相对地哈希冲突的概率越低。

处理哈希冲突

实践中哈希表⼀般还是选择除法散列法作为哈希函数，当然哈希表⽆论选择什么哈希函数也避免不了冲突，那么插⼊数据时，如何解决冲突呢？主要有两种两种⽅法，开放定址法和链地址法。

开放定址法

在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种：线性探测、⼆次探测、双重探测（自行了解）。（哈希表有三种状态表示：存在、空、删除）开放定址法的哈希表结构

enum Status { EMPTY, EXIST, DELETE }; template<class K, class V> struct HashData { pair<K, V> _kv; Status _status = EMPTY; }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: HashTable(size_t size = 11) :_tables(size) , _n(0) {} //... private: vector<HashData<K, V>> _tables; size_t _n; };
优化

但是上面的实现并不是那么好，如果当映射的元素_n/_tables.size()大于负载因子时，显然是需要扩容的，如果选择2倍扩容，原本的11空间变为22空间，看似没有毛病。但前面我们说过，使用除法散列法时，要尽量避免M为某些值，即取不太接近2的整数次幂的⼀个质数。因此，不能直接地选择2倍扩容地方式来放大空间。那代码又该如何实现呢？

  1. 提前造好一些数据，这些数据得保证是质数，且是不太接近2的整数次幂的⼀个质数；
  2. 每次扩容的时候都往我们造好的数据上进行扩容。
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; } enum Status { EMPTY, EXIST, DELETE }; template<class K, class V> struct HashData { pair<K, V> _kv; Status _status = EMPTY; }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: HashTable(size_t size = __stl_num_primes) :_tables(size) , _n(0) {} //... private: vector<HashData<K, V>> _tables; size_t _n; };

在上面这段程序中，哈希表默认初始空间是28，当大于负载因子时进行扩容，第一次扩容是53，第二次是97…… ，可以发现，每次扩容都是以近乎2倍扩容且满足不太接近2的整数次幂的⼀个质数。这种手动造数据的方法看似笨拙，实则这难道不是利用其特性下的一种取巧吗？

线性探测
  • 在映射数据的时候可能会存在哈希冲突，此时从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛到哈希表尾，则回绕到哈希表头的位置。
  • h(key) = hash0 = key % M，hash0位置冲突了，则线性探测公式为：hc(key,i) = hashi = (hash0 + i) % M， i = {1, 2, 3, ..., M − 1}，保证线性探测时能从队尾走到队头，且因为负载因⼦小于1，则最多探测M-1次，⼀定能找到⼀个存储key的位置。
  • 可以发现线性探测的问题会占用其他值可能映射到的空间，会导致原本不冲突的值产生哈希冲突。严重的话肯呢个会使多个hash0，hash1，hash2，hash3的值都争夺hash3位置，这种现象叫做群集/堆积。

二次探测（了解）

存在哈希冲突是必然的，但有什么比较好的方法可以减少哈希冲突的现象呢？

  • 从发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为止，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表尾的位置；
  • h(key) = hash0 = key % M , hash0位置冲突了，则⼆次探测公式为：hc(key,i) = hashi = (hash0 ± i^2 ) % M， i = {1, 2, 3, ...,M/2 }；
  • ⼆次探测当 hashi = (hash0 − i 2 )%M 时，当hashi<0时，需要hashi += M。

线性探测实现

bool Insert(const pair<K, V>& kv) { size_t hash0 = kv.first % _tables.size(); size_t hashi = hash0; size_t i = 1; //如果该点存在 --> 线性探测 while (_tables[hashi]._status == EXIST) { hashi = (hashi + i) % _tables.size(); i++; } _tables[hash0]._kv = kv; _tables[hash0]._status = EXIST; ++_n; return true; }
扩容

方案一：新建一个哈希表，遍历旧表让里面的数据重新映射到新表当中；

方案二：采用复用的手段将旧表数据映射到新表中。

if ((double)_n / (double)_tables.size() > 0.7) { HashTable<K, V, Hash> newHT(__stl_next_prime(_tables.size() + 1)); for (size_t i = 0;i < _tables.size();i++) { if (_tables[i]._status == EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); }
查找和删除
查找规律：巧妙利用线性探测的特性





删除规律：采用Find函数寻找该值是否存在，如果存在标记为del，返回true；否则，返回false。
代码实现
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; } enum Status { EMPTY, EXIST, DELETE }; template<class K, class V> struct HashData { pair<K, V> _kv; Status _status = EMPTY; }; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: HashTable(size_t size = __stl_num_primes) :_tables(size) , _n(0) {} bool Insert(const pair<K, V>& kv) { //扩容 --> 负载因子大于0.7 if ((double)_n / (double)_tables.size() > 0.7) { HashTable<K, V, Hash> newHT(__stl_next_prime(_tables.size() + 1)); for (size_t i = 0;i < _tables.size();i++) { if (_tables[i]._status == EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); } size_t hash0 = kv.first % _tables.size(); size_t hashi = hash0; size_t i = 1; //如果该点存在 --> 线性探测 while (_tables[hashi]._status == EXIST) { hashi = (hashi + i) % _tables.size(); i++; } _tables[hash0]._kv = kv; _tables[hash0]._status = EXIST; ++_n; return true; } HashData<K, V>* Find(const K& key) { size_t hash0 = key % _tables.size(); size_t hash1 = hash0; size_t i = 1; while (_tables[hash1]._status != EMPTY) { if (_tables[hash1]._kv.first == key && _tables[hash1]._status != DELETE) { return &_tables[hash1]; } hash1 = (hash1 + i) % _tables.size(); ++i; } return nullptr; } bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) { ret->_status = DELETE; return true; } else { return false; } } private: vector<HashData<K, V>> _tables; size_t _n; };

链地址法

开放定址法无论怎样势必会造成哈希冲突，因其 占⽤的都是哈希表中的空间，始终存在互相影响问题。那如何解决这种弊端呢？链地址法为了解决这种冲突，不是再将所有的数据直接存储在哈希表中，而是通过指针的方式让每一个值都映射到对应空间，即使产生冲突会用指针的方式将它们悬挂起来，挂在哈希表该位置下面，当然我们形象地称这种方法为拉链法或哈希桶。

但是在一些极端场景下，如有人恶意造出一段数据让它都映射到同一个位置，导致某个桶特别长，查询时间复杂度达到了O(N)。有大佬提出，如果这个桶的长度超过⼀定阀值(8)时就把链表转换成红⿊树。（用全域散列法也可）

链地址法的结构实现

 //手动造数据见上面 template<class K,class V> struct HashNode { pair<K, V> _kv; HashNode<K, V>* _next; HashNode(const pair<K, V>& kv) :_next(nullptr) ,_kv(kv) {} }; template<class K, class V> class HashTable { typedef HashNode<K, V> Node; public: HashTable(size_t size = __stl_next_prime(0)) :_tables(size, nullptr) ,_n(0) {} private: vector<Node*> _tables; size_t _n; };
特殊情况：插入元素不是数字

如果插入元素是浮点数、负数情况呢？

仿函数的作用再次体现出来了，无论是整数、浮点数、负数，统一强转成正数来处理，找到该映射的位置，对查找、删除等操作都不会受到影响，因为我们同样需要将目标值强制转成正数映射到对应位置。

 //仿函数 template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; // --> 针对浮点、负数等情况 } };

针对字符串

但是字符串的处理，并不能直接强转成正数来处理，这并不被允许。因此，在这里采用特化的思想进行特殊处理，实现如下。

 //针对字符串 template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t hash0 = 0; for (auto& ch : key) { //对不同字符串但hash0相同的处理，减少冲突 hash0 *= 131; hash0 += ch; } return hash0; } };
改动
template<class K, class V, class Hash = HashFunc<K>>
扩容

开放定址法负载因⼦必须⼩于1，链地址法的负载因⼦就没有限制了。在stl中的实现最⼤负载因⼦基本控制在1，⼤于1就扩容，我们同样采用此逻辑进行扩容。扩容操作时，开一个新的哈希表，需要将旧表上的值都重新映射到新表中。

  1. 方法一：由于是链地址法的实现，一个位置下可能会挂着多个值（即哈希桶），那么就需要遍历该位置中桶的每个结点，将每个结点的值重新映射到新表中，而每次操作都需要申请新结点，并把旧表中该结点释放掉。显然，这种方式是非常浪费的，且效率非常低效。
  2. 方法二：正是由于采用的是链地址法的实现，由于哈希表中每个位置都是一个指针，那么我们只需要遍历旧表中结点映射在新表中的位置，使其指向旧表中该结点。最后，将旧表置为空，交换新旧链表，完成扩容操作。
 bool Insert(const pair<K, V>& kv) { //不允许冗余 if (Find(kv.first)) return false; Hash hs; //需要扩容 if (_n == _tables.size()) { // 也可以，但是扩容新开辟节点，释放旧节点，有点浪费 /*HashTable<K, V> newHT(__stl_next_prime(_tables.size() + 1)); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { newHT.Insert(cur->_kv); cur = cur->_next; } } _tables.swap(newHT._tables);*/ 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 hash0 = hs(cur->_kv.first) % newtables.size(); cur->_next = newtables[hash0]; newtables[hash0] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); } size_t hash0 = hs(kv.first) % _tables.size(); Node* newnode = new Node(kv); //头插 newnode->_next = _tables[hash0]; _tables[hash0] = newnode; ++_n; return true; }
删除
 bool Erase(const K& key) { Hash hs; size_t hash0 = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hash0]; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) { _tables[hash0] = cur->_next; } else { prev->_next = cur->_next; } --_n; delete cur; return true; } prev = cur; cur = cur->_next; } return false; }
代码实现
 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 K,class V> struct HashNode { pair<K, V> _kv; HashNode<K, V>* _next; HashNode(const pair<K, V>& kv) :_next(nullptr) ,_kv(kv) {} }; //仿函数 template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; // --> 针对浮点、负数等情况 } }; //针对字符串 template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t hash0 = 0; for (auto& ch : key) { //对不同字符串但hash0相同的处理，减少冲突 hash0 *= 131; hash0 += ch; } return hash0; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; public: HashTable(size_t size = __stl_next_prime(0)) :_tables(size, nullptr) ,_n(0) {} bool Insert(const pair<K, V>& kv) { //不允许冗余 if (Find(kv.first)) return false; Hash hs; //需要扩容 if (_n == _tables.size()) { // 也可以，但是扩容新开辟节点，释放旧节点，有点浪费 /*HashTable<K, V> newHT(__stl_next_prime(_tables.size() + 1)); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { newHT.Insert(cur->_kv); cur = cur->_next; } } _tables.swap(newHT._tables);*/ 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 hash0 = hs(cur->_kv.first) % newtables.size(); cur->_next = newtables[hash0]; newtables[hash0] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); } size_t hash0 = hs(kv.first) % _tables.size(); Node* newnode = new Node(kv); //头插 newnode->_next = _tables[hash0]; _tables[hash0] = newnode; ++_n; return true; } Node* Find(const K& key) { Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) return cur; cur = cur->_next; } return nullptr; } bool Erase(const K& key) { Hash hs; size_t hash0 = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hash0]; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) { _tables[hash0] = cur->_next; } else { prev->_next = cur->_next; } --_n; delete cur; return true; } prev = cur; cur = cur->_next; } return false; } ~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; } } private: vector<Node*> _tables; size_t _n; };

Read more

猛裁1.6万人后，网站再崩6小时、一周4次重大事故！官方“紧急复盘”：跟裁员无关，也不是AI写代码的锅

猛裁1.6万人后，网站再崩6小时、一周4次重大事故！官方“紧急复盘”：跟裁员无关，也不是AI写代码的锅

整理 | 郑丽媛 出品 | ZEEKLOG（ID：ZEEKLOGnews） 过去几年里，科技公司几乎都在同一件事上加速：让 AI 参与写代码。 从自动补全、自动生成函数，到直接修改系统配置，生成式 AI 已经逐渐走进真实生产环境。但最近发生在亚马逊的一连串事故，却给整个行业泼了一盆冷水——当 AI 开始真正参与生产环境开发时，事情可能远比想象复杂。 最近，多家媒体披露，本周二亚马逊内部紧急召开了一场工程“深度复盘（deep dive）”会议，专门讨论最近频繁出现的系统故障——其中，一个被反复提及的关键词是：AI 辅助代码。 一周 4 次严重事故，亚马逊内部紧急复盘 事情的起点，是最近一段时间亚马逊系统稳定性明显下降。 负责亚马逊网站技术架构的高级副总裁 Dave Treadwell 在一封内部邮件中坦言：“各位，正如大家可能已经知道的，最近网站及相关基础设施的可用性确实不太理想。” 为此，公司决定把原本每周例行举行的技术会议

By Ne0inhk
这回真的“装”到了！来OpenClaw全国纵深行，你只需要带一台电脑……

这回真的“装”到了！来OpenClaw全国纵深行，你只需要带一台电脑……

AI Agent 的风，已经从 GitHub 吹到了线下。 过去几个月，越来越多开发者开始讨论一个问题： 当 AI 不再只是聊天，而是可以执行任务，软件会变成什么样？ 在这股浪潮中，一个开源项目迅速进入开发者视野——OpenClaw，在 GitHub 上获得大量关注，相关教程、实践案例不断出现。有人用它自动整理资料，有人用它管理开发流程，还有人尝试让它执行复杂的工作流。 很多开发者第一次意识到： AI 不只是工具，它可能成为“执行者”。 不过，在技术社区之外，大多数人对 Agent 的理解仍停留在概念层面。 * AI Agent 到底是什么？ * 如何在自己的电脑上运行？ * 普通开发者能否真正用起来？ 带着这些问题，一场围绕 OpenClaw 的开发者城市行动正在展开。 ZEEKLOG 发起的OpenClaw 全国纵深行将走进 20 个城市，用最直接的方式回答一个问题——如果

By Ne0inhk
字节辟谣「武汉全员被裁」：超2000人base武汉；315曝光给AI大模型“投毒”已成产业链；腾讯正式成为OpenClaw赞助商 | 极客头条

字节辟谣「武汉全员被裁」：超2000人base武汉；315曝光给AI大模型“投毒”已成产业链；腾讯正式成为OpenClaw赞助商 | 极客头条

「极客头条」—— 技术人员的新闻圈！ ZEEKLOG 的读者朋友们好，「极客头条」来啦，快来看今天都有哪些值得我们技术人关注的重要新闻吧。（投稿或寻求报道：[email protected]） 整理 | 苏宓 出品 | ZEEKLOG（ID：ZEEKLOGnews） 一分钟速览新闻点！ * 腾讯正式成为 OpenClaw 赞助商 * 字节辟谣「武汉全员被裁」：超 2000 人 base 武汉，将加大对湖北投入 * 2026 北京亦庄人形机器人半马完成首场练习测试 * 美团 CEO 王兴：我们都应该努力“减少登味”，内部不要再叫我“兴哥” * 向 AI 投毒已成产业链！315 晚会曝光 GEO 技术：虚构产品都能成 AI 标准答案 * 雷军官宣：新一代小米

By Ne0inhk
只因一个高级词，作文被判“18% AI生成”！AI检测「荒诞现状」：写得太好=AI作弊，学生被逼“降智”写作

只因一个高级词，作文被判“18% AI生成”！AI检测「荒诞现状」：写得太好=AI作弊，学生被逼“降智”写作

【ZEEKLOG 编者按】当生成式 AI 迅速进入校园，许多学校的第一反应是部署各种“AI 检测工具”，试图用技术手段识别学生是否在作业中使用了 AI。然而，这种看似合理的做法，正在产生一些出乎意料的副作用：学生因为用词稍微“高级”一点就被判定为“AI生成”，优秀写作反而变成一种风险；为了避免被误判，一些原本不使用 AI 的学生开始主动学习和使用 AI 工具，只为“自证清白”。 原文链接：https://www.techdirt.com/2026/03/06/were-training-students-to-write-worse-to-prove-theyre-not-robots-and-its-pushing-them-to-use-more-ai/ 作者 | Mike Masnick      编译 | 郑丽媛 出品 | ZEEKLOG（ID：ZEEKLOGnews）  大约一年半前，我写过一件发生在我孩子身上的事。 当时学校给每个学生发了一台 Chromebook，上面预装了一款 AI

By Ne0inhk