Java 集合深度解析：LinkedHashMap 原理、源碼與 LRU 緩存實戰

LinkedHashMap 深度解析：有序 Map 的雙重身份與 LRU 緩存最佳實踐

LinkedHashMap 是 Java 集合框架中極具特色的成員：它同時擁有 HashMap 的高效查找與 LinkedList 的有序特性，完美解決「既要 O(1) 查找，又要保持插入/訪問順序」的工程難題。本文將從 Entry 結構、初始化機制、存取邏輯、排序模式四個維度深度剖析源碼（基於 JDK 8），並展示如何用 10 行代碼實現生產級 LRU 緩存。

核心特性速覽

• 繼承 HashMap，底層仍是「數組 + 鏈表/紅黑樹」
• 新增雙向鏈表維護順序：head（最舊）⇄ tail（最新）
• 兩種順序模式：插入順序（默認）與 訪問順序（accessOrder=true）
• 非線程安全，併發場景需外部同步或用 Collections.synchronizedMap

1. Entry 節點：雙向鏈表的關鍵

LinkedHashMap 重新定義了靜態內部類 Entry<K,V>，在繼承 HashMap.Node<K,V> 基礎上新增 before、after 兩個引用：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;  // 雙向鏈表指針
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

鏈表頭尾由 head、tail 兩個哨兵節點標記（JDK 8 中合併為 header 環狀結構），實現 O(1) 頭尾插入刪除。

2. 初始化：構造器鏈與 init() 回調

所有構造器最終委派給 HashMap(int capacity, float loadFactor)，並將 accessOrder 設為 false（插入順序）。關鍵在於重寫 init()：

void init() {
    header = new Entry<>(-1, null, null, null);
    header.before = header.after = header; // 環狀雙向鏈表初始化
}

此處利用 HashMap 構造器末尾調用 init() 的模板方法模式，完成鏈表骨架搭建。

3. 存儲機制：重寫 addEntry / createEntry

put() 邏輯復用父類，關鍵差異在 createEntry 與 addEntry：

void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Node<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    e.addBefore(header);          // 關鍵：插入雙向鏈表尾部（header 前）
    size++;
}

private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

addEntry 還肩負「刪除最舊條目」職責（配合 removeEldestEntry 實現 LRU）：

void addEntry(int hash, K key, V value, int bucketIndex) {
    createEntry(hash, key, value, bucketIndex);
    Entry<K,V> eldest = header.after;           // 鏈表頭 = 最舊
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    } else if (size >= threshold) {
        resize(2 * table.length);
    }
}

4. 讀取機制：recordAccess 實現訪問順序遷移

重寫 get()，命中後調用 e.recordAccess(this)：

public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>) getEntry(key);
    if (e == null) return null;
    e.recordAccess(this);  // 關鍵：訪問順序模式下移動到鏈表尾
    return e.value;
}

void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>) m;
    if (lm.accessOrder) {              // 僅訪問順序模式生效
        lm.modCount++;
        remove();                      // 從原位置斷開
        addBefore(lm.header);          // 插入尾部（最新）
    }
}

鏈表移動屬 O(1) 操作，不影響 get 時間複雜度。

5. 排序模式：accessOrder 決定行為

構造訪問順序 Map：new LinkedHashMap<>(16, 0.75f, true)

6. LRU 緩存實戰：重寫 removeEldestEntry

只需繼承並覆蓋一個方法，即得生產級 LRU 緩存：

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

    public LRUCache(int maxCapacity) {
        super(maxCapacity, 0.75f, true); // 關鍵：啟用訪問順序
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity;     // 超容量即淘汰最舊（鏈表頭）
    }
}

// 使用示例
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "A"); cache.put(2, "B"); cache.put(3, "C");
cache.get(1);            // 訪問 1，順序變為 2,3,1
cache.put(4, "D");       // 觸發淘汰，移除鏈表頭 2
// 當前緩存：3,1,4

7. 並發陷阱與替代方案

• 非線程安全：多線程寫入會導致鏈表指針錯亂、size 不一致
• 方案一：Collections.synchronizedMap(new LRUCache<>(100))，鎖粒度粗，高併發性能差
• 方案二（推薦）：Caffeine 或 Guava Cache，基於 W-TinyLFU 算法，高併發、高命中率、支援過期/刷新策略
• 方案三：JDK 10+ 可用 ConcurrentHashMap + 自定義雙向隊列，但實現複雜度高

總結

LinkedHashMap 通過「雜湊表 + 雙向鏈表」雙重結構，優雅地統一了高效查找與有序遍歷。其 accessOrder 機制配合 removeEldestEntry 鉤子，使 LRU 緩存實現極為簡潔。理解其源碼設計，不僅能應對面試高頻考點，更能在業務中靈活應對「有序去重」、「最近使用追蹤」等場景。下一篇我們將深入剖析 HashMap 的擴容機制與 hash 算法演進。