なぜHashMapは初期容量が2の累乗であることを要求しますか？

Question

私は、次の

//The default initial capacity - MUST be a power of two. 
static final int DEFAULT_INITIAL_CAPACITY = 16; 

私の質問を見たとき、私はJavaのHashMapのソースコードを経由して、この要件は、最初の場所に存在しない理由は？私はまた、カスタム容量のHashMapを作成することができますコンストラクタは2の累乗に変換することを参照してください。

int capacity = 1; 
while (capacity < initialCapacity) 
    capacity <<= 1; 

容量は常に2の累乗でなければならないのはなぜ？

また、自動再ハッシングを実行すると、どういうことが起こりますか？ハッシュ関数も変更されていますか？

Answer 1

マップは、intの値（負の場合があります）を[0, table.length)の値にマッピングして、任意のキーに使用する内部テーブルインデックスを使用する必要があります。 table.lengthが安く本当にを行うことができ、2のべき乗、あるとき - とindexForで、次のとおりです。

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

異なるテーブル長を使用すると、残りの部分を計算し、それが非だことを確認する必要があると思います否定的。これは間違いなくマイクロ最適化ですが、おそらく有効なものです。

また、自動再ハッシングを実行すると、どういうことが起こりますか？ハッシュ関数も変更されていますか？

あなたが何を意味するのかは私には明らかではありません。同じハッシュコードが使用されます（各キーでhashCodeを呼び出して計算されるため）が、テーブルの長さが変更されるため、テーブル内で異なるハッシュコードが配布されます。たとえば、テーブルの長さが16の場合、ハッシュコード5と21の両方がテーブルエントリ5に格納されます。テーブルの長さが32に増加すると、異なるエントリになります。

Answer 2

実際には、HashMapのバッキングアレイに素数サイズを使用するのが理想的です。そうすれば、キーはアレイ全体に自然に分散されます。しかし、これはmod分割で動作し、その操作はJavaのすべてのリリースで遅くなり、遅くなりました。 ある意味では、2つの手法の威力は、貧弱なハッシュコード実装では配列内でキー衝突を起こしやすいため、想像できる最悪のテーブルサイズです。

そのため、JavaのHashMap実装ではもう1つの非常に重要なメソッドが見つかるでしょう。これはhash(int)であり、貧弱なハッシュコードを補うものです。