布谷鸟哈希（Cuckoo Hashing）的冲突解决与插入策略 1. 问题描述 布谷鸟哈希是一种解决哈希表冲突的动态算法，其核心思想是使用两个（或多个）独立的哈希函数和对应的哈希表。当插入新元素时，如果目标位置已被占用，它会“踢走”原有元素（类似布谷鸟的巢寄生行为），并将被踢走的元素重新插入到另一个哈希表的位置。这一过程可能递归进行，直到所有元素找到空位或达到最大迭代次数。 2. 基本结构 假设有两个哈希表 \( T_ 1 \) 和 \( T_ 2 \)，分别对应哈希函数 \( h_ 1(x) \) 和 \( h_ 2(x) \)。每个表的大小为 \( m \)，负载因子（已存储元素与总容量的比值）通常设计为低于 50% 以保证效率。 3. 插入操作的步骤 步骤1：尝试直接插入 计算元素 \( x \) 在表 \( T_ 1 \) 中的位置 \( h_ 1(x) \)。 如果 \( T_ 1[ h_ 1(x) ] \) 为空，直接插入 \( x \) 并结束。 否则，计算 \( x \) 在表 \( T_ 2 \) 中的位置 \( h_ 2(x) \)。若 \( T_ 2[ h_ 2(x) ] \) 为空，插入 \( x \) 并结束。 步骤2：冲突处理与“踢走”机制 若两个位置均被占用，随机选择其中一个表（例如 \( T_ 1 \)）的对应位置，执行以下操作： 将 \( x \) 强制插入 \( T_ 1[ h_ 1(x) ] \)，并踢走该位置原有的元素 \( y \)。 为被踢走的 \( y \) 寻找新位置： 若 \( y \) 原本来自 \( T_ 1 \)，则将其重新插入到 \( T_ 2 \) 的位置 \( h_ 2(y) \)。 若 \( y \) 原本来自 \( T_ 2 \)，则将其重新插入到 \( T_ 1 \) 的位置 \( h_ 1(y) \)。 重复上述过程，直到某个元素找到空位，或达到最大迭代次数（例如 \( 2m \) 次）。 步骤3：处理循环与重构 若迭代过程中出现循环（即同一组元素被反复踢走），说明当前哈希表可能无法容纳所有元素。此时需要： 终止插入操作。 重构哈希表：选择新的哈希函数，重新分配所有元素的存储位置。 4. 查找与删除 查找 ：只需检查 \( T_ 1[ h_ 1(x)] \) 和 \( T_ 2[ h_ 2(x) ] \) 是否等于 \( x \)，时间复杂度为 \( O(1) \)。 删除 ：在对应位置标记删除或直接置空，需避免破坏后续查找的连续性。 5. 关键优化与特性 多个哈希函数 ：使用超过两个哈希函数可以进一步提高负载因子（如达到 90% 以上），但会增加计算开销。 空间效率 ：由于每个元素只有两个候选位置，内存访问局部性较好。 避免循环 ：通过限制最大迭代次数或动态扩容（如翻倍表大小）来保证稳定性。 6. 实例演示 假设哈希函数为： \( h_ 1(x) = x \mod 5 \) \( h_ 2(x) = (x // 5) \mod 5 \) 表大小 \( m = 5 \)，依次插入元素 3, 7, 12： 插入 3：\( h_ 1(3)=3 \)，\( T_ 1[ 3 ]=3 \)。 插入 7：\( h_ 1(7)=2 \)（空），直接存入 \( T_ 1[ 2 ] \)。 插入 12： \( h_ 1(12)=2 \)（冲突，已有 7），尝试 \( h_ 2(12)=2 \)（空），存入 \( T_ 2[ 2 ]=12 \)。 若再插入 10： \( h_ 1(10)=0 \)（空），直接存入 \( T_ 1[ 0 ]=10 \)。 7. 总结 布谷鸟哈希通过强制踢走冲突元素和重新分配的策略，实现了平均 \( O(1) \) 的查找性能。其核心挑战在于避免循环和设计合适的哈希函数，通常适用于对查询效率要求高、插入操作相对较少的场景。