知识卡片
Cuckoo驱逐冲突
内容
Cuckoo Hashing 为元素准备多个候选位置，冲突时把旧元素“踢出”并递归安置。它让查询保持常数时间，但插入可能触发连锁迁移，空间利用率和重建策略决定稳定性。
参考来源
- 位置：《大数据日知录：架构与算法》第3章《大数据常用的算法与数据结构》"3.6 Cuckoo哈希（Cuckoo Hashing）"一节（源文件：_epub-src/OEBPS/text00008.html）
- 结论依据：原文明确Cuckoo哈希"同时使用两个不同的哈希函数"为元素找候选位置，插入时"如果没有空桶，则踢出已经占据位置的……之后反复这个过程，直到所有数值都找到空桶安置"，且"这个过程可能导致无限循环，一般做法是设定最大替换次数"；查询"可以在O(1)时间内完成"。
- 原始内容：传统哈希方法只使用一个哈希函数，为了较好地解决哈希冲突问题，Cuckoo哈希同时使用两个不同的哈希函数……插入新的位置，如果没有空桶，则踢出已经占据位置的……之后反复这个过程，直到所有数值都找到空桶安置。对于Cuckoo哈希来说，上述过程可能导致无限循环，一般做法是设定最大替换次数……与传统的哈希方式相比较，Cuckoo哈希省去了当哈希冲突时进行冲突解决的过程，所以查找效率非常高。