HashMapの基本特性
HashMapはハッシュテーブルを基盤としたMapインターフェースの実装であり、キーと値のペアを格納する。非同期処理を前提としているためスレッドセーフではなく、キーと値の両方にnullを許容する。また、要素の格納順序は保証されない。
JDK 1.8以降、データ構造は大幅に改善された。以前は「配列＋リスト」で構成されていたが、衝突（ハッシュ値が同一になり配列のインデックスが重複すること）が多発した際のパフォーマンス低下を防ぐため、「配列＋リスト＋赤黒木」へと進化した。リストの長さが閾値（デフォルト8）を超え、かつ配列の長さが64以上の場合に、そのインデックスのデータ構造が赤黒木に変換される。
補足として、リスト長が8を超えても配列長が64に満たない場合は赤黒木化されず、配列のリサイズ（拡張）が優先される。これは、配列が小さい段階でツリー化を行うと、平衡維持のための回転や色変更操作がかえってオーバーヘッドとなり、逆に効率が悪化するためである。したがって、検索効率の最適化のために、配列長が十分に確保された段階で初めてツリー化が行われる。
データ構造と格納プロセス
ハッシュ衝突の解決
二つの異なるオブジェクトが同じハッシュコードを返す現象をハッシュ衝突と呼ぶ。HashMapでは以下のアプローチで対処する。
- キーのハッシュコードが同一場合、
equalsメソッドで内容を比較する。 - 内容も同一であれば、既存の値を上書きする。
- 内容が異なる場合は、リストの末尾にノードを追加する。リスト長が閾値を超えれば赤黒木へ変換する。
リサイズのタイミング
要素数が「配列長 × 負荷係数」の閾値に達し、かつ追加先のバケットが空でない場合、配列は現在の2倍の容量に拡張され、既存のデータが再配置される。
容量が2の累乗である理由
HashMapの初期容量や拡張後の容量は必ず2の累乗になるよう設計されている。これは、ハッシュ値から配列のインデックスを計算する際に剰余演算（hash % length）の代わりにビット論理積演算（hash & (length - 1)）を用いるためである。
配列長が2の累乗である場合、length - 1は全ビットが1となる。例えば長さ16の場合、15は2進数で1111となる。この場合、hash & 1111はハッシュ値の下位4ビットをそのままインデックスとして採用するため、均一な分散が期待できる。仮に長さが2の累乗でない（例：9）とすると、length - 1は1000となり、特定のビットパターンのハッシュ値しかインデックスとして採用されず、衝突が頻発してしまう。
また、コンストラクタで2の累乗ではない値が指定された場合、内部のcalculatePowerOfTwoメソッド（概念的実装）により、指定値以上の最小の2の累乗に変換される。
static int calculatePowerOfTwo(int targetSize) {
int adjusted = targetSize - 1;
adjusted |= adjusted >>> 1;
adjusted |= adjusted >>> 2;
adjusted |= adjusted >>> 4;
adjusted |= adjusted >>> 8;
adjusted |= adjusted >>> 16;
return (adjusted < 0) ? 1 : (adjusted >= MAX_LIMIT) ? MAX_LIMIT : adjusted + 1;
}ツリー化の閾値が8である理由
リストから赤黒木への変換閾値が8に設定されているのは、確率論に基づく。負荷係数0.75の条件下で、理想的なハッシュ関数が用いられた場合、バケット内のリスト長が特定の長さkになる確率はポアソン分布に従う。長さ8に達する確率は約0.00000006（千万分の6）であり、極めてレアケースである。
赤黒木のノードは通常のノードの約2倍のメモリを消費するため、頻繁にツリー化を行うことは空間的オーバーヘッドの増大を招く。そのため、めったに起こり得ない深刻なハッシュ衝突が発生した場合のみ、時間的効率を優先してツリー構造に切り替えるというトレードオフの結果が8という数値である。なお、削除等でノード数が6以下になると、再びリスト構造に戻る。
メンバ変数とコンストラクタ
- DEFAULT_INITIAL_CAPACITY (16): デフォルトの初期容量。
- DEFAULT_LOAD_FACTOR (0.75f): デフォルトの負荷係数。容量の使い切りを防ぎつつ、メモリの無駄遣いを抑えるバランス値。
- threshold: 拡張を行う境界値（容量 × 負荷係数）。
初期化時に格納予定の要素数が分かっている場合、無駄なリサイズを防ぐために初期容量を適切に設定することが推奨される。要素数nを格納する場合、n / 0.75f + 1.0fを初期容量として指定することで、要素追加時のリサイズを回避できる。
要素の追加: putとハッシュ計算
キーのハッシュ値は、単にhashCode()を呼び出すだけでなく、摂動関数を用いて計算される。
static int computeDisturbedHash(Object key) {
int code;
return (key == null) ? 0 : (code = key.hashCode()) ^ (code >>> 16);
}これは、上位16ビットと下位16ビットのXORを取ることで、配列長が小さい場合でもハッシュ値の上位ビットの影響をインデックス計算に反映させ、衝突を緩和するためである。
putValの処理フロー
- 配列が未初期化なら
resize()を実行し、初期配列を生成。 - インデックス
(length - 1) & hashのバケットが空なら、新規ノードを挿入。 - バケットに既にノードが存在する場合：
- キーが同一であれば値を上書き。
- ノードが
TreeNodeなら赤黒木として挿入処理。 - リスト構造なら末尾まで探索し、重複キーがなければ追加。リスト長が閾値に達すれば
treeifyBinを呼び出す。
- 要素数が閾値を超えた場合、リサイズを実行。
リサイズと再ハッシュの最適化
拡張時、単に全要素のハッシュを再計算するのではなく、元の配列長を使ったビット演算で高速に再配置を行う。容量が2倍になると、インデックスを決定するビットマスクに新たに1ビット追加される。
この新しいビットが0の場合は元のインデックス、1の場合は「元のインデックス + 旧配列長」に移動する。この仕組みにより、再ハッシュの計算コストを大幅に削減しつつ、衝突していたノードを新旧のバケットに均等に分散させることができる。
要素の取得と削除
要素取得（get）および削除（remove）は、まずハッシュ値からバケットを特定し、バケット内の構造に応じて処理を分岐する。
- リスト構造の場合、先頭から順次探索を行う。
- 赤黒木構造の場合、二分探索に近い形で高速に探索（O(log n)）を行う。
削除処理において、赤黒木のノード数が閾値（6）を下回った場合は、再度リスト構造に変換される。
マップの反復処理
HashMapのデータを走査する主な方法は以下の通りである。
Map<String, Integer> inventory = new HashMap<>();
inventory.put("melon", 8);
inventory.put("berry", 12);
// エントリセットを用いたイテレータ（推奨）
Iterator<Map.Entry<String, Integer>> it = inventory.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<String, Integer> entry = it.next();
System.out.println(entry.getKey() + ":" + entry.getValue());
}
// JDK 8以降のforEach（推奨）
inventory.forEach((item, count) -> {
System.out.println(item + " - " + count);
});
// keySetを用いたgetの呼び出し（非推奨：二重ループとなるためパフォーマンスが低下）
for (String item : inventory.keySet()) {
inventory.get(item);
}