什么是 Cuckoo Hashing？它是如何工作的？

Cuckoo Hashing 是一种用于解决 Hash Table 中哈希冲突的技术。它通常使用两个或多个哈希函数，使每个键拥有多个可能的存储位置。

例如：

h1(key)
h2(key)

核心思想

假设我们需要插入键 A。首先计算 h1(A)。如果该位置为空，则直接存储 A。

如果该位置已经存储了 B，那么 A 可以替换 B，而 B 则需要移动到自己的另一个候选位置。

插入 A
↓
位置被 B 占用
↓
A 替换 B
↓
B 移动到另一个候选位置

这个过程可能持续到找到空位置为止。

查找操作

查找一个键时，只需要检查它的候选位置：

h1(key)
h2(key)

因此查找通常具有：

O(1)

的时间复杂度。

Cycle 问题

连续的键迁移可能形成循环：

A → B → C → A → B → C

因此实际实现通常会限制最大迁移次数。如果超过限制仍无法完成插入，则可以进行 Rehashing。

Rehashing

Rehashing 通常包括选择新的哈希函数、扩大哈希表以及重新插入已有元素。

时间复杂度

| 操作 | 通常复杂度 | |---|---| | Search | O(1) | | Delete | O(1) | | Insert | Expected O(1) | | Rehash | O(n) |

优点

• 查找速度非常快
• 只需检查少量固定位置
• 不需要为每个 Bucket 维护链表
• 适合 Lookup 密集型系统

缺点

• 插入逻辑相对复杂
• 可能出现 Cycle
• 有时需要 Rehashing
• 哈希函数的质量非常重要
• 较高的 Load Factor 会增加插入难度

应用场景

Cuckoo Hashing 的思想适用于需要快速查找的内存数据结构、缓存系统、网络系统以及其他高性能 Lookup 场景。

这一思想还被应用于 Cuckoo Filter。Cuckoo Filter 是一种用于 Membership Query 的概率型数据结构，经常与 Bloom Filter 进行比较。

总结

Cuckoo Hashing 通过为每个键提供多个候选位置，并在发生冲突时移动已有键来解决 Hash Collision。

它最大的优势是快速且可预测的查找性能，而主要代价是插入过程更加复杂，并需要处理 Cycle、Load Factor 和偶尔发生的 Rehashing。