16

Java 1.6 APIによって提供されるHashMapクラスのコードを読んでいますが、次の操作の必要性を完全に理解できません（putメソッドとgetメソッドの本体にあります）。

int hash = hash(key.hashCode());

ここで、メソッドhash()の本体は次のとおりです。

 private static int hash(int h) {
         h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

これにより、提供されたハッシュコードに対してビット演算を実行することにより、ハッシュが効果的に再計算されます。APIに次のように記載されていても、そうする必要があることを理解できません。

HashMapは2の累乗の長さのハッシュテーブルを使用するため、これは重要です。そうしないと、下位ビットで異ならないhashCodeの衝突が発生します。

Key Value Parsがデータ構造の配列に格納されていること、およびこの配列内のアイテムのインデックス位置がそのハッシュによって決定されることを理解しています。私が理解できないのは、この関数がハッシュ分布にどのように値を追加するかということです。

4

4 に答える 4

25

Helper が書いたように、キー オブジェクトの既存のハッシュ関数に問題があり、下位ビットを混合するのに十分な仕事をしない場合に備えて存在します。pgrasが引用したソースによると、

 /**
  * Returns index for hash code h.
  */
 static int indexFor(int h, int length) {
     return h & (length-1);
 }

ハッシュは 2 の累乗の長さで AND 演算されます (したがって、length-11 のシーケンスであることが保証されます)。この ANDing により、 の下位ビットのみhが使用されます。の残りhは無視されます。何らかの理由で、元のハッシュが 2 で割り切れる数のみを返すと想像してください。それを直接使用すると、ハッシュマップの奇数の位置は使用されず、衝突数が 2 倍に増加します。本当に病的なケースでは、不適切なハッシュ関数により、ハッシュマップが O(1) コンテナーよりもリストのように動作する可能性があります。

Sun のエンジニアは、あまりにも多くのハッシュ関数が下位ビットで十分にランダムでないこと、および多くのハッシュマップが上位ビットを使用するほど大きくないことを示すテストを実行したに違いありません。このような状況では、HashMap のビット操作はhash(int h)、追加の計算が必要になる場合でも、(衝突率が低いため) 予想されるほとんどのユースケースよりも実質的に改善されます。

于 2010-03-29T15:04:01.733 に答える
2

hashCode の実装がうまくいかなくても、適切な配布を保証するためにこれが行われていることをどこかで読んだことがあります。

于 2010-03-29T13:42:49.760 に答える
2

ハッシュマップでわかるように、基礎となる実装はハッシュ テーブル、具体的にはクローズド バケット ハッシュ テーブルです。負荷係数によって、コレクション内のオブジェクトの適切な量 / バケットの総数が決まります。

さらに要素を追加し続けるとしましょう。そうするたびに、それは更新ではなく、オブジェクトの hashcode メソッドを実行し、モジュロ演算子でバケットの数を使用して、オブジェクトを入れるバケットを決定します。

n (コレクション内の要素の数) / m (バケットの数) が大きくなるにつれて、読み取りと書き込みのパフォーマンスが低下します。

ハッシュコード アルゴリズムが優れていると仮定すると、パフォーマンスはこの比較 n/m に左右されます。

再ハッシュは、バケットの数を変更するためにも使用されますが、コレクションが構築されたときと同じ負荷係数を維持します。

ハッシュ実装の主な利点は、読み取りと書き込みの理想的な O(1) パフォーマンスです。

于 2011-02-18T16:25:27.213 に答える
1

ご存知のように、object.hashCode() はユーザーによってオーバーライドされる可能性があるため、実装が非常に悪いと、ランダムではない下位レベルのビットがスローされます。これにより、一部のバケツが混雑する傾向があり、多くのバケツが満たされないままになります。

彼らがハッシュで何をしようとしているかの視覚的なマップを作成しました。hash(int h) メソッドは、結果の数値がよりランダムに (したがって、より均一にバケットに) 分散されるように、ビット レベルの操作を行って乱数を作成しているようです。

各ビットは、次のように異なるビットに再マップされます。

        h1 = h1 ^ h13 ^ h21 ^ h9 ^ h6     
        h2 = h2 ^ h14 ^ h22 ^ h10 ^ h7
        h3 = h3 ^ h15 ^ h23 ^ h11 ^ h8
        h4 = h4 ^ h16 ^ h24 ^ h12 ^ h9
        h5 = h5 ^ h17 ^ h25 ^ h13 ^ h10

. . . .

h12まで。

ご覧のとおり、h の各ビットは、それ自体から非常に離れています。そのため、かなりランダムになり、特定のバケットが混雑することはありません。この助けを願っています。完全なビジュアルが必要な場合は、メールを送ってください。

于 2011-09-21T14:02:57.050 に答える