代码之家 › 专栏 › 技术社区 › Wilhelm

为什么要使用“基于质数”的hashcode实现而不是“幼稚”的hashcode实现?

gethashcode .net

Wilhelm · 技术社区 · 14 年前

我已经看到,例如,建议使用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

2 回复 | 直到 7 年前

Mark Byers 14 年前

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

但是,如果假设输入数据通常在高位相似,并且只在低位不同(注意:许多实际数据是这样的),质数方法将把这种变化分散到整个散列中,而异或方法将不会-在低位有小的变化两个或多个值的s在执行异或运算时很容易互相抵消,因此质数方法在这种情况下不太可能发生冲突。

另外,对于gethashcode,应该使用32位值,而不是8位值。

Hans Passant 14 年前

截断散列是这里的问题。异或方法只能产生256个不同的值。prime方法可以生成超过750000个不同的值,但是只使用8个低位就可以丢弃其中的749744个值。因此,它永远不会比xor做得更好。

在你的具体情况下,你可以做得更好。整数中有足够的位生成具有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+属性、compile选项卡、高级编译选项、勾选“删除整数溢出检查”全局关闭该选项。通过将散列计算为int64来避免这种情况。所以有点贵。