容量とJavaのHashMapでindexFor

Question

のJava HashMapのソースコードを通過する間に、我々はキーの最初のバケットは以下のような方法で決定されて見ることができます。私の理解あたりとして

static int indexFor(int h, int length) { //h = hash of key 
    return h & (length-1);    //length = capacity of array at 
}          //   current time 

初期サイズであれば16（length-1 = 15 = 1111）であり、キー​​の生成ハッシュが108378（1 10100111 01011010）の場合、 indexFor()メソッドは10（1010）を返します。

今や、いくつかの追加の後、容量が32に変更されました。ここでキー​​（ハッシュ108378）を検索する場合は、同じindexFor()メソッドのバケットを再度チェックします。 h & (length-1)コードスニペットは26を返します。 （108378 & 31）。

私の質問は、テーブルがサイズ変更された場合、メソッドが正しいバケットを見つける方法ですか？

Answer 1

負荷係数の最大しきい値に達すると、Rehashingと呼ばれるプロセスが発生し、すべての要素が新しいテーブルに移動します。ハッシュテーブルのエントリ数が 負荷係数と現在の容量の積を超える

、ハッシュテーブルは が再ハッシュされ（すなわち、内部データ構造が再構築されている）ので ことハッシュテーブルのバケット数は約2倍です。

マップの予想されるエントリ数とその負荷係数 は、初期容量を設定するときに考慮する必要があります。したがって、再ハッシュ操作の回数を最小限に抑えるために です。

Answer 2

テーブルのサイズが変更されると、lengthパラメータが変更され、indexForメソッドは異なる値を返します。テーブルのサイズが変更されると、現在テーブルにある値を新しいテーブルに移動する必要があります。したがって、新しいインデックスが各値に対して計算されます。

Answer 3

表示されているlengthは、map.size()によって報告された値ではありません。これは、ハッシュテーブルのサイズを表す内部長です。この長さは、密度の高いハッシュマップではsize()より小さくなることがあります。まばらに埋め込まれたハッシュマップでは、size()よりも大きくなることがあります。値が小さいほど、h & (length-1)の評価が同じキーが見つかるほど、より多くのキーがバケットにグループ化されます。いくつかの（できるだけ願わくは等の希）時点

時間にマップは、あまりにも多くの衝突、（各バケットにあまりにも多くのキーを）引き起こし、lengthが小さすぎると判断したのでハッシュを再割り当て、マップを再編成すべてのハッシュ値を再計算し、バケットでキーを再配布して、h & (length-1)がすべてのハッシュ値に対して正しいことを確認してください。