双重散列并非最稳：Robin Hood 未命中探测反超它、线性探测暴涨 5.4 倍的高负载实测复盘

如果你背过《算法导论》里开放寻址那节，一定记得一句话的潜台词：线性探测有「一次聚集」、二次探测要控制负载、双重散列最抗聚集所以最稳。我照着这个共识写了十年代码，直到上周把一个缓存索引表的负载因子从 0.7 调到 0.9，未命中率没变，P99 延迟却翻了一倍。问题出在哪？我用一个 5 万键的 Node 基准，把 linear / double-hashing / Robin-Hood 三条探测链在 α=0.5/0.7/0.9 下拆开量了一遍——结果和教科书说的，差得有点远。

背景：为什么「开放寻址选型」值得专门测

哈希表是后端、前端、数据库里最底层的零件之一。链式（chaining）在 JS/Python 里常见，但 C++ 的 absl::flat_hash_map、Rust 的 hashbrown、Go 的 map 底层走的都是开放寻址（open addressing）——把键值连续铺在一块数组里，冲突了就顺着「探测链」往下找。

开放寻址里最常被拿来比的三种策略是：

• 线性探测（linear probing）：冲突了就 i+1, i+2… 顺序找下一个空槽。缓存最友好，但有「一次聚集」——一串被占的槽会越拖越长。
• 双重散列（double hashing）：用第二个哈希算一个步长 step，i, i+step, i+2step… 跳着找。理论上聚集最少，代价是每次要多算一次哈希、探测链在内存里不连续。
• Robin Hood 哈希：插入时按「探测距离」让后来者插队，让整张表的距离分布变平；查找未命中时可以提前终止。

教科书给的共识是：双重散列最抗聚集 → 综合表现最好；线性探测简单但高负载会退化；Robin Hood 是进阶优化。但「抗聚集」和「真的更快」之间，隔着缓存局部性、未命中路径、删除 Tombstone 这些工程现实。下面用实测把这三者的边界钉死。

解剖：三条探测链到底怎么走

三种策略的插入和查找，差异全在「下一个槽位怎么选」。下面这张图把同一次插入冲突后的探测路径画了出来。

图1：同一组冲突键下，三条探测链的走向。线性探测连续（缓存友好但易拖成长串），双重散列跳跃（分散但内存跳跃），Robin Hood 在插入时按探测距离换位移位（绿色为被插队的原占用者）。

核心代码其实很短。线性探测就是 while(occupied) i=(i+1)%m；双重散列把 +1 换成 +step，step = 1 + (h2(k) % (m-1))（质数表长保证步长与表长互质，探测链必然遍历全表）；Robin Hood 在插入时比较「当前键的探测距离」和「槽内原键的探测距离」，谁离自己的 home 更远谁留下，被挤走的键继续往后走。

这里有一个容易踩的坑：用 Int32Array 存无符号键值会被当成有符号数，一旦键值 ≥ 2³¹，读取回来是负数，slots[i] !== k 永远不成立，查找会一路探到表尾——我前几版基准就卡在这，未命中探测直接跑出 N×m 量级。正确做法是用独立的 used 占用位数组判空，比较键值时统一 >>> 0 还原。

实证一：探测长度随负载因子的拐点

我在 Node 22 上用 5 万键、质数表长、均匀分布的 32 位键，分别测了「命中平均探测长度」和「未命中平均探测长度」（未命中键保证不在表中）。三次复现稳定，下表是均值：

先把「命中」和「未命中」分开看，因为它们的命运完全不同。命中探测长度三种策略差距不大（线性=Robin Hood，因为命中探针长度就是「离 home 的距离」，Robin Hood 不缩短命中距离）；真正分胜负的是未命中——也就是「这个键不在表里，要探多少次才确认空槽」。

实证二：高负载下谁先崩

把未命中探测随 α 的变化画成曲线，线性探测的那条线几乎是指数起飞：

图2：未命中探测长度 vs 负载因子。线性探测在 α=0.7 后陡升，α=0.9 时达到 48.2 次；双重散列和 Robin Hood 全程平缓。

具体数字更刺眼：

