LinkedHashSet/LinkedHashMap

1. LinkedHashSet と LinkedHashMap とは？

Java の標準ライブラリには、Set と Map のいくつかの実装があります。最もよく知られているのは HashSet と HashMap です。これらはハッシュによる高速な要素アクセスを提供しますが、要素の走査時の順序は一切保証しません。走査順が重要なときは、LinkedHashSet と LinkedHashMap が役立ちます。

• LinkedHashSet は、要素の追加順を記憶する Set です。
• LinkedHashMap は、キーと値のペアの追加順（または必要に応じてアクセス順）を記憶する Map です。

実装は「通常の」HashSet/HashMap とほぼ同じですが、要素の順序を保持するために双方向連結リストが追加されています。

2. 挿入順とアクセス順

挿入順序

デフォルトでは、LinkedHashSet と LinkedHashMap は、for-each/イテレータでの走査時に、追加した順序で要素を返すことを保証します。

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
for (String s : set) {
    System.out.println(s);
}
// 出力: A B C

Map<Integer, String> map = new LinkedHashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
for (Integer key : map.keySet()) {
    System.out.println(key + " -> " + map.get(key));
}
// 出力: 1 -> one, 2 -> two, 3 -> three

アクセス順（LinkedHashMap のみ）

LinkedHashMap には、最後にアクセスした順（access order）のモードがあります。マップ作成時にコンストラクタの第 3 引数に true を渡すと、要素へのアクセス（get/put）のたびに、その要素がリストの末尾へ移動します。

Map<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);
lruMap.put(1, "one");
lruMap.put(2, "two");
lruMap.put(3, "three");

lruMap.get(2); // キー 2 にアクセス

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// 出力: 1 3 2 (2 は最後。アクセスされたため)

removeEldestEntry による LRU キャッシュ

LinkedHashMap の最大の特徴は、LRU キャッシュ（Least Recently Used、「最も最近使われていない」）を簡単に実装できることです。メソッド removeEldestEntry(Map.Entry<K,V> eldest) をオーバーライドするだけで、これが true を返した場合に新規追加時、最も「古い」要素が削除されます。

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true = アクセス順序
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// 使用例:
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // 1 を一番 "新しい" 状態にする
cache.put(4, "four"); // 2 が削除される（最も古い）
System.out.println(cache.keySet()); // [3, 1, 4]

3. メモリと速度のコスト: LinkedHashSet/LinkedHashMap vs HashSet/HashMap

内部構造

内部は通常の HashSet/HashMap とほぼ同じですが、各要素が双方向連結リストにも保持されます。この追加の構造が挿入順/アクセス順を「記憶」します。

メモリのコスト

各ノードが prev/next 参照を持つため、必要なメモリは増えます。数百万要素では顕著ですが、一般的な用途では決定的な順序のための妥当な対価です。

速度のコスト

追加/検索/削除といった基本操作は、償却的にO(1)のままです。イテレーションはリストをたどる分わずかに遅くなりますが、多くの場合差は最小限です。また「最も古い要素を削除する」（LRU）というシナリオは非常に効率的に実現できます。なぜなら「最古」の要素は常にリストの先頭にあるからです。

まとめ: 順序が重要なら LinkedHashSet/LinkedHashMap を選びましょう。メモリを節約したく、順序が不要なら HashSet/HashMap で十分です。

4. キャッシュ、決定的な出力、安定したテスト

キャッシュ（LRU）

LinkedHashMap は、サイズ制限と「古い」要素の自動削除を備えたキャッシュの基盤として最適です。各種ライブラリ/フレームワーク、ファイルや画像、計算結果の管理などで利用されます。

決定的な出力

レポート、エクスポート、シリアライズなど、データの表現が予測可能であることが重要な場合は、LinkedHashSet/LinkedHashMap を使いましょう。特にテストでは重要で、実行のたびに順序が揺れません。

安定したテスト

ユニットテストでは、期待されるコレクションと得られたコレクションを比較することがよくあります。順序が保証されないと、テストが不安定になります（フレークします）。「Linked」系の実装なら、決定性が安定性をもたらします。

例: HashMap と LinkedHashMap の比較

Map<Integer, String> hashMap = new HashMap<>();
Map<Integer, String> linkedMap = new LinkedHashMap<>();

for (int i = 1; i <= 5; i++) {
    hashMap.put(i, "val" + i);
    linkedMap.put(i, "val" + i);
}

System.out.println(hashMap.keySet());   // 順序は任意になり得る！
System.out.println(linkedMap.keySet()); // 常に 1, 2, 3, 4, 5

5. キュー用途における LinkedList と ArrayDeque

LinkedList

• インターフェース List、Deque、Queue を実装。
• 双方向連結リスト: 先頭と末尾での挿入/削除が高速。
• キュー（FIFO）、スタック（LIFO）、両端キューとして利用可能。

ArrayDeque

• Deque、Queue を実装（ただし List ではない）。
• 配列ベースで自動的に拡張される。
• キュー/スタック操作では多くの場合 LinkedList より高速で、オーバーヘッドが小さい。
• 要素 null はサポートしない。

どちらをいつ使うべきか？

• キューとスタック — ほぼ常に ArrayDeque。
• 中間での挿入/削除が多い うえにリストも必要 — LinkedList。
• 順序を持つ Set/Map — LinkedHashSet/LinkedHashMap。

例: タスクキュー

Queue<String> queue = new ArrayDeque<>();
queue.add("task1");
queue.add("task2");
System.out.println(queue.poll()); // task1

例: スタック

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop()); // second

まとめ:
— キューとスタックには ArrayDeque。
— 中間への頻繁な挿入があるリストには LinkedList。
— 順序を持つ Set/Map には LinkedHashSet/LinkedHashMap。

6. LinkedHashSet/LinkedHashMap を扱うときのよくあるミス

誤り №1: HashSet/HashMap が順序を保持すると期待する。
HashSet/HashMap は順序を保証しません。順序が重要なら LinkedHashSet/LinkedHashMap を使いましょう。

誤り №2: removeEldestEntry をオーバーライドせずにキャッシュ用途で LinkedHashMap を使う。
LRU には removeEldestEntry をオーバーライドする必要があります。そうしないとマップは無制限に増大します。

誤り №3: 不要なのにキュー/スタックに LinkedList を使う。
ほとんどのケースでは ArrayDeque の方が高速で省メモリです。

誤り №4: LinkedHashMap にソートを期待する。
LinkedHashMap は挿入順/アクセス順を保持しますが、キーでのソートはしません。ソートには TreeMap を使いましょう。

誤り №5: ArrayDeque に null を追加する。
ArrayDeque は null 要素をサポートせず、NullPointerException になります。

誤り №6: 順序を考慮せずにコレクションを比較する。
LinkedHashSet/LinkedHashMap と通常の HashSet/HashMap を比較する際は、要素の順序の違いに注意してください。