Cuckoo Hashing 是什么？为什么查找可以做到最坏 O(1)？
简化版
Cuckoo Hashing 使用多个哈希函数，一个 key 有多个候选位置。查找时只检查这些固定位置，所以最坏 O(1)。插入时如果位置被占，会踢出旧 key，让旧 key 去自己的另一个候选位置，可能触发连锁搬迁。
详细版
Cuckoo Hashing 的名字来自杜鹃鸟把别的鸟蛋挤出巢。它的核心是“一个元素有几个家”。
- 常见设计用 2 个哈希函数。
- key 只能放在
h1(key)或h2(key)对应位置。 - 查找只查这两个位置。
- 插入时如果都满了，踢出其中一个旧 key。
- 旧 key 再去自己的另一个位置，可能继续踢人。
- 如果出现循环，需要扩容或换哈希函数 rehash。
它用复杂插入换快速查找。
完整版教学
一、为什么普通开放寻址查找可能走很远
普通开放寻址冲突后会沿探测序列找位置。负载高或分布不好时，一个 key 可能需要探测很多槽。
Cuckoo Hashing 换了思路：不允许一个 key 随便走很远，只给它固定几个候选位置。
key A 可放：h1(A)=3 或 h2(A)=11
查找 A：只看 3 和 11这就是它查找最坏 O(1) 的来源。候选位置数量固定，查找次数固定。
二、插入时为什么要“踢人”
如果新 key 的两个候选位置有空位，直接放入。如果都被占，就选择一个位置，把旧 key 踢出去，新 key 占这个位置。
被踢出去的旧 key 还可以去自己的另一个候选位置：
插入 X，候选位置 2 和 7
位置 2 被 A 占
X 放到 2，A 被踢出
A 去 h2(A)这个过程可能连锁发生。它让表保持“每个 key 都在自己的候选位置之一”这个不变量。
三、为什么可能出现循环
连锁踢人不一定总能结束。如果几个 key 的候选位置形成一个闭环，插入新 key 可能来回踢，永远找不到空位。
A 只能在 1/2
B 只能在 2/3
C 只能在 3/1
新 key 也落在这些位置实现通常会设置最大踢出次数，比如超过 500 次就认为失败，然后扩容或换哈希种子重新建表。
四、查找为什么快但插入更复杂
查找只需检查固定位置：
return table[h1(key)] == key || table[h2(key)] == key插入却可能触发多次搬迁，甚至 rehash。它的性能特点很鲜明：读快，写复杂。
| 操作 | 特点 |
|---|---|
| 查找 | 固定检查 2 个或少数位置 |
| 删除 | 找到候选位置后清空 |
| 插入 | 可能连锁踢出 |
| 扩容 | 失败或负载过高时触发 |
五、和布隆过滤器有什么不同
两者都用多个哈希函数，但目的不同。布隆过滤器是概率集合，可能误判存在；Cuckoo Hashing 是精确哈希表，需要真的存 key/value。
布隆过滤器回答“可能在不在集合”，Cuckoo Hashing 回答“key 对应的值是什么”。不要因为都多哈希就混为一谈。
六、适合什么场景
Cuckoo Hashing 适合读多写少、希望查找延迟稳定的场景。写入特别频繁且负载变化大的场景，连锁搬迁和 rehash 会更难控制。
记忆钩子：Cuckoo Hashing 的查找快，是因为每个 key 只有几个固定“家”；插入麻烦，是因为新住户可能一路踢人。
七、常见误区与追问
- 误区：Cuckoo Hashing 没有冲突。 冲突仍然存在，只是通过多个候选位置和踢出搬迁处理。
- 误区：插入也是严格 O(1)。 平均可能很好，但最坏可能连锁搬迁甚至 rehash。
- 误区：多个哈希函数就是布隆过滤器。 Cuckoo Hashing 是精确表，布隆过滤器是概率结构。
- 追问：为什么查找最坏 O(1)？ 因为只检查固定数量候选位置，不沿长探测链走。
- 追问：插入循环怎么办？ 设置踢出上限，失败后扩容或更换哈希函数重新构建。
八、加强记忆
Cuckoo Hashing 可以记成“每个 key 有两个家”。查找只看家里有没有，所以稳定；插入时新 key 可能把别人赶去另一个家，所以复杂。它是用写入复杂度换读取确定性的典型设计。