5

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
4

2 に答える 2

3

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

ただし、入力データが一般に上位ビットで類似しており、ほとんどが下位ビットでのみ異なると仮定すると (注: 多くの実際のデータはこのようなものです)、素数法はこの変動をハッシュ全体に分散させます。一方、XOR 法はそうではありません。2 つ以上の値の下位ビットの小さな変化は、XOR の際に互いに簡単に打ち消し合う可能性があります。したがって、この場合、素数法は衝突する可能性が低くなります。

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

于 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

Xor メソッドは、入力値が適切に分散されている場合に問題ありません。プライム メソッドの問題点は、Overflow 例外が発生しやすいことです。これを VB.NET コードで処理するのは難しく、C# の unchecked キーワードに相当するものはありません。プロジェクト+プロパティ、コンパイルタブ、高度なコンパイルオプションで、「整数オーバーフローチェックを削除する」にチェックマークを付けて、グローバルにオフにする必要があります。ハッシュを Int64 として計算することで、これを回避します。それはそれを少し高価にします。

于 2010-03-15T12:38:20.230 に答える