LinkedHashMap 是 HashMap 的子類，內部維護一個雙向鏈表，保證迭代順序。支持兩種順序模式：
get/put 訪問後移至末尾，適合 LRU 緩存// 插入順序（4 個構造方法）
public LinkedHashMap()
public LinkedHashMap(int initialCapacity)
public LinkedHashMap(int initialCapacity, float loadFactor)
public LinkedHashMap(Map<? extends K, ? extends V> m)
// 訪問順序（唯一構造方法）
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
// accessOrder=true 啟用訪問順序
Map<String,Integer> map = new LinkedHashMap<>();
map.put("c", 100);
map.put("d", 200);
map.put("a", 500);
map.put("d", 300); // 修改不影響順序
// 輸出: c=100, d=300, a=500
應用場景：配置文件去重保留最後值且保持原序、購物車按加入順序展示、SQL ORDER BY 預排序後入 Map 避免 TreeMap 開銷。
Map<String,Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("c", 100);
map.put("d", 200);
map.put("a", 500);
map.get("c"); // 訪問 c 移至末尾
map.put("d", 300); // 訪問 d 移至末尾
// 輸出: a=500, c=100, d=300
LRU（Least Recently Used）：最近最少使用淘汰策略。LinkedHashMap 提供 removeEldestEntry 鉤子方法：
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false; // 默認不限制容量
}
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int maxEntries;
public LRUCache(int maxEntries) {
super(16, 0.75f, true); // 訪問順序
this.maxEntries = maxEntries;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxEntries; // 超容量淘汰最久未訪問
}
}
LRUCache<String,Object> cache = new LRUCache<>(3);
cache.put("a", "abstract");
cache.put("b", "basic");
cache.put("c", "call");
cache.get("a"); // 訪問 a
cache.put("d", "call"); // 容量超限，淘汰 b
System.out.println(cache); // {c=call, a=abstract, d=call}
transient Entry<K,V> header; // 雙向鏈表頭哨兵節點
final boolean accessOrder; // 順序模式標誌
static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after; // 雙向鏈表指針
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>) m;
if (lm.accessOrder) {
lm.modCount++;
remove(); // 從當前位置移除
addBefore(lm.header); // 移至鏈表末尾（header.before）
}
}
void recordRemoval(HashMap<K,V> m) {
remove(); // 從鏈表移除
}
}
init()：初始化 header 指向自身，形成空鏈表createEntry()：新節點插入哈希表並 addBefore(header) 入鏈表尾addEntry()：調用父類後檢查 removeEldestEntry 淘汰get()：命中後調用 recordAccess 調整順序containsValue()：利用鏈表遍歷，比 HashMap 數組遍歷更高效LinkedHashSet 內部基於 LinkedHashMap，保持插入順序：
Set<String> set = new LinkedHashSet<>();
set.add("b"); set.add("c"); set.add("a"); set.add("c");
// 輸出: [b, c, a]
| 特性 | LinkedHashMap | HashMap | TreeMap |
|---|---|---|---|
| 順序 | 插入/訪問序 | 無序 | 鍵自然序/定制序 |
| 底層 | 數組+鏈表+雙向鏈表 | 數組+鏈表 | 紅黑樹 |
| get/put 複雜度 | O(1) | O(1) | O(log n) |
| 典型用途 | LRU、有序配置 | 通用映射 | 有序遍歷、範圍查詢 |
掌握 LinkedHashMap 的雙向鏈表機制與 removeEldestEntry 擴展點，能輕鬆實現高效 LRU 緩存與有序映射需求。
