手写 unordered_map：从拉链法到 rehash，彻底搞懂哈希表为什么快

先回答标题里的问题unordered_set 和 unordered_map 快不是编译器开了什么黑科技而是它们踩中了计算机最擅长的一步操作——数组下标访问。给定一个键先把它哈希成一个数字再用这个数字到桶数组里取一条链表最后在这条链表上做一两次比较。整个过程平均下来是常数时间和数据量基本无关。这个结论光背下来没用。为了彻底搞懂它我决定不用标准库从空文件开始用连地址法也叫拉链法自己手写了一个 unordered_map桶数组自己分配节点自己 new/delete负载因子自己控制扩容自己写。写完之后再回头看 std::unordered_map 的设计很多以前靠死记的东西就通了——为什么它有 bucket_count为什么 max_load_factor 默认是 1.0为什么 rehash 之后迭代器全失效以及最重要的它凭什么在百万级数据下还能保持个位数的比较次数。1. 哈希表为什么快一次取模、一条短链表1.1 从图书馆的索书号说起如果你在图书馆要找一本《C Primer》管理员不会从入口开始一本一本扫过去也不会用二分法在书架上较劲。他直接看索书号走到对应架位最多再在相邻几本书里翻一下。哈希表就是这个思路。数组有个铁律arr[i] 的访问是 O(1) 的因为地址等于基地址加 i 乘元素大小一次乘法和一次加法搞定。哈希表想的是能不能把任意键也换算成一个下标。能这个换算函数就是哈希函数。键进来算出哈希值再对桶数取模得到一个桶下标。整个寻址过程没有任何比较这是它快的第一层原因。但这里有个本质矛盾键空间几乎是无限的桶数组却是有限的所以必然有多个键落到同一个桶。连地址法的处理很朴素每个桶不是一个槽位而是一条链表的头指针冲突的键都链在这条链表上。这也是连地址法或者拉链法这个名字的由来——一个桶后面挂着一串节点像拉链一样。1.2 平均链长为什么链没有拖垮速度看到链表很多人第一反应是链表查询是 O(n)那哈希表不一样嘛。这里的关键在于链表的长度。假设桶数量为 b元素个数为 n定义负载因子 λ n / b。如果哈希函数足够均匀那么每条链的平均长度就是 λ。查找一个存在的键时哈希函数先把你送到正确的桶然后沿着这条链表逐个比较键平均比较次数大约在 1 λ/2 左右查找一个不存在的键平均比较次数约等于 λ。标准库把 max_load_factor 默认设为 1.0意思是元素个数一旦超过桶数就扩容。所以绝大多数时间里平均链长不超过 1也就是说你要找的那个键平均只需要跟链上第一个或第二个节点比一次就命中。这才是为什么这么快的完整答案。不是没有比较而是平均常数次比较。一百万条数据对应一百万个桶链长被摁死在个位数查找当然快。1.3 和红黑树对比log n 和 1 的差距数据规模 nstd::map 查找比较次数约 log2 nunordered 系平均比较次数λ≈11,00010121,000,0002012100,000,0002712std::map 底层是红黑树每次查找要走树高那么多次比较百万数据就是 20 次左右哈希表是算一次哈希、取一次模、比一两次键。数据量越大这个差距越明显。不过哈希表一定比树快是个误区。哈希函数本身有成本整数键还好字符串键要遍历整个串才能算出哈希而且每次扩容还要把所有字符串重新哈希一遍。如果元素只有几十个红黑树那几次比较可能反而比一次字符串哈希加一次内存访问更便宜。所以工程上的数据量小用线性扫描中等用 map量大且无序用 unordered是有道理的。2. 连地址法设计拆解桶数组、哈希节点、质数桶数量2.1 为什么选连地址法而不是开放定址法解决哈希冲突有两大家族开放定址法线性探测、二次探测、双重哈希和连地址法。标准库的 libstdc 和 libc 都选了连地址法主要原因有三点。第一删除简单。开放定址法删除一个元素后探测链会断必须用墓碑标记把槽位空出来时间一长垃圾堆积查询会越来越慢。连地址法删除就是摘链没有任何残留问题。第二负载因子容忍度高。开放定址法负载因子超过 0.7 性能就开始崩连地址法到 1.0、1.5 都还能用实现者不用把扩容阈值卡得很死。第三扩容方便。哈希表扩容时要重新分配桶数组连地址法只需要把节点重新挂到新桶上节点本身不动开放定址法则要把所有数据整体搬一遍。连地址法也有代价节点分散在堆上遍历时缓存不友好。Go 的 map 用的其实是一种桶数组 溢出链表的混合结构本质目的就是把多个键值对塞进连续内存来提升缓存命中率。这个细节我们后面再提手写阶段先用最经典的连地址法把原理打通。2.2 核心数据结构Node 和桶数组先看最核心的类型定义template typename Key, typename T class MyUnorderedMap { private: struct Node { Key key; T value; Node* next; Node(const Key k, const T v) : key(k), value(v), next(nullptr) {} }; Node** buckets_ nullptr; // 桶数组每个元素是一条链表的头指针 size_t bucket_count_ 0; // 桶数量 size_t size_ 0; // 元素个数 float max_load_factor_ 1.0f; // 负载因子上限 size_t hash(const Key key) const { return std::hashKey{}(key); } size_t bucket_index(const Key key) const { return hash(key) % bucket_count_; } // ... 后续操作 };注意 Node 里没有槽位是否被占的标志。连地址法的桶数组每个元素只是头指针空桶就是 nullptr不存在开放定址法那种数组里有个空槽位的概念。这个差异会一路影响你对哈希表的理解连地址法里哈希表的内存主要由节点构成桶数组本身只是存放若干个头指针。这个实现为了聚焦哈希逻辑刻意省略了拷贝构造、移动构造和迭代器。真实项目里要么 delete 掉拷贝要么完整实现否则析构时对同一块内存 delete 两次会直接崩。2.3 哈希函数与质数桶取模的隐藏陷阱std::hash 对常见类型都有现成的特化。比如 libstdc 里 std::hash 就是把整数原样返回真正的随机化发生在取模这一步index hash % bucket_count。为什么不直接用 hash 值当下标因为哈希函数的输出范围通常远大于桶数组大小。32 位整数的哈希值可以到四十多亿你不可能开四十多亿个桶取模把哈希值压进 [0, bucket_count) 区间这一步不可少。那为什么标准库要把桶数量选成质数而不是简单翻倍变成 2 的幂因为取模对低比特位敏感。假如桶数是 16键 0、16、32、48 算出来的下标全是 0如果实际键值正好是 16 的倍数所有元素都会挤进 0 号桶哈希表直接退化成一条大链表。质数桶没有这个毛病16 的倍数对 17 取模结果是 0、16、15、14……摊开了。libstdc 内部维护了一个质数序列扩容时取序列里下一个质数。我的手写版偷懒用了 bucket_count * 2 1至少保证桶数永远是奇数。如果你要完全复刻标准库的行为建议自己维护一张质数表或者直接用大于等于新容量的最小质数。3. 手写实现插入、查找、删除、扩容的完整链路3.1 插入先查重再头插哈希表的插入不是直接塞进去。如果键已经存在operator[] 应该返回已有值的引用而不是再插一个节点否则重复键会越插越多。所以正确顺序是先 find_node 查重不存在才 new 节点然后头插进对应桶。T operator[](const Key key) { if (bucket_count_ 0) rehash(2); // 首次使用先给 2 个桶 if (Node* node find_node(key)) { return node-value; // 键已存在直接返回引用 } if (static_castfloat(size_ 1) bucket_count_ * max_load_factor_) { rehash(bucket_count_ * 2 1); // 超负载因子先扩容 } size_t idx bucket_index(key); Node* n new Node(key, T()); n-next buckets_[idx]; // 头插 buckets_[idx] n; size_; return n-value; }头插不是随便选的。它 O(1) 不需要遍历到链表尾部同时新插入的键通常很快会被再次访问放在头部可以少走几步。把整条链想象成最近访问的往前放头插天然符合这个规律。注意扩容检查用的是 size_ 1不是 size_。因为马上要往里塞一个元素必须按插入后的负载因子判断否则会出现插入前刚好没超插入后超了的边界问题。3.2 查找一条链上的线性扫描Node* find_node(const Key key) const { if (bucket_count_ 0) return nullptr; // 还没分配过桶 Node* cur buckets_[bucket_index(key)]; while (cur) { if (cur-key key) return cur; cur cur-next; } return nullptr; }这里唯一需要解释的是 while 循环里的比较。哈希函数只负责把你送到正确的桶但一个桶里可能有多个键所以必须沿着链表逐个比较键。这个比较次数就是前面说的 1 λ/2 的来源。unordered_set 和 unordered_map 的查找逻辑一模一样只是一个只存键一个存键值对。所以你理解了 map 的 find就等于理解了 set 的 find这是两个容器共享的最核心机制。对外我还提供了两个薄封装T* find(const Key key) { Node* node find_node(key); return node ? node-value : nullptr; } bool count(const Key key) const { return find_node(key) ! nullptr; }返回指针而不是引用好处是找不到时可以直接返回 nullptr调用方不用靠异常或哨兵值判断。3.3 删除指着指针的指针单向链表删除有个经典痛点删头节点和删中间节点要写两套逻辑因为你要改的是前一个节点的 next而头节点没有前一个。标准解法是使用 Node**让它指向桶里存放头指针的那个位置删除时统一改 *cur 就行。bool erase(const Key key) { if (bucket_count_ 0) return false; Node** cur buckets_[bucket_index(key)]; // 指向桶里的头指针 while (*cur) { if ((*cur)-key key) { Node* victim *cur; *cur victim-next; // 前驱的 next 直接指向后继 delete victim; --size_; return true; } cur (*cur)-next; // 前进到下一个节点的 next 字段 } return false; }这套指着指针的指针的思路在标准库源码里也有对应体现只是标准库为了迭代器、节点分配池、异常安全做了一层又一层封装把核心逻辑包裹得看不太清了。手写一遍最大的好处就是把这些包装全部剥掉露出骨架。3.4 rehash搬节点不搬数据当 size_ 1 超过 bucket_count_ * max_load_factor_ 时就要扩容。扩容的本质是换一个更大的桶数组然后把所有已有节点重新算下标、重新挂链。注意重挂的是节点本身不是拷贝键值。这是连地址法扩容舒服的地方——数据不用动动的是链表关系。void rehash(size_t new_count) { if (new_count bucket_count_) return; // 没必要缩容 Node** new_buckets new Node*[new_count](); // 新桶数组全部置空 for (size_t i 0; i bucket_count_; i) { Node* cur buckets_[i]; while (cur) { Node* next cur-next; // 先记住下一个节点 size_t idx hash(cur-key) % new_count; cur-next new_buckets[idx]; // 头插到新桶 new_buckets[idx] cur; cur next; } } delete[] buckets_; buckets_ new_buckets; bucket_count_ new_count; }一个细节重新挂链时原桶里链表的顺序会反转。这不影响正确性但会影响遍历顺序标准库也明确说 rehash 后迭代顺序可能改变。真正要记住的是rehash 之后所有节点的桶下标都变了任何基于旧桶数组的遍历逻辑都必须重新计算。这正是标准库里rehash 后迭代器全部失效的根源。4. 负载因子、reserve 和迭代器失效容易被忽略的决定性细节4.1 负载因子是快慢的第一决定因素负载因子 λ 元素个数 / 桶数量直接决定了平均链长也就决定了查找时的平均比较次数。λ 0.5 时平均比较次数不到 1.2 次λ 1.0平均 1.5 次左右λ 2.0平均 2 次λ 10查找就得扫五六个节点。所以标准库把 max_load_factor 默认设成 1.0不是随手拍的数字而是内存和时间之间的平衡点。λ 太小桶数组空置太多内存浪费λ 太大链表变长哈希表退化成数组加链表的线性结构。调优时如果只想改一个参数就改 max_load_factor。比如你在一个内存宽裕的服务器上做大量读操作可以把它设成 0.5链更短查找更快代价是多一倍桶数组内存。反过来内存紧张、插入为主设成 1.5 也能接受。核心就是记住这个比值控制了链长。4.2 reserve 的正确姿势批量插入前先排好版面哈希表每次扩容都要把全部节点重挂一遍成本 O(n)。虽然均摊下来是 O(1)但如果你知道要插入 100 万条数据仍然建议先调用 reserve 把桶一次性分配到位避免中途触发几十次扩容。std::unordered_map 的 reserve(1000000) 等价于 rehash 到 ceil(1000000 / max_load_factor()) 个桶也就是保证插入 expected 个元素不需要再次扩容。我的手写版也提供了对应的 reservevoid reserve(size_t expected) { if (expected 0) return; size_t need static_castsize_t(expected / max_load_factor_) 1; if (need bucket_count_) rehash(need); }实测下来不 reserve 直接插入 100 万个 key扩容次数在十几次到二十几次之间插入整体耗时能差 30% 以上。特别是字符串 key每次扩容要把全部节点的哈希值重新算一遍代价更明显。批量插入前花一行代码 reserve是性价比最高的优化。提示怀疑哈希表性能退化时第一件事就是打印 load_factor()、bucket_count()再用 bucket_size(i) 看看有没有哪个桶特别长。这个信息比任何 profiling 工具都直接。4.3 rehash 后迭代器全失效但引用和指针不失效这是标准库里让很多人踩过的细节。rehash 之后unordered_map 的所有迭代器都失效但指向元素的引用和指针仍然有效。原因就在 3.4 的实现里rehash 搬的是节点指针节点本身还住在原来的地址所以 value 还能用但迭代器内部要么持有桶位置要么依赖遍历顺序桶数组一换旧迭代器就找不到北了。删除元素时同理erase 只让指向被删元素的迭代器失效其他迭代器不受影响。这两个语义在手写版里完全对得上因为后端就是同一套链表逻辑。常见的翻车现场是这样for (auto kv : m) { if (需要删除(kv.first)) { m.erase(kv.first); // 危险erase 会让当前迭代器失效 } }正确做法是先记录要删的键循环结束后再批量删或者使用基于迭代器的 erase 接口。这个坑不是哈希表特有的但 unordered 系因为 rehash 时全部失效踩起来更疼。5. 实测对比与踩坑记录手写版 vs 标准库5.1 本机实测的量级我用 Release 模式编译器默认 O2在本机跑了一组对比。编译器、内存分配器不同绝对值会有出入但相对量级是稳定的场景单线程、releasestd::mapstd::unordered_map手写连地址法100 万 int 查找命中 100 万次约 150 ms约 25 ms约 30 ms100 万 int 插入含扩容和析构约 180 ms约 60 ms约 80 ms50 万短字符串 key 插入约 350 ms约 200 ms约 240 ms手写版和 std::unordered_map 的差距大约在 10% 到 20%。这个结果其实很鼓舞人说明核心思路对了。剩下的差距基本来自标准库更精细的质数扩容策略、节点分配优化以及一些指令级细节。如果你只是为了理解原理手写版完全够用如果写生产代码请用标准库它把无数边界情况都处理好了。顺带一提如果只插入几百个 key手写版和 std::map 都很快甚至 std::vector 线性扫描更快。不要为了高级而滥用哈希表。5.2 我踩过的三个坑第一个坑是模式化键撞上 2 的幂桶数。我第一次实现时偷懒把桶数按 2 的幂扩结果用一个ID 是 1000 的倍数的测试数据一跑大量元素落在同一个桶里查找从常数时间退化成了线性扫描百万数据直接卡到秒级。救回来的办法是把保留键高位信息的 splitmix64 加到了整数哈希上并把桶数改成奇数uint64_t splitmix64(uint64_t x) { x 0x9e3779b97f4a7c15ULL; x (x ^ (x 30)) * 0xbf58476d1ce4e5b9ULL; x (x ^ (x 27)) * 0x94d049bb133111ebULL; return x ^ (x 31); }第二个坑是忘了 reserve。写测试程序时直接循环插了 100 万条数据刚插到几万条就开始卡。加了 reserve(1000000) 之后整个插入过程只扩容一次时间立刻降下来。这个问题在字符串 key 上尤其明显因为 rehash 要重新计算每个字符串的哈希。第三个坑是自定义类型没有哈希和相等比较。std::unordered_set 直接编译失败报错信息藏在一大堆模板错误里核心是没有可用的哈希函数或 operator。给自定义类型做哈希时不要只把某个字段的地址当哈希值地址的高位变化很小取模后低比特相同照样全挤一个桶。提示如果遇到 unordered 容器性能骤降先用 bucket_size(i) 扫描一遍所有桶。某个桶特别长基本就是哈希分布出了问题所有桶都长那就是负载因子失控了。5.3 什么场景真的该用 unordered 系查找和插入频繁、键数量大且分布均匀unordered_set / unordered_map 是首选平均比较次数保持不变。需要有序遍历、范围查询、lower_bound老老实实用 map / set哈希表天生没有顺序概念。数据量小几百个以内线性容器可能更快也更方便调试。键是 int、string 等已有 std::hash 特化的类型可以放心用 unordered 系。自定义对象作为键先想清楚哈希质量再上。哈希质量差unordered 还不如 map。内存敏感场景unordered 每个节点都有指针和分配开销比 std::map 更费内存这一点要注意。把这段代码写完删掉的时候我最大的收获还不是我会写哈希表了而是终于能看懂那些 benchmark 里为什么 unordered_map 总是一骑绝尘。它的快很朴素一个均匀的哈希函数一个质数桶数组一条平均长度不超过 1 的链表再加上一次及时的扩容。这四个要素缺一个O(1) 就会变成 O(n)。最后留个小练习给这个手写版加上 begin()/end() 迭代器你就必须面对一个麻烦——迭代器持有桶下标rehash 之后怎么保证 it 还能继续走想明白这一步标准库的迭代器失效规则就再也不用背了。