• 线性探测的未命中探测从 α=0.5 的 1.505，涨到 α=0.9 的 48.156，放大 32 倍。
• 同一区间，双重散列只涨 8.9 倍（1.002→8.917），Robin Hood 涨 6.5 倍（0.756→4.891）。
• 到 α=0.9，线性探测的未命中探测是双重散列的 5.4 倍、是 Robin Hood 的 9.8 倍。

这正好解释了开头那个缓存索引表的事故：表越满，一次「查不到」要顺着长串空槽一路探，长串越长越容易跨缓存行，P99 就爆了。而且这还不是最坏情况——2026 年 Sean Carroll 在聚集分布下的实测里，线性探测的最差未命中探测达到了 23,425 次（N=65536，负载 0.75）。Robin Hood 之所以能在 α=0.9 把未命中压到 4.89，靠的是它的「早停」：未命中查找时只要遇到一个探测距离比自己当前距离更小的槽，就可以断定键不存在、立刻收手；而双重散列的未命中必须一路探到真正的空槽，于是会更多次穿过被占的长串。

实证三：探测最少，不等于最快

到这里，教科书共识被拆成两半：双重散列确实在「命中探测」上最少（0.383/0.725/1.572 全程最佳），但在「未命中探测」上，Robin Hood 反超了它（0.756/1.507/4.891 vs 1.002/2.345/8.917）——也就是说「双重散列最抗聚集」这句话，在 misses 这个维度上并不成立。

那「探测少 = 快」成立吗？我的粗粒度插入吞吐（单次构建、5 万键，单位 ns/op，单 run 仅供参考）给出了另一个反转：

• α=0.9 时，双重散列插入 40ns，线性探测 60ns，Robin Hood 100ns。

双重散列因为探针少，插入反而最快；Robin Hood 因为插入时要反复比较和换位移位，最慢。所以「探测次数」和「墙钟时间」会反向——这一点在 2026 年那篇用 Set Shaping Theory 加速哈希表查找的论文里也有印证：在负载 0.95 的读多场景里，线性探测靠顺序访问的缓存局部性，总加速比（2.20×）甚至高过 Robin Hood（2.15×）和双重散列（0.63×）。换句话说，「谁最快」完全取决于你的工作负载是插入多还是查找多、是命中多还是未命中多。没有一种策略在所有维度通吃。

局限：我的基准覆盖了什么、没覆盖什么

诚实交代边界，免得被当成万能结论：

• 只测了均匀随机键 + 高质量哈希。一旦哈希质量差、或键本身聚集（比如顺序 ID 没打散），线性探测的未命中会崩得更狠——Carroll 的 23425 次最坏情况就是聚集分布下的结果，我没有复现聚集分布，只引用了他的数据。
• 没测删除 / Tombstone：开放寻址删键要打墓碑，墓碑会污染未命中探测链，线性探测受创最重，这部分我留给下一篇。
• 墙钟数字是单次粗测，目的是看量级与排序，不是给生产下精确结论；要定罪还得上 JMH / perf 那一套。
• 表长取了质数（双重散列互质保证），工程里更多用 2 的幂 + SIMD 元数据（SwissTable），探测链行为会不同。

结论与下一步

一条可带走的方法论：开放寻址选型不要背共识，要按「负载因子 × 工作负载（命中/未命中比）× 哈希质量」三维来选。 我的实测给的结论是——默认高负载 + 读多：优先 Robin Hood 或 SwissTable 类（未命中稳）；哈希质量没把握、键可能聚集：远离纯线性探测；追求极致插入吞吐且哈希靠谱：双重散列；而「双重散列最稳」只对命中路径成立，对未命中路径，Robin Hood 才是那个把探测长度压到 4.89 的赢家。

开源地址

• 矩阵门户：GitHub – wangzifan396-wzf/WB: nano-tools: 400+ single-file, zero-dependency, local-first web utilities in one portal. Offline and private, nothing leaves your browser. Binary & protocol parsers, crypto, dev, audio, visualization, productivity. · GitHub
• 单文件工具聚合器：GitHub – wangzifan396-wzf/nano-workbench: Single-file tabbed launcher for the nano-tools matrix – one tab, all 28 tools, instant switch. Zero-dep. Part of nano-tools. · GitHub
• GitHub 组织主页：wangzifan396-wzf (WangZi) · GitHub