LinkedHashSet/LinkedHashMap

1. 什麼是 LinkedHashSet 與 LinkedHashMap？

在 Java 標準程式庫中，Set 與 Map 有多種實作。最知名的是 HashSet 與 HashMap。這些結構透過雜湊提供對元素的快速存取，但 在遍歷元素時不保證任何順序。當遍歷順序很重要時，LinkedHashSet 與 LinkedHashMap 就派上用場了。

• LinkedHashSet 是會記住元素插入順序的 Set。
• LinkedHashMap 是會記住鍵-值對插入順序（或可選擇改為存取順序）的 Map。

它們本質上與「普通的」HashSet/HashMap 類似，但另外用一個雙向連結串列來保存元素的順序。

2. 插入順序與存取順序

插入順序

預設情況下，LinkedHashSet 與 LinkedHashMap 保證在遍歷時（for-each/iterator），元素會 依照它們被加入的順序 返回。

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）。在建立映射時將建構子第三個參數設為 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。這對測試尤為重要——順序不會因為每次執行而「亂跳」。

穩定的測試

在單元測試中，常需要比較預期的集合與實際結果。若順序無法保證，測試可能會變得不穩定（flaky）。使用「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 vs 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：用 LinkedHashMap 做快取卻沒有覆寫 removeEldestEntry。
若要 LRU，必須覆寫 removeEldestEntry，否則映射會無限制地成長。

錯誤 3：沒有必要時仍使用 LinkedList 來實作佇列/堆疊。
在多數情況下，ArrayDeque 更快且更省資源。

錯誤 4：期望 LinkedHashMap 會排序。
LinkedHashMap 保留插入/存取順序，但不會依鍵排序。需要排序時請用 TreeMap。

錯誤 5：往 ArrayDeque 加入 null。
ArrayDeque 不支援元素 null——會拋出 NullPointerException。

錯誤 6：比較集合時忽略順序差異。
在比較 LinkedHashSet/LinkedHashMap 與一般的 HashSet/HashMap 時，請務必考量元素順序的不同。