布谷鸟哈希（Cuckoo Hashing） 描述 布谷鸟哈希是一种解决哈希表冲突的开放寻址方案，它使用两个（或多个）独立的哈希函数和两个对应的哈希表（或一个表的两个逻辑部分）。其核心思想是每个键可能被存储在两个候选位置之一，当插入新键时，如果两个候选位置都被占用，它会"踢出"其中一个已存在的键，并将被踢出的键重新插入到它的另一个候选位置，这一过程可能递归进行。布谷鸟哈希在理想情况下能实现常数级的查找和删除时间复杂度。 核心原理 双哈希函数与双表 ：设两个哈希函数 \( h_ 1(x) \) 和 \( h_ 2(x) \)，以及两个大小相同的表 \( T_ 1 \) 和 \( T_ 2 \)（或一个表的两个部分）。 插入策略 ：键 \( x \) 只能位于 \( T_ 1[ h_ 1(x)] \) 或 \( T_ 2[ h_ 2(x)] \) 中的一个位置。插入时，如果任一位置为空，直接存入；若均被占，随机选择一个位置（如 \( T_ 1[ h_ 1(x)] \)）踢出原有键 \( y \)，存入 \( x \)，然后为 \( y \) 寻找其另一个候选位置（若 \( y \) 原在 \( T_ 1 \)，则检查 \( T_ 2[ h_ 2(y) ] \)），递归处理。 循环检测与扩容 ：若递归过程中出现循环（如键被重复踢出），或递归深度超过阈值（如表大小的对数），则触发重新哈希（rehash）并扩容表。 步骤详解 初始化 创建两个大小均为 \( m \) 的表 \( T_ 1 \) 和 \( T_ 2 \)，初始化为空。 选择两个独立的哈希函数 \( h_ 1 \) 和 \( h_ 2 \)，例如 \( h_ 1(x) = x \mod m \)，\( h_ 2(x) = (x \div m) \mod m \)（其中 \( \div \) 表示整数除法）。 查找操作 检查 \( T_ 1[ h_ 1(x)] \) 和 \( T_ 2[ h_ 2(x) ] \)：若任一位置存在 \( x \)，则找到；否则不存在。 时间复杂度：\( O(1) \)，仅需两次内存访问。 插入操作 基础步骤 ： a. 若 \( T_ 1[ h_ 1(x) ] \) 为空，存入 \( x \)，结束。 b. 否则，若 \( T_ 2[ h_ 2(x) ] \) 为空，存入 \( x \)，结束。 c. 若均不空，随机选择（如优先 \( T_ 1 \)）：踢出 \( T_ 1[ h_ 1(x) ] \) 中的键 \( y \)，将 \( x \) 存入该位置，然后对 \( y \) 递归执行插入操作（此时 \( y \) 的候选位置变为另一个表）。 示例 ： 假设表大小 \( m = 3 \)，哈希函数 \( h_ 1(x) = x \mod 3 \)，\( h_ 2(x) = (x \div 3) \mod 3 \)。 插入 3：\( h_ 1(3)=0 \)，\( T_ 1[ 0] \) 空 → 存入 \( T_ 1[ 0 ] \)。 插入 5：\( h_ 1(5)=2 \) 空 → 存入 \( T_ 1[ 2 ] \)。 插入 7：\( h_ 1(7)=1 \) 空 → 存入 \( T_ 1[ 1 ] \)。 插入 10：\( h_ 1(10)=1 \) 被 7 占，\( h_ 2(10)=3 \) 空？错误！应计算 \( h_ 2(10) = (10 \div 3) \mod 3 = 3 \mod 3 = 0 \)。 修正后：\( h_ 1(10)=1 \)（被 7 占），\( h_ 2(10)=0 \)（空）→ 存入 \( T_ 2[ 0 ] \)。 插入 12：\( h_ 1(12)=0 \)（被 3 占），\( h_ 2(12)=4 \mod 3=1 \) 空 → 存入 \( T_ 2[ 1 ] \)。 插入 15：\( h_ 1(15)=0 \)（被 3 占），\( h_ 2(15)=5 \mod 3=2 \) 空 → 存入 \( T_ 2[ 2 ] \)。 插入 18：\( h_ 1(18)=0 \)（被 3 占），\( h_ 2(18)=6 \mod 3=0 \)（被 10 占）。 踢出策略：踢 \( T_ 1[ 0] \) 的 3，存入 18；为 3 找新位置：\( h_ 2(3)=1 \)（被 12 占）→ 踢 \( T_ 2[ 1] \) 的 12，存入 3；为 12 找新位置：\( h_ 1(12)=0 \)（现为 18）→ 踢 \( T_ 1[ 0] \) 的 18，存入 12；为 18 找新位置：\( h_ 2(18)=0 \)（被 10 占）→ 踢 \( T_ 2[ 0] \) 的 10，存入 18；为 10 找新位置：\( h_ 1(10)=1 \)（被 7 占）→ 踢 \( T_ 1[ 1] \) 的 7，存入 10；为 7 找新位置：\( h_ 2(7)=2 \)（被 15 占）→ 踢 \( T_ 2[ 2] \) 的 15，存入 7；为 15 找新位置：\( h_ 1(15)=0 \)（被 12 占）→ 循环检测触发，重新哈希并扩容。 删除操作 检查 \( T_ 1[ h_ 1(x)] \) 和 \( T_ 2[ h_ 2(x) ] \)，若存在 \( x \) 则删除。 时间复杂度：\( O(1) \)。 循环处理与优化 最大递归深度 ：设置阈值（如 \( 2 \log m \)），避免无限递归。 多哈希函数 ：可使用超过两个哈希函数（如布谷鸟哈希的变种），增加候选位置，降低冲突概率。 重新哈希 ：当插入失败时，选择新的哈希函数、扩容表（如双倍大小），并重新插入所有键。 优势与局限 优势 ：查找和删除最坏情况为 \( O(1) \)，适合高负载因子场景（可达 90%+）。 局限 ：插入时间可能因递归踢出而变长；重新哈希成本高；对哈希函数独立性要求严苛。 布谷鸟哈希通过"踢出"机制动态调整键的位置，平衡了空间与时间效率，是哈希表冲突解决的一种高效方案。