68

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 の範囲を示したくありません。しかし、ほとんどのアプリケーションでは、比較的小さな値が大きな値よりも頻繁に発生すると思います。(大きな値を持っている場合、素数の選択はおそらく重要ではありません。) 大きな違いはないかもしれませんが、より良い選択はこれを改善するための簡単で明白な方法です。Commons lang HashCodeBuilderも、奇妙なことに小さい値を提案します。

(明確化: これはWhy does Java's hashCode() in String use 31 as a Multiplier? の複製ではありません。なぜなら、私の質問は JDK の 31 の歴史には関係なく、新しいコードでより良い値になるものについてです同じ基本的なテンプレートを使用します.そこにある答えはどれもそれに答えようとしません.)

4

6 に答える 6

80

92821の使用をお勧めします。これが理由です。

これに意味のある答えを与えるには、との可能な値について何かを知っている必要がiありjます。私が一般的に考えることができる唯一のことは、多くの場合、大きな値よりも小さな値の方が一般的であるということです。（プログラムで値として表示される15のオッズは、たとえば438281923よりもはるかに優れています。）したがって、適切な素数を選択して、最小のハッシュコードの衝突をできるだけ大きくすることをお勧めします。31の場合、これはかなり悪いです-すでにの場合、i=-1およびとj=31同じハッシュ値がi=0ありj=0ます。

これは興味深いので、この意味で最高の素数を整数範囲全体で検索する小さなプログラムを作成しました。つまり、プライムごとに、と同じハッシュコードを持つのMath.abs(i) + Math.abs(j)すべての値の最小値を検索し、この最小値が可能な限り大きいプライムを取得しました。i,j0,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よりもはるかに理にかなっていると思います。

于 2010-05-12T07:26:44.150 に答える
6

実際、素数が大きすぎて に近づくとINT_MAX、モジュロ演算のために同じ問題が発生します。ほとんどの長さ 2 の文字列をハッシュすることが予想される場合は、おそらく の平方根に近い素数INT_MAXが最適です。ハッシュする文字列がそれよりも長い場合、それはそれほど問題ではなく、とにかく衝突は避けられません...

于 2009-12-02T21:54:16.047 に答える
5

衝突はそれほど大きな問題ではないかもしれません... ハッシュの主な目的は、1:1 の比較に equals を使用しないようにすることです。衝突したハッシュを持つオブジェクトに対して equals が「一般的に」非常に安価な実装がある場合、これは (まったく) 問題ではありません。

結局、ハッシュの最良の方法は何を比較するかによって異なります。int ペアの場合 (例のように)、基本的なビット単位の演算子を使用するだけで十分です (& または ^ を使用するなど)。

于 2009-12-02T23:20:52.810 に答える
4

私は7243を選びます。少数の衝突を避けるのに十分な大きさです。すぐに小さな数にオーバーフローしません。

于 2009-12-02T22:11:23.703 に答える
4

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

public int hashCode() {
   http://primes.utm.edu/curios/ ;)
   return 97654321 * i ^ 12356789 * j;
}
于 2009-12-02T21:52:51.627 に答える
1

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

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

31を27に置き換えると、結果は非常に似ていることがわかりました。

于 2016-10-15T05:25:26.180 に答える