Почему “главная” реализация хэш-кода должна использоваться вместо “наивной”?
Я видел, что реализация простого числа функции GetHashCode, рекомендуют, например, здесь. Однако с помощью следующего кода (в VB, извините), кажется, как будто та реализация дает ту же плотность хеша как "наивную" xor реализацию. Если бы плотность является тем же, я предположил бы, что существует та же вероятность коллизии в обеих реализациях. Я пропускаю что-нибудь на том, почему главный подход предпочтен?
Я - supossing, что, если хэш-код является байтом, я не теряю общность для целочисленного случая.
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 ответа
Вероятность коллизий также зависит от ожидаемого распределения входных данных. В вашем примере вы предполагаете, что входные данные равномерно распределены по всему диапазону. Это идеальная ситуация, и неудивительно, что оба алгоритма работают хорошо.
Однако, если вы предположите, что входные данные в целом похожи в старших битах и различаются в основном только в младших битах (примечание: много реальных данных таковы), метод простого числа распространит это изменение на весь хеш, в то время как метод XOR - нет - небольшие изменения младших битов двух или более значений могут легко нейтрализовать друг друга при выполнении XOR. Таким образом, вероятность столкновения метода простых чисел в этом случае меньше.
Также вы должны использовать 32-битные значения для GetHashCode, а не 8-битные значения.
Усечение хеша - это ваша проблема. Метод Xor может генерировать только 256 различных значений. Метод Prime может генерировать более 750000 различных значений, но вы отбрасываете 749 744 из них, используя только 8 младших битов. И поэтому никогда не сможет справиться лучше, чем Xor.
В вашем конкретном случае вы можете добиться большего. В Integer достаточно битов, чтобы сгенерировать уникальный хэш с 16 миллионами различных значений:
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 подходит, когда входные значения хорошо распределены. Проблема с основным методом заключается в том, что легко вызвать исключение переполнения. С этим трудно справиться в коде VB.NET, у него нет эквивалента ключевому слову unchecked C #. Вы должны отключить это глобально с помощью Project + Properties, вкладки Compile, Advanced Compile Options, отметьте «Удалить проверки переполнения целых чисел». Избегайте этого, вычисляя хэш как Int64. Что делает его немного дороже.