Cuckoo hashing（布谷鸟哈希）：一种哈希表（hash table）冲突解决方法，通常使用两个（或多个）哈希函数为每个键提供候选位置；当插入发生冲突时，会把占位的元素“踢走”（移到它的另一个候选位置），像连锁搬家一样，直到找到空位或触发重建（rehash）。常见优点是查找通常只需检查很少的位置（常见为 2 个）。
/ˈkʌkuː ˈhæʃɪŋ/
We used cuckoo hashing to keep lookups fast.
我们使用布谷鸟哈希来保持查询速度很快。
When the table got too full, cuckoo hashing caused a chain of evictions, so the system rehashed into a larger table to avoid insertion failure.
当表变得过满时，布谷鸟哈希会引发一连串“踢出”操作，因此系统把数据重哈希到更大的表里，以避免插入失败。
“Cuckoo（布谷鸟）”因其把蛋产在别的鸟巢里而得名；在 cuckoo hashing 中，新插入的键会把原来占据位置的键“挤走”，让它去另一个“巢位”（由另一个哈希函数决定的候选位置），这种“占巢/搬巢”的过程形象地对应了算法的核心机制。
Select Language