ArrayList・LinkedList・HashMap の内部構造 ── なぜ「使い分け」が必要なのか

「ArrayList と LinkedList はどう違いますか？」という質問に「ArrayList はインデックスアクセスが速い、LinkedList は挿入・削除が速い」と答えられる人は多い。でも「なぜ？」まで答えられる人は少ない。

なぜを知らないまま使い分けると、実際は LinkedList が遅い場面でも「挿入が速いはず」と思い込んで使ってしまう。

---

1. ArrayList の正体 ── 内部は配列

ArrayList は名前に “List” とあるが、内部実装は**配列（Object[]）**だ。

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

【ヒープ上の ArrayList オブジェクト】

┌─────────────────────────────────────────────┐
│ ArrayList                                   │
│ ├─ elementData: 0xC100 (配列への参照)       │
│ ├─ size: 3                                  │
│ └─ ...                                      │
└─────────────────────────────────────────────┘

0xC100 の Object[] 配列（実際はもっと大きい）:
┌───────┬───────┬───────┬───────┬───────┐
│ "A"   │ "B"   │ "C"   │ null  │ null  │
│ [0]   │ [1]   │ [2]   │ [3]   │ [4]   │
└───────┴───────┴───────┴───────┴───────┘
  0xD01   0xD02   0xD03  （空き容量）

各要素は「参照（アドレス）」が連続して並んでいる。String オブジェクト本体は別のヒープ領域にある。

インデックスアクセスが O(1) な理由

配列は先頭アドレス + インデックス × 要素サイズで任意の要素の位置が計算できる。

0xC100 + (2 × 8bytes) = 0xC110 → [2] 番目の要素のアドレス

計算一発でアドレスが出るため、インデックスがいくつでも同じ速さ（O(1)）でアクセスできる。

末尾への追加が（ほぼ）O(1) な理由・リサイズのコスト

list.add("D") は空きスロット（size の位置）に参照を書くだけなので速い。ただし配列が満杯になるとリサイズが発生する。

満杯時の add:
1. 現在の容量の約 1.5 倍の新しい配列を作成
2. 全要素をコピー（O(n)）
3. 新しい配列に新要素を追加

これが amortized O(1) と呼ばれる理由:
リサイズは稀にしか起きないため、平均コストは O(1) に収束する

最初から要素数がわかっているなら new ArrayList<>(expectedSize) で容量を指定するとリサイズを防げる。

中間への挿入・削除が O(n) な理由

list.add(1, "X"); // インデックス 1 に挿入

挿入前:  [A][B][C][ ][ ]
                ↑ ここに X を入れる

Step 1: [1] 以降を全部 1 つ後ろにシフト
         [A][ ][B][C][ ]
         
Step 2: [1] に X を書く
         [A][X][B][C][ ]

n 要素の List の中間に挿入すると、平均 n/2 要素のシフトが必要 → O(n)。

---

2. LinkedList の正体 ── ノードの連鎖

LinkedList は「前後のノードへのポインタを持つノード」が連なったデータ構造（双方向連結リスト）だ。

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");

【ヒープ上のノード構造】

LinkedList オブジェクト
├─ first → [Node A]
└─ last  → [Node C]

[Node A]         [Node B]         [Node C]
┌──────────┐    ┌──────────┐    ┌──────────┐
│ prev:null│    │ prev: A  │    │ prev: B  │
│ item: "A"│───►│ item: "B"│───►│ item: "C"│
│ next: B  │    │ next: C  │    │ next:null│
└──────────┘    └──────────┘    └──────────┘

各ノードがバラバラにヒープに存在し、互いのアドレスを持ち合っている。

先頭/末尾への挿入が O(1) な理由

list.addFirst("Z");

新しいノード Z を作る:
[Node Z]
├─ prev: null
├─ item: "Z"
└─ next: → [Node A]

LinkedList.first を Z に変更
Node A の prev を Z に変更

→ ポインタを 2 本付け替えるだけ → O(1)

配列のようにシフトが不要なのでどれだけ大きなリストでも O(1) で済む。

インデックスアクセスが O(n) な理由

list.get(500); // 500 番目の要素

