ハッシュコード計算に適した素数は何ですか?

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

  •  11-09-2019
  •  | 
  •  

質問

Eclipse 3.5 には、Java hashCode() 関数を生成する非常に優れた機能があります。たとえば、(少し短縮されています:) が生成されます。

class HashTest {
    int i;
    int j;        
    public int hashCode() {
        final int prime = 31;
        int result = prime + i;
        result = prime * result + j;
        return result;
    }
}

(クラス内にさらに多くの属性がある場合、 result = prime * result + attribute.hashCode(); 追加の属性ごとに繰り返されます。int の場合は .hashCode() を省略できます。)

これは問題ないようですが、プライムの選択肢 31 に関しては問題ありません。おそらくそこから取られたものだと思われます Java String の hashCode 実装, 、ハードウェア乗算器の導入後は久しくなくなったパフォーマンス上の理由で使用されていました。ここでは、i と j の値が小さい場合に多くのハッシュコードの衝突が発生しています。たとえば、(0,0) と (-1,31) は同じ値になります。小さな値が頻繁に発生するため、これは Bad Thing(TM) だと思います。String.hashCode の場合、「Ca」や「DB」など、同じハッシュコードを持つ多くの短い文字列も見つかります。大きな素数を取る場合、素数を正しく選択すると、この問題は解消されます。

そこで私の質問:選ぶべきプライムは何ですか?それを見つけるためにどのような基準を適用しますか?

これは一般的な質問として意図されているため、i と j の範囲を指定するつもりはありません。しかし、ほとんどのアプリケーションでは、大きな値よりも比較的小さな値が頻繁に発生すると思います。(値が大きい場合、素数の選択はおそらく重要ではありません。) 大きな違いは生じないかもしれませんが、より良い選択をすることは、これを改善するための簡単で明白な方法であるため、そうしない手はありません。コモンズラング ハッシュコードビルダー また、奇妙なことに小さな値を示唆しています。

(説明:これは ない の複製 String 内の Java の hashCode() が乗数として 31 を使用するのはなぜですか? なぜなら、私の質問は JDK の 31 の歴史に関するものではなく、同じ基本テンプレートを使用する新しいコードでより良い値は何かということに関するものだからです。そこにある答えはどれもそれに答えようとしていません。)

役に立ちましたか？

解決

使用することをお勧めします 92821. 。その理由は次のとおりです。

これに対して意味のある答えを与えるには、可能な値について何か知っておく必要があります。 i そして j. 。一般的に考えられる唯一のことは、多くの場合、大きな値よりも小さな値の方が一般的であるということです。(プログラム内の値として 15 が出現する確率は、たとえば 438281923 よりもはるかに優れています。) したがって、適切な素数を選択して、最小のハッシュコードの衝突をできるだけ大きくするのが得策と思われます。31 の場合、これはかなり悪いです - すでに i=-1 そして j=31 と同じハッシュ値を持っています i=0 そして j=0.

これは興味深いので、この意味で最良の素数を int 範囲全体から検索する小さなプログラムを書きました。つまり、各素数について、次の最小値を検索しました。 Math.abs(i) + Math.abs(j) のすべての値にわたって i,j 同じハッシュコードを持つもの 0,0, そして、この最小値ができるだけ大きい素数をとりました。

ドラムロール:この意味での最良の素数は 486187739 です (最小の衝突は i=-25486, j=67194）。92821 とほぼ同じくらい優れており、覚えやすいのですが、衝突が最も小さいのは次のとおりです。 i=-46272 and j=46016.

「小さい」に別の意味を持たせて最小限にしたい場合 Math.sqrt(i*i+j*j) 衝突ができるだけ大きい場合、結果は少し異なります。最も良いのは 1322837333 です。 i=-6815 and j=70091, 、でも私のお気に入りの 92821 (最小の衝突) -46272,46016) も最高値とほぼ同じです。

これらの計算が実際にそれほど意味があるかどうかについては、かなり議論の余地があることは認めます。しかし、そうしない正当な理由がない限り、92821 を素数とすることは 31 よりもずっと理にかなっていると思います。

他のヒント

あなたはそれがINT_MAXに近づくように大きな素数を取る場合は、

実際には、あなたがあるためモジュロ演算の同じ問題を抱えています。あなたは主に長さ2の文字列をハッシュすることが予想される場合は、あなたがハッシュ文字列が

...それはあまり問題ではないとの衝突はとにかく避けられない長い場合、おそらくINT_MAXの平方根に近いプライムは、最高のだろう
1つの比較：

衝突はハッシュの第一の目標は、1のために等号を使用しないことです...このような大きな問題ではないかもしれません。 あなたは、実装を持っている場合は等しい「とは、一般に」hashsを衝突したオブジェクトのための非常に安価であり、これは（すべてでは）問題ではありません。

は終わりでは、ハッシュの最良の方法は、あなたが比較されているかに依存するものです。 INTペアの場合には（^用い＆又はように）十分かもしれない基本的なビット演算子を使用して、（あなたの例のように）。

あなたは、iとjのためのあなたの範囲を定義する必要があります。あなたは両方のために素数を使用することができます。

public int hashCode() {
   http://primes.utm.edu/curios/ ;)
   return 97654321 * i ^ 12356789 * j;
}

私は小さな数字との衝突を避けるために十分な大き7243.を選ぶと思います。すぐに小さな数字にオーバーフローません。

ハッシュコードはプライムとは何の関係もないことを指摘したいだけです。JDK実装では 

for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }

交換してみたら見つかった 31 と 27, 、結果は非常に似ています。

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