5

HashMapのソースコードを調べて、いくつか質問があります。PUTメソッドは、キーと値を取得し、

  1. キーのハッシュコードのハッシュ関数。

  2. 前の手順で取得したハッシュを使用して、このペアのバケットの場所を計算します

    public V put(K key, V value) {
   int hash = hash(key.hashCode());
   int i = indexFor(hash, table.length);
   .....
}


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


static int indexFor(int h, int length) {
   return h & (length-1);
}

例：

  • サイズ10のHashMapを作成します。
  • put（k、v）を3回呼び出し、これらの3つがバケットloc 7、8、および9を占めると想定します。
  • プット4番目のK、Vペアを呼び出すと、次のようになります
    • hash（）はkey.hashcode（）で呼び出され、ハッシュが計算されます
    • indexForはハッシュに基づいて計算されます

質問：

  1. 4番目のk、vの計算されたバケット位置が既存の境界外にある場合はどうなりますか？場所11と言いますか？

よろしくお願いしますAkh

4

3 に答える 3

2

最初の質問：マップは常にサイズに2の累乗を使用します（10の容量を指定すると、実際には16を使用します）。つまり、index & (length - 1)常に範囲内にある[0, length)ため、常に範囲内にあります。

2番目と3番目の質問が何に関連しているかは明確ではありません。必要がない限り、すべてを再割り当てするとは思い ません。HashMap

于 2012-09-25T18:21:17.203 に答える
1

HashMapsは通常、バケット数を変更するハッシュコードを使用します。衝突が発生したときに何が起こるかは、実装によって異なります（JavaのHashMapについては不明です）。2つの基本的な戦略があります。バケットに含まれるアイテムのリストを保持するか、バケットがいっぱいの場合は他のバケットにスキップします。私の推測では、HashMapはリストバケットアプローチを使用しています。

于 2012-09-25T18:21:41.913 に答える
0

詳細を見てみましょう。ハッシュマップはバケットサイズをどのように初期化しますか？

次のコードはHashMap.javaからのものです

while（i <paramInt）i << = 1;

最初の10を渡すと、上記のコードを使用して2のサイズになります。したがって、上記のコードを使用して、HashMapはバケットサイズ16を初期化します。

以下のコードは、バケットインデックスの計算に使用されます。

static int indexFor(int h, int length) {
        return h & (length - 1);
    }
于 2017-10-10T09:55:42.823 に答える