5

我已经看到建议使用 GetHashCode 函数的素数实现，例如这里。但是，使用以下代码（在 VB 中，抱歉），似乎该实现提供了与“天真”异或实现相同的哈希密度。如果密度相同，我会假设两种实现中的碰撞概率相同。关于为什么首选主要方法，我是否遗漏了什么？

我假设如果哈希码是一个字节，我不会失去整数情况的一般性。

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
4

2 回答 2

3

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

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

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

于 2010-03-15T07:16:00.947 回答
1

截断哈希是你的问题。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

The Xor method is okay when the input values are well distributed. A problem with the prime method is that it is easy to trigger an Overflow exception. That's difficult to deal with in VB.NET code, it doesn't have the equivalent of the C# unchecked keyword. You have to turn that off globally with Project + Properties, Compile tab, Advanced Compile Options, tick "Remove integer overflow checks". Avoid that by computing the hash as an Int64. Which makes it a bit expensive.

于 2010-03-15T12:38:20.230 回答