10

誰かがこれらの定数の重要性とそれらが選ばれた理由を説明できますか?

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

ソース: java-se6 ライブラリ

4

2 に答える 2

2

実際には非常に多くの異なる関数が使用され、わずかに異なる目的で使用されているため、適切なハッシュ関数とは何かを理解することは困難です。

Java のハッシュ テーブルは次のように機能します。

  1. それらは、キー オブジェクトにそのハッシュ コードを生成するように要求します。メソッドの実装はhashCode()明らかに可変品質である可能性が高く (最悪の場合、定数値を返します!)、使用している特定のハッシュ テーブルには確実に適合しません。
  2. 次に、上記の関数を使用してビットを少し混ぜ合わせ、上位ビットに存在する情報も下位ビットに移動します。次は…</li>
  3. ハッシュ コードの mod (ハッシュ テーブル配列エントリの数に関して) を取得して、ハッシュ テーブル チェーンの配列へのインデックスを取得します。ハッシュ テーブル配列のサイズが 2 の累乗に相当する可能性が明確にあるため、ステップ 2 でのビットの混合は、単に破棄されないようにするために重要です。
  4. equals()次に、（メソッドに従って）等しいキーを持つエントリに到達するまで、チェーンをトラバースします。

全体像を完成させるために、ハッシュ テーブル配列のエントリ数は一定ではありません。チェーンが長くなりすぎると、配列が新しい大きな配列に置き換えられ、すべてが再ハッシュされます。これは比較的高速であり、通常の使用パターン (多数のput()の後に多数の が続くなどget()) のパフォーマンスに良い影響を与えます。

使用される実際の定数はかなり恣意的です (そして、多数のIntegerやString値などを含むいくつかの単純なコーパスを使った実験によっておそらく選択されます) が、それらの目的はそうではありません: 値全体の情報を値の下位ビットのほとんどに分散させることの出力に存在する情報がhashCode()可能な限り使用されるようにします。

(完全なハッシングや暗号化ハッシングではこれを行いません。名前は似ていますが、実装戦略は大きく異なります。前者は衝突を回避/削減するためにキー空間の知識が必要であり、後者は移動するための情報が必要です。下位ビットだけでなく、すべての方向で。)

于 2012-09-04T15:18:51.590 に答える
0

私はまた、そのような「魔法の」数字について疑問に思っていました. 私の知る限り、それらは魔法の数字です。
広範なテストによって、奇数と素数にはハッシュで使用できる興味深い優先順位があることが証明されています (プライマリ/セカンダリ クラスタリングなどを回避します)。
ほとんどの数値は、統計的に良好な分布を示すことが証明された調査とテストの後に得られたものだと思います。具体的にこれらの数値がなぜそうなのか、私にはわかりませんが、印象はあります（私が間違っている場合は、ここの同僚が私を修正してくれることを願っています）どちらの実装者も、これらの特定の数値がこれらの品質を示す理由を知りません

于 2012-09-03T21:12:43.230 に答える