Cuckoo Hashing

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

踢出路径例子 ​

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

概率与装载边界 ​

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

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

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；若后台增量重建，查询需同时检查新旧表，不能继续声称接口完全未变。