布谷鸟哈希原理、配表查表方法

2025-12-03 14:59:16

一、 核心原理：为什么叫“布谷鸟”？

布谷鸟（Cuckoo）有一种习性：它不筑巢，而是把蛋下在其他鸟的巢里。如果巢里的蛋满了，它会把别人的蛋踢出去，把自己的蛋放进去。

布谷鸟哈希借用了这个隐喻：

  1. 两个哈希函数：我们准备两个不同的哈希函数，$H_1$和$H_2$。

  2. 两个可能的巢：对于任何一个元素$x$，它只有两个可能的位置：$T_1[H_1(x)]$或者$T_2[H_2(x)]$。

  3. 踢出（Kick）机制：如果要插入新元素时，发现两个位置都被占了，新元素会强制把老元素“踢走”，霸占它的位置。被踢走的老元素则去寻找它的备用位置。

二、 配置表（构建）与查表流程

1. 查表原理（Lookup）

这是布谷鸟哈希最大的优势。查找过程极其简单，没有任何链表遍历或探测循环。

给定一个 Key，查找步骤如下：

  1. 计算位置A：$Pos_A = H_1(Key)$。检查该位置是否是我们要找的 Key？如果是，返回。

  2. 计算位置B：$Pos_B = H_2(Key)$。检查该位置是否是我们要找的Key？如果是，返回。

  3. 结束：如果这两个位置都不是，那么该 Key 一定不存在。

结论：查找次数固定为2 次哈希计算+ 2 次内存访问。绝对的$O(1)$。

2. 配置表生成原理（Insertion/Build）

构建过程相对复杂，因为涉及“踢馆”行为。

插入Key 的步骤：

  1. 先尝试放入位置$H_1(Key)$。如果该位置为空，插入成功。

  2. 如果位置$H_1(Key)$已经有元素（叫它$Old\_Key$），则新 Key 霸占该位置。

  3. $Old\_Key$ 被踢出，被迫去寻找它的另一个位置（如果它之前在 $H_1$ 位置，它就去 $H_2$位置；反之亦然）。

  4. 如果$Old\_Key$ 的新位置又是空的，插入成功。

  5. 如果新位置也有人，继续踢出……以此类推，直到所有元素都安顿好。

  6. 死循环：如果踢出的次数超过设定阈值（说明表太满或形成环路），则判定构建失败，需要更换哈希函数的随机种子（Seed）并**重哈希（Rehash）**整个表。

三、 具体例子演练

假设我们有两个哈希表$T_1$和$T_2$，长度都为 5（索引 0-4）。

设定哈希函数：

我们要插入的数据序列： 20, 50, 53

第一步：插入20

  1. 计算$H_1(20) = 20 mod 5 = 0。

  2. 检查$T_1[0]，是空的。

  3. 操作：直接放入。

索引 T1（哈希 1） T2（哈希 2）
0 20  
1    
2    
3    
4    

第二步：插入50

  1. 计算$H_1(50) = 50 mod 5 = 0。

  2. 检查$T_1[0]，冲突！里面已经有20了。

  3. 踢出机制启动：

    • 50霸占$T_1[0]。

    • 20 被踢出，手握着自己的值，去找备用位置。

    • 20计算它的$H_2(20) = (20/5) mod 5 = 4。

    • 检查$T_2[4]，是空的。

    • 20成功落户$T_2[4]。

索引 T1（哈希 1） T2（哈希 2）
0 50 (把20踢走了)  
1    
2    
3    
4    

第三步：插入53 (多米诺骨牌效应)

  1. 计算$H_1(53) = 53 mod 5 = 3。

  2. 检查$T_1[3]，是空的。

  3. 操作：直接放入。

此时一切正常。为了演示更复杂的踢出，我们增加一个数据：插入75。

第四步：插入75 (复杂的踢出链)

  1. 计算$H_1(75) = 75 mod 5 = 0。

  2. 检查$T_1[0]，冲突！里面是50。

  3. 第一轮踢出：

    • 75霸占$T_1[0]。

    • 50被踢出。

  4. 50找新家：

    • 50原来在$H_1，现在找 $H_2。

    • $H_2(50) = (50/5) mod 5 = 10 mod 5 = 0。

    • 检查$T_2[0]，是空的。

    • 50落户$T_2[0]。

最终状态：

索引 T1（哈希 1） T2（哈希 2）
0 75 50
1    
2    
3 53  
4   20

四、 查表演示（Lookup）

现在我们要查找Key = 20。

  1. 计算Hash 1：$H_1(20) = 0。

    • 查看$T_1[0]，里面是 75。

    • 不匹配 (75 不等于 20）。

  2. 计算Hash 2：$H_2(20) = 4。

    • 查看$T_2[4]，里面是20。

    • 匹配！返回数据。

如果要查找Key = 99 (不存在)：

  1. $H_1(99) = 4。$T_1[4]是空。

  2. $H_2(99) = 4。$T_2[4]是20(不匹配)。

  3. 结论：不存在。

五、 为什么配置表特别适合布谷鸟哈希？

配置表（如Excel 转出的二进制数据）有以下特点：

  1. 只读（Read-Only）：程序运行时，我们只会疯狂查询，不会动态插入删除。

  2. 离线构建：我们可以在打包阶段（Build Time）花时间去生成哈希表。即使构建时发生了死循环（踢出次数过多），编译器只需要换一个随机种子重新生成一遍即可，直到生成一个完美的、没有冲突的表结构。

对比传统哈希（链地址法）：

总结

返回首页