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

Question

我已经看到建议使用GetHashCode函数的素数实现，例如here。但是使用下面的代码（在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位值。

Answer 2

截断散列是你的问题。 Xor方法只能生成256个不同的值。 Prime方法可以生成超过750,000个不同的值，但是只使用8个低位就可以丢弃749,744个值。因此，从来没有比Xor做得更好。

在您的具体情况下，您可以做得更好。 Integer中有足够的位来生成具有1600万个不同值的唯一哈希值：

  Public Shared Function GetGoodHash(ByVal valueOne As Integer, ByVal valueTwo As Integer, ByVal valueThree As Integer) As Integer
    Return valueOne And 255 + (valueTwo And 255) << 8 + (valueThree And 255) << 16
  End Function

当输入值分布均匀时，Xor方法是可以的。 prime方法的一个问题是很容易触发溢出异常。在VB.NET代码中很难处理，它没有相应的C＃unchecked关键字。您必须使用Project + Properties，Compile选项卡，Advanced Compile Options全局关闭它，勾选“删除整数溢出检查”。通过将哈希计算为Int64来避免这种情况。这让它有点贵。