HashMapの詳細解析

HashMapはJavaで最も広く使われるキーと値のコンテナの一つです。JDK 8以降、その底層構造は「配列 + 連結リスト + 赤黒木」の組み合わせになり、JavaコレクションフレームワークのコアコンポーネントとなりつつあるのはHashMapです。

主要フィールドはこのように抽象化できます：

Java

        public class HashMap<K, V> {
    transient Node<K, V>[] table;  // ハッシュバケット配列
    transient int size;            // キーと値のペアの数
    int threshold;                 // リサイズしきい値
    final float loadFactor;        // 負荷係数
}

各バケットには連結リストノードまたは赤黒木ノードが格納されます：

Java

        static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
}

ハッシュバケットとは何か

table を一列のスロットとして想像してください。各スロットが「バケット」です。

put(key, value) を呼び出すと、HashMapは：

キーのハッシュ値を計算する
ハッシュ値からバケットのインデックスを求める
そのバケットにキーと値のペアを格納する

バケットインデックスの計算式はおおよそ：

Java

        int index = hash & (table.length - 1);

剰余ではなくビット演算を使います。これには table.length が2のべき乗である必要があります。これがHashMapの容量が常に2のべき乗である理由です。

hash() メソッドは何をしているか

HashMapは key.hashCode() を直接使わず、「撹乱」ステップを加えます：

Java

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

上位16ビットと下位16ビットをXORすることで、ハッシュ値の上位ビットもバケットインデックス計算に参加させ、ハッシュ衝突を減らします。

これをしないと、多くの上位ビットパターンが & (n-1) で捨てられ、衝突が増えてしまいます。

ハッシュ衝突はどう解決されるか

異なるキーが同じバケットに割り当てられることがあります。これがハッシュ衝突です。

HashMapはチェイン法で解決します：

同じバケット内の複数エントリは連結リストでつながれる
JDK 8以降、リストの長さが8を超え、かつ配列の長さが64以上の場合、リストが赤黒木に変換される

メリット：

連結リストはシンプルで、衝突が少ないときのオーバーヘッドが小さい
リストが長くなるとルックアップはO(n)になるが、赤黒木ならO(log n)に抑えられる

赤黒木はノード数が <= 6 になると連結リストに戻ります。

put はどう動くか

map.put(key, value) の大まかな流れ：

Java

        public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putVal の内部ロジックの概要：

tableが空なら、まずリサイズで初期化する
バケットインデックスを計算する i = (n-1) & hash
バケットが空なら新しいノードを作ってそこに置く
バケットが空でない場合：
- 最初のノードのキーが同じなら、値を上書き
- 木のノードなら、木の挿入ロジックへ
- そうでなければリストを走査：一致するキーがあれば上書き、末尾まで見つからなければ追加
追加後にリスト長が >= 8 になったら、赤黒木への変換を検討
sizeがthresholdを超えたらリサイズを実行

get はどう動くか

map.get(key) の大まかな流れ：

Java

        public V get(Object key) {
    Node<K, V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode のロジック：

ハッシュからバケットインデックスを計算
バケットの最初のノードのキーが一致するか確認
一致しなければ、木か連結リストかを判断してそれぞれの検索ロジックへ

ハッシュが均一に分散されて衝突が少ない場合、getの時間計算量はO(1)に近づきます。

デフォルト容量と負荷係数

Java

        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

デフォルト初期容量：16
デフォルト負荷係数：0.75

リサイズしきい値（threshold）= 容量 × 負荷係数。

つまり、sizeが 16 × 0.75 = 12 を超えるとリサイズが発生します。

なぜ0.75なのか？

時間と空間のバランスを取った経験値です：

低すぎる（例：0.5）：衝突は少ないが、配列スペースが無駄になる
高すぎる（例：1.0）：スペース効率は高いが、衝突が増えてパフォーマンスが低下

0.75はこの2つの要素の妥当なバランスです。

リサイズはどのように行われるか

size > threshold のとき、resize() が発動します。

リサイズのコアロジック：

Java

        // 新しい容量は古い容量の2倍
int newCap = oldCap << 1;
int newThr = oldThr << 1;

リサイズ後、すべての既存ノードを新しいバケット位置に再配置する必要があります（rehash）。

JDK 8はrehashを最適化しています：

Java

        // ノードの新しい位置は2つのうちどちらか：
// 1. 元のインデックスと同じ
// 2. 元のインデックス + 旧容量
if ((e.hash & oldCap) == 0) {
    // 低位リスト（元のインデックス）
} else {
    // 高位リスト（元のインデックス + oldCap）
}

この最適化は2のべき乗の容量という特性を利用しており、ハッシュ値の1ビットを確認するだけで新しいバケットが決まります。完全なハッシュマッピングを再計算する必要がありません。

null キーはどう扱われるか

HashMapは null をキーとして許可しており、常にバケットインデックス0に配置されます：

Java

        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

キーが null の場合、hashは0を返し、バケットインデックスも0になります。

スレッド安全性

HashMapはスレッドセーフではありません。

並行して put を呼び出すと以下の問題が発生する可能性があります：

データの上書き（2つのスレッドが同じバケットに同時に書き込む）
JDK 7の環状リストによる無限ループ（JDK 8で修正済み）

スレッドセーフな代替手段：

Collections.synchronizedMap(map)：すべての操作をsynchronizedでラップ、シンプルだがスループットが低い
ConcurrentHashMap：JDK 8はCAS + synchronizedをバケットレベルで使用し、並行性がはるかに高い

実際の開発では、並行シナリオでは ConcurrentHashMap を使うことを推奨します。

Fonnpo

Spring フレームワーク完全ガイド

LinkedListの詳細解析

ArrayListの詳細解析