「素朴な」ハッシュコード実装の代わりに、「プライムベースの」ハッシュコード実装を使用する必要があるのはなぜですか？

StackOverflow https://stackoverflow.com/questions/2445538

  •  20-09-2019
  •  | 
  •  

質問

たとえば、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
役に立ちましたか？

解決

衝突の確率は、入力データの予想される分布にも依存します。例では、範囲全体に均一に分布している入力データを想定しています。これは理想的な状況であり、両方のアルゴリズムがうまく機能することは驚くことではありません。

ただし、入力データが一般にハイビットで類似しており、主に低ビットでのみ異なると仮定すると（注：多くの実際のデータはこのようなものです）、プライムナンバーメソッドはこのバリエーションをハッシュ全体に広げます。 XORメソッドはそうではありませんが、2つ以上の値の低いビットの小さな変化は、Xor'edのときに互いに簡単にキャンセルできます。したがって、この場合、素数法は衝突する可能性が低くなります。

また、8ビット値ではなく、GethashCodeに32ビット値を使用する必要があります。

他のヒント

ここでのハッシュを切り捨てることがあなたの問題です。 XORメソッドは、256個の異なる値のみを生成できます。プライムメソッドは750,000を超える異なる値を生成できますが、8つの低ビットのみを使用して749,744を捨てます。したがって、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メソッドは問題ありません。主要な方法の問題は、オーバーフローの例外を簡単にトリガーできることです。 VB.NETコードで対処するのは難しいため、C＃Unチェックキーワードに相当するものはありません。 Project +プロパティ、コンパイルタブ、アドバンストコンパイルオプション、「整数オーバーフローチェックの削除」を使用して、グローバルにオフにする必要があります。ハッシュをINT64として計算して、それを避けてください。それは少し高価になります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top