哈希除法散列法与乘法散列法的缺点及碰撞问题对比

1. 除法散列法N为2的幂时碰撞率高的根本原因 #

当N = 2^p时，f(k) = k mod N的计算本质是仅保留k的二进制表示的低p位，高位信息完全不参与哈希运算：

• 如果输入的key存在明显的低位分布规律（比如大量key是按4、8等2的整数次幂步长对齐的整数，低位全为0），就会出现大量重复的哈希结果
• 这种情况下哈希结果完全依赖输入的低p位分布，没有利用输入的全量信息，对输入分布的适配性极差

2. 乘法散列法规避该问题的核心逻辑 #

乘法散列的哈希函数为f(k)=⌊N×(kA−⌊kA⌋)⌋，其中A通常取0~1之间的无理数（比如黄金分割常数A=(√5-1)/2 ≈ 0.618），规避碰撞的逻辑如下：

• 计算k*A时，输入k的所有二进制位的信息会被扩散到乘积的整数部分和小数部分，我们取的kA − ⌊kA⌋是乘积的小数部分，这部分已经包含了k所有位的信息，不存在仅用局部位计算的问题
• 最后一步乘N再向下取整的操作，本质是从小数部分中取出前p位（当N=2^p时），而这部分信息是输入k全位经过无理数乘法打散后的结果，和输入k的低位没有直接对应关系，哪怕输入k的低位高度重合，打散后的小数部分也会有明显差异，自然大幅降低了碰撞概率

3. 两者碰撞概率差异的本质 #

• 除法散列的哈希结果和输入的局部位强绑定，只要输入局部位相同就会碰撞，只有选择素数作为N才能在一定程度上降低碰撞概率，适配性差
• 乘法散列通过全位扩散的设计，让哈希结果和输入的所有位都相关，哪怕输入存在局部规律，经过无理数乘法打散后也会呈现近似均匀的分布，不需要依赖N为素数，哪怕N取2的幂也能保持较低的碰撞率

内容的提问来源于stack exchange，提问作者Avv