为什么要使用"基于质量"的哈希码实现而不是"天真"哈希码实现呢？

Question

我已经看到建议使用GetHashCode函数的素数实现,例如这里.但是使用下面的代码(在VB中,抱歉),似乎该实现提供了与"天真"xor实现相同的哈希密度.如果密度相同,我认为在两种实现中都存在相同的碰撞概率.我错过了为什么主要方法更受欢迎？

我认为如果哈希码是一个字节,我不会失去整数情况的一般性.

Sub Main()
    Dim XorHashes(255) As Integer
    Dim PrimeHashes(255) As Integer

    For i = 0 To 255
        For j = 0 To 255
            For k = 0 To 255
                XorHashes(GetXorHash(i, j, k)) += 1
                PrimeHashes(GetPrimeHash(i, j, k)) += 1
            Next
        Next
    Next

    For i = 0 To 255
        Console.WriteLine("{0}: {1}, {2}", i, XorHashes(i), PrimeHashes(i))
    Next
    Console.ReadKey()
End Sub

Public Function GetXorHash(ByVal valueOne As Integer, ByVal valueTwo As Integer, ByVal valueThree As Integer) As Byte
    Return CByte((valueOne Xor valueTwo Xor valueThree) Mod 256)
End Function

Public Function GetPrimeHash(ByVal valueOne As Integer, ByVal valueTwo As Integer, ByVal valueThree As Integer) As Byte
    Dim TempHash = 17
    TempHash = 31 * TempHash + valueOne
    TempHash = 31 * TempHash + valueTwo
    TempHash = 31 * TempHash + valueThree

    Return CByte(TempHash Mod 256)
End Function

Answer 1

碰撞的概率还取决于输入数据的预期分布。在您的示例中，您假设输入数据在整个范围内均匀分布。这是理想的情况，两种算法都表现良好也就不足为奇了。

但是，如果您假设输入数据通常在高位上相似，而主要仅在低位上不同（注意：很多真实数据都是这样），则素数方法会将这种变化分散到整个哈希上而 XOR 方法不会 - 当 XOR 运算时，两个或多个值的低位的微小变化很容易相互抵消。所以素数法在这种情况下发生冲突的可能性较小。

此外，您应该对 GetHashCode 使用 32 位值，而不是 8 位值。