内部構造：配列＋連結リスト＋赤黒木
主要なポイント
- ハッシュ関数の攪乱処理
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
このメソッドは、keyのハッシュ値に対して攪乱処理を行う。上位16ビットはそのまま保持し、下位16ビットと上位16ビットの排他的論理和（XOR）を計算し、その結果を下位16ビットに設定する。この処理により、配列の長さが短い場合の衝突を減らすことを目的としている。
- 格納位置の計算
index = hash & (length - 1)
これは実質的にhash % lengthと同じ意味を持つが、ビット演算のほうが計算効率が良い。この式が成立するためには、lengthが2のべき乗でなければならない。
- 要素追加メソッド
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
- 再ハッシュ（リサイズ）メソッド
final Node<K,V>[] resize()
リサイズの主な理由は、要素数が増加した際に検索速度がO(1)からO(n)に低下するためであり、連結リスト化が進むと検索効率が悪化する。そのため、再ハッシュによって配列を拡張する。
初期化時のリサイズ:
初期容量が指定されていない場合、デフォルト値として容量16とリサイズ閾値12（16×0.75）を設定。
初期容量が指定されている場合、tableSizeForメソッドを使って、指定された値以上の2のべき乗値を求める。
非初期化時のリサイズ: 配列サイズとリサイズ閾値がそれぞれ2倍になる。
連結リストの分割処理
リサイズ後、配列の長さが2倍になるため、連結リスト内の要素の格納位置を再計算する。その結果、リストは2つの部分に分割される。一方は元の位置に残り、他方は「元の位置＋元の配列長」の新しい位置に移動する。
tableSizeForメソッド
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
このメソッドは、入力された値以上の最小の2のべき乗値を返す。例えば、8を入力すると8を返し、9を入力すると16を返す。
- 赤黒木への変換条件
バケット内の要素数が8以上 ハッシュテーブル全体のサイズが64以上
- 赤黒木からの逆変換条件
バケット内の要素数が6以下