布谷鸟哈希：让查找常数时间，冲突时像布谷鸟一样驱逐蛋

标准开放寻址哈希表在条目聚集、探测链变长时性能下降。Rasmus Pagh 和 Flemming Friche Rodler 提出疑问：如果每个键恰好有两个可能的槽位而非一个，会怎样？

他们在 2001 年于奥胡斯 BRICS 展示了这个字典，使用两个哈希函数和两个表。冲突时，新键驱逐原有者，而原有者递归到它的另一个家。查找最多两次探测即可保证完成。

因为表平均只需半满，所以结构在内存效率高的同时，提供了最坏情况下的常数时间查找。

给每个键两个位置，将失败者迁移

两个可能的位置将搜索限制在两次探测，无论键集如何。

驱逐机制解决冲突，无需长探测链或链表。

保持高占用率，内存使用高效且缓存友好。

选择在最坏情况下也快的数据结构，而不是仅在平均情况下快。两选择驱逐将罕见的昂贵冲突转变为有界的两次探测查找。

布谷鸟哈希成为字典理论与实践中的参考结果。其常数时间保证和缓存局部性使其对硬件和高性能路由具有吸引力，驱逐思想影响了后来的哈希和草图方案。