LinkedList は先頭から 500 回 next を辿らないと 500 番目に到達できない。ランダムアクセスは O(n)。

LinkedList は実務でほぼ使われない

理論上「中間挿入が速い」のだが、実際のユースケースでは：

• ランダムアクセスが多い → ArrayList の圧勝
• 先頭/末尾への挿入だけ → ArrayDeque の方が速い（キャッシュ効率が良い）
• 中間挿入が本当に多い → そもそも設計を見直す

加えて、各ノードがバラバラにヒープに置かれるため CPU キャッシュ効率が悪い（連続メモリでないため L1/L2 キャッシュに乗りにくい）。実測では大抵 ArrayList の方が速い。

---

3. HashMap の正体 ── ハッシュ値とバケット

HashMap<String, Integer> map = new HashMap<>();
map.put("Alice", 30);
map.put("Bob", 25);

ハッシュ値とバケットの仕組み

put(key, value) の処理：

1. key.hashCode() を呼んでハッシュ値を計算
   "Alice".hashCode() → 例: 63281940

2. ハッシュ値 % バケット数 でバケットの位置を決定
   63281940 % 16 = 4 → バケット [4] に格納

3. バケット [4] に Entry（key・value のペア）を追加

【HashMap の内部構造（バケット配列 + エントリ）】

内部配列（バケット）: 初期サイズ 16
┌─────┬─────┬─────┬─────┬─────────────┬─────┐
│  0  │  1  │  2  │  3  │      4      │ ... │
└─────┴─────┴─────┴─────┴──────┬──────┴─────┘
                                │
                          [Entry]
                          ├─ key: "Alice"
                          ├─ value: 30
                          └─ next: → [Entry]
                                     ├─ key: "Dave"（ハッシュ衝突）
                                     ├─ value: 28
                                     └─ next: null

get が O(1) に近い理由

map.get("Alice")

1. "Alice".hashCode() % 16 = 4 → バケット [4] を直接参照（O(1)）
2. バケット [4] の Entry を順番に key.equals() で確認
   → "Alice" を発見 → 30 を返す

バケットを「直接特定」できるため、リストのように先頭から探す必要がない。

ハッシュ衝突と load factor

異なるキーが同じバケットに入ることを**衝突（Collision）**と呼ぶ。衝突が多いとバケット内のリストが長くなり、O(1) から O(n) に近づく。

衝突を減らすため、load factor（デフォルト 0.75）が使われる。エントリ数がバケット数 × 0.75 を超えると、バケット数を 2 倍に拡張して全エントリを再配置（リハッシュ）する。

バケット数 16 × 0.75 = 12
→ 12 個目のエントリを追加するとき、バケット数を 32 に拡張してリハッシュ

Java 8 以降は衝突が多いバケット（8 個以上）は赤黒木に変換され、最悪でも O(log n) になる。

equals と hashCode の契約

// 絶対に守らないといけないルール
a.equals(b) が true  →  a.hashCode() == b.hashCode() でなければならない

HashMap は「同じキー」かを「まずハッシュ値で絞り込み、次に equals で確認」する。hashCode() が違えば別のバケットを見てしまい、equals が true でも「見つからない」ことになる。

// equals をオーバーライドしたのに hashCode をしていないと：
Set<Person> set = new HashSet<>();
Person p1 = new Person("Alice", 30);
set.add(p1);

Person p2 = new Person("Alice", 30); // p1.equals(p2) = true としたとして
set.contains(p2); // false になる可能性がある（hashCode が違うバケットを見るため）

これが「equals() をオーバーライドしたら hashCode() も合わせる」の正体だ。

---

4. 各コレクションの選び方

※ ArrayList は稀にリサイズあり、LinkedList の中間挿入は位置特定が O(n)、HashMap は衝突次第

実務でのシンプルな指針：

• 読み取り中心・ランダムアクセス → ArrayList
• スタック・キューとして使う → ArrayDeque
• キーで値を引く → HashMap（順序不要）、LinkedHashMap（挿入順）、TreeMap（キーソート）
• 重複なしの集合 → HashSet（順序不要）、TreeSet（ソート順）
• LinkedList が最適な場面は実務ではほぼない

---

まとめ