Почему «простейшая» реализация хеш-кода должна использоваться вместо «наивной»? - PullRequest
Новая
       6

Почему «простейшая» реализация хеш-кода должна использоваться вместо «наивной»?

5 голосов
/ 15 марта 2010

Я видел, что рекомендуется использовать реализацию функции 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

Ответы [ 2 ]

3 голосов
/ 15 марта 2010

Вероятность столкновений также зависит от ожидаемого распределения входных данных. В вашем примере вы принимаете входные данные, которые равномерно распределены по всему диапазону. Это идеальная ситуация, и неудивительно, что оба алгоритма работают хорошо.

Однако, если вы предполагаете, что входные данные, как правило, похожи в старших битах и ​​отличаются в основном только младшими битами (примечание: многие реальные данные похожи на это), метод простого числа распространит эту вариацию весь хэш, тогда как метод XOR не будет - небольшие изменения в младших битах двух или более значений могут легко компенсировать друг друга, когда XOR'ed. Таким образом, метод простых чисел в этом случае менее вероятен.

Также вы должны использовать 32-битные значения для GetHashCode, а не 8-битные значения.

1 голос
/ 15 марта 2010

Сокращение хэша - ваша проблема здесь. Метод Xor может выдавать только 256 различных значений. Метод Prime может генерировать более 750 000 различных значений, но вы отбрасываете 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, он не имеет эквивалента ключевого слова C # unchecked. Вы должны отключить это глобально с помощью Project + Properties, вкладки Compile, Advanced Compile Options, отметьте галочкой «Удалить проверки целочисленного переполнения». Избегайте этого, вычисляя хеш как Int64. Что делает его немного дороже.

...