javaのhash（）実装

Question

JavaのHashMapクラスを使用しています。私の理解では、ハッシュテーブルの容量はバケットの数の2乗である（容量16は4つのバケットを意味する）。 put（key、value）が呼び出されると、key.hashCode（）はInteger数を出力し、この新たに追加された（key、value）の組はkey.hashCode（）％バケット数に基づいて配置されます。しかし、次は、上記のコードからHashMap.class

static final int hash(Object key) { 
    int h; 
    return (key == null) ? 0 : (h = key.hashCode())^(h >>> 16); 
} 

の実際の実装である、私はバケットにkey.hashCode（）値のフィッティングが起こるんどのように把握することはできませんよ。

Answer 1

そのコードは、hashCodeをバケットに「適合」させません。上位のビットをより重要にするハッシュコードを「ちょうど」拡散します。ここではそのメソッドのjavadocです。

ハッシュの上位ビットを低く計算するためにkey.hashCode（）と拡散（XOR）を計算します。このテーブルは2のべき乗マスキングを使用しているため、現在のマスクの上のビットだけが変化するハッシュのセットは常に衝突します。 （よく知られている例の中には、小さなテーブルに連続する整数を保持するFloatキーのセットがあります）。したがって、上位ビットの影響を下方向に広げる変換を適用します。速度、効用、ビット拡散の品質にはトレードオフがあります。多くの一般的なハッシュセットはすでに合理的に配布されているため（拡散の恩恵を受けません）、ビン内の大きな衝突セットを処理するためにツリーを使用するため、システム損失を最小限に抑えるために、また、テーブル境界のためにインデックス計算に使用されない最高ビットの影響を組み込むことができます。

バケットの実際のフィッティングはgetNode(int, Object)方法で行われる：

first = tab[(n - 1) & hash] 

hashはhash(Object)とnの結果は、ハッシュテーブルの大きさです。