Cuckoo Hashing

两位置不变量 ​

两个来自合适通用哈希族公理库通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。的独立函数给键 $x$ 候选槽 $h_1(x)$ 与 $h_2(x)$。每个键必须存于二者之一，因此查找只检查两处，最坏 $O(1)$。插入把键放入一个候选槽，若占用就踢出旧键，旧键转到自己的另一位置；遇到环或步数阈值后重新选择哈希函数并重建。

Cuckoo 图刻画 ​

把两张表的槽作为二分图顶点，每个键作为连接两个候选槽的边。为每条边选择一个端点存放，且每顶点容量一；经典单槽模型可成功放置，当且仅当每个连通分量的边数不超过顶点数，即分量至多含一个环。树分量沿路径定向即可，双环分量必有某槽承担两键。

踢出路径例子 ​

新键 $x$ 占用 $h_1(x)$ 并踢出 $y$，$y$ 转到 $h_2(y)$ 又踢出 $z$；若 $z$ 的另一槽为空，整条交替路径完成。若路径回到已经出现的状态，继续踢只会循环，必须 rehash，而不是声称插入仍为最坏常数。

概率与装载边界 ​

在低于经典阈值、哈希足够随机时，插入期望摊还常数；接近阈值时复杂分量和长路径概率迅速增加。桶化 cuckoo、更多候选和 stash 改变阈值与查询位置数，须另写模型。查询的常数最坏界不含重建期间的并发语义；Las Vegas 版本通过重试保证结果正确，但运行时间随机。

Rehash 的摊还语义 ​

检测到环后，给当前全部键重新抽一对哈希函数并从空表构建；若仍失败继续重试。只要装载低于相应随机图阈值，单次全表构建成功概率有常数下界，所以重试次数期望常数，重建总成本可向自上次扩容以来的插入摊还。

这个结论要求失败时更换函数，而不是沿同一环从另一个起点继续踢。扩容也改变图顶点数和阈值。若系统要求每次插入最坏延迟，需要增量 rehash、stash 或 deamortization，并重新说明查询要检查哪些旧/新位置。

失败分量怎样被识别 ​

设候选槽为 $a,b,c$，已有键对应边 $(a,b)$、$(b,c)$、$(c,a)$。三条边构成单环，仍可沿环给每条边选不同端点；再插入候选同为 $(a,b)$ 的键后，分量有 4 条边却只有 3 个顶点，容量一放置必然失败。踢出过程反复回到旧状态只是这一图条件的运行时表现。

实现可按以下顺序处理：

1. 限制一次踢出的最大步数，并记录本轮访问状态；
2. 超限后把新键和被踢出的键一起保留在临时区，不能丢失；
3. 抽取新哈希函数，从空表重插全部键；
4. 若仍遇坏分量则重试，达到负载阈值时先扩容。

查找只检查两个槽的最坏 $O(1)$ 与插入的期望摊还 $O(1)$ 是两种不同保证。若加入 stash，查询还必须检查 stash；若后台增量重建，查询需同时检查新旧表，不能继续声称接口完全未变。

参考资料

• Rasmus Pagh, Flemming Friche Rodler, Cuckoo Hashing, Journal of Algorithms, 2004.
• Michael Mitzenmacher, Some Open Questions Related to Cuckoo Hashing, ESA, 2009.