Cuckoo Hashing

每个键像一条连接两个候选槽的边，选择存储位置就是把这条边定向到一个端点。踢出链沿着当前定向寻找可改道的路径；若某个分量的边比槽还多，无论从哪一键开始踢都不可能成功，循环只是容量障碍在执行过程中的表现。

踢出路径例子 ​

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

概率与装载边界 ​

原论文期刊版的期望摊还 $O(1)$ 更新界选取如下条件：键占一个 RAM 字，输入操作序列与算法的随机选择独立；固定 $\epsilon >0$，维持每张表容量 $r\ge (1+\epsilon )n$，并以几何扩缩容保持线性空间。两个函数独立抽取且可在常数时间求值。对充分大的规模，插入最多执行 $\mathrm{MaxLoop}=\lceil 3{\log }_{1+\epsilon }r\rceil$ 轮，每轮依次尝试两张表；自上次重哈希开始累计至多 $r^2$ 次插入后，还要主动重哈希。常数规模单独处理。

该分析使用的哈希族构造，在任意固定的至多 $r^2$ 个相关键上，以 $1-O(n^{-2})$ 的概率提供 $n^{\delta }$ 阶独立均匀输出，其中 $\delta >0$ 为固定常数；构造失败事件另计入时间分析。充分大时 $\mathrm{MaxLoop}<n^{\delta }$，足以分析一次受限踢出过程涉及的键。这个构造条件与定期换函数共同限定了同一哈希对服务的键集；普通通用碰撞界只控制键对，不能替代它。

这里总装载率是 $n/(2r)<1/2$。桶化 cuckoo、更多候选和 stash 有各自的阈值与查询契约。查询的常数最坏界针对已经构造好的顺序表；Las Vegas 重建通过重试保持结果正确，运行时间随机。

候选位置由随机哈希函数决定，插入失败概率和重哈希次数因此属于随机化算法理路随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。分析。查询的常数探测是条件性的：它依赖当前表已经成功构造，并不消除构造阶段的随机失败事件。

Rehash 的摊还语义 ​

达到踢出阈值或本轮哈希对的 $r^2$ 次插入上限时，都给全部现存键及尚未安置的键换一对函数，重置本轮计数并重新构建；重建中的插入也从这次重建开始计数，失败则重新开始。原论文在上述条件下证明，普通踢出过程的期望长度为 $O(1+1/\epsilon )$，一次插入因超限而触发重建的概率为 $O(n^{-2})$，一次完整重建的期望成本为 $O(n)$。

失败触发的额外期望成本因此为 $O(1/n)$；定期重哈希的成本分摊到该轮插入，同样为 $O(1/n)$。几何扩缩容再单独摊还，得到期望摊还常数更新。主动重哈希所在的那一次操作仍可能花费线性时间，故这项保证是对操作序列的成本记账。

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

失败分量怎样被识别 ​

设第一张表的槽为 $a_1,a_2$，第二张表的槽为 $b_1,b_2$。四个不同键的候选边为 $(a_1,b_1)$、$(a_2,b_1)$、$(a_2,b_2)$、$(a_1,b_2)$，构成一个四环，可依次把四条边放在 $a_1,b_1,a_2,b_2$。再加入第五个键，其候选仍为 $(a_1,b_1)$，就得到允许平行边的二分图分量：5 条边争用 4 个槽，任何放置都必然失败。两表模型不会出现三角形；不同键拥有同一对候选则完全可能。

实现可按以下顺序处理：

1. 限制一次踢出的最大步数，并记录本轮访问状态；
2. 超限后把新键和被踢出的键一起保留在临时区，不能丢失；
3. 抽取新哈希函数，从空表重插全部键；
4. 若仍失败则重试，达到负载阈值时先扩容；即使一直成功，也在同一哈希对累计 $r^2$ 次插入后主动重哈希。

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