布谷鸟哈希(Cuckoo Hashing)

定义

布谷鸟哈希(Cuckoo Hashing)由 Pagh 和 Rodler 于 2001 年提出,名称来自布谷鸟把其他鸟蛋挤出巢的习性:每个键有两个候选桶(由两个独立哈希函数给出),必须存放在其中之一。

原理

查询与删除最坏 O(1):只检查两个位置。插入时若两个候选桶都被占,就把其中一个住户"踢"到它的另一个候选位置,被踢者再递归踢别人;若踢出链条过长(可能成环),则更换哈希函数并整体重建。负载因子约 50% 以下时插入期望常数;每桶存多个槽位或用更多哈希函数的变体可把负载率提到 90% 以上。

应用

布谷鸟哈希用于对查询延迟有硬性要求的场景:网络设备的流表与包分类、GPU 哈希表、内存键值系统(如 MemC3 对 Memcached 的改造);布谷鸟过滤器把同一思想用于近似成员查询,成为布隆过滤器的可删除替代。

优缺点

优点是最坏情形查询 O(1)、无链表指针、缓存行为可预测;缺点是插入可能触发连锁搬迁甚至全表重建,对哈希函数质量敏感。