案例库 · 软件与 IT · 技术决策 · 2001
布谷鸟哈希：让查找常数时间，冲突时像布谷鸟一样驱逐蛋
Pagh 和 Rodler 给每个键两个家；冲突时新来者驱逐原有者，保证最坏情况 O(1) 查找。
BRICS（奥胡斯大学）
那一手
标准开放寻址哈希表在条目聚集、探测链变长时性能下降。Rasmus Pagh 和 Flemming Friche Rodler 提出疑问：如果每个键恰好有两个可能的槽位而非一个，会怎样？
他们在 2001 年于奥胡斯 BRICS 展示了这个字典，使用两个哈希函数和两个表。冲突时，新键驱逐原有者，而原有者递归到它的另一个家。查找最多两次探测即可保证完成。
因为表平均只需半满，所以结构在内存效率高的同时，提供了最坏情况下的常数时间查找。
为什么管用
- 两个可能的位置将搜索限制在两次探测，无论键集如何。
- 驱逐机制解决冲突，无需长探测链或链表。
- 保持高占用率，内存使用高效且缓存友好。
值了多少给每个键两个位置，将失败者迁移聪明
可以搬走什么
选择在最坏情况下也快的数据结构，而不是仅在平均情况下快。两选择驱逐将罕见的昂贵冲突转变为有界的两次探测查找。
后来呢
布谷鸟哈希成为字典理论与实践中的参考结果。其常数时间保证和缓存局部性使其对硬件和高性能路由具有吸引力，驱逐思想影响了后来的哈希和草图方案。
资料来源
发现哪里写错了？告诉我们。