如何深入解讀LinkedHashMap原理和源碼

# 如何深入解讀LinkedHashMap原理和源碼

## 一、LinkedHashMap概述

LinkedHashMap是Java集合框架中一個重要的實現類，它繼承自HashMap，在HashMap的基礎上通過維護一個雙向鏈表來保證元素的插入順序或訪問順序。與HashMap的純哈希表結構不同，LinkedHashMap通過結合哈希表和鏈表的優勢，提供了可預測的迭代順序。

### 1.1 核心特性
- **有序性**：默認保持插入順序（accessOrder=false），可配置為訪問順序（LRU模式）
- **性能平衡**：查找效率O(1)，略低于HashMap但遠優于TreeMap
- **繼承關系**：`java.util.LinkedHashMap` → `java.util.HashMap` → `java.util.AbstractMap`

### 1.2 典型應用場景
- 需要保持插入順序的緩存系統
- 實現LRU（最近最少使用）緩存策略
- 需要有序鍵值對且不頻繁修改的場景

## 二、數據結構解析

### 2.1 底層存儲結構
```java
// 繼承HashMap的Node并添加雙向指針
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);
    }
}

LinkedHashMap在HashMap的數組+鏈表/紅黑樹結構基礎上，額外維護了一個雙向鏈表： - 頭節點：transient LinkedHashMap.Entry<K,V> head - 尾節點：transient LinkedHashMap.Entry<K,V> tail

2.2 兩種排序模式

1. 插入順序（默認）：

   public LinkedHashMap(int initialCapacity, float loadFactor) {
      super(initialCapacity, loadFactor);
      accessOrder = false; // 關鍵參數
   }
   

2. 訪問順序（LRU）：

   public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
      super(initialCapacity, loadFactor);
      this.accessOrder = accessOrder; // 設置為true
   }
   

三、核心源碼解析

3.1 節點訪問邏輯

訪問節點時的順序維護（get()方法）：

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder) // 如果為訪問順序模式
        afterNodeAccess(e); // 將被訪問節點移到鏈表尾部
    return e.value;
}

afterNodeAccess()方法實現：

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
        // 從鏈表中移除節點p
        LinkedHashMap.Entry<K,V> b = p.before, a = p.after;
        p.after = null;
        if (b == null) head = a;
        else b.after = a;
        
        if (a != null) a.before = b;
        else last = b;
        
        // 將p插入到鏈表尾部
        if (last == null) head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

3.2 插入操作處理

插入節點時的鉤子方法（覆蓋HashMap的newNode()）：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p); // 將新節點鏈接到鏈表尾部
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

3.3 刪除操作處理

刪除節點后的處理（afterNodeRemoval()）：

void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
    LinkedHashMap.Entry<K,V> b = p.before, a = p.after;
    p.before = p.after = null; // 清理指針
    
    if (b == null) head = a;
    else b.after = a;
    
    if (a == null) tail = b;
    else a.before = b;
}

四、LRU緩存實現原理

4.1 移除最老元素機制

通過覆蓋removeEldestEntry()方法實現：

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false; // 默認不刪除
}

// 典型LRU緩存實現示例
final int MAX_ENTRIES = 100;
LinkedHashMap<Integer, String> cache = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }
};

4.2 完整LRU工作流程

1. 新元素插入時自動追加到鏈表尾部
2. 元素被訪問時移動到尾部（當accessOrder=true）
3. 當容量超過閾值時，自動移除鏈表頭部元素

五、迭代器實現

5.1 關鍵迭代器類

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    
    LinkedHashIterator() {
        next = head; // 從頭節點開始
        expectedModCount = modCount;
    }
    
    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after; // 通過after指針遍歷
        return e;
    }
    // ... 其他方法省略
}

5.2 三種視圖迭代器

1. KeyIterator：繼承LinkedHashIterator實現Iterator<K>
2. ValueIterator：繼承LinkedHashIterator實現Iterator<V>
3. EntryIterator：繼承LinkedHashIterator實現Iterator<Map.Entry<K,V>>

六、性能分析與對比

6.1 時間復雜度對比

6.2 內存占用比較

• LinkedHashMap比HashMap多維護一個雙向鏈表，每個Entry多存儲兩個指針
• 典型內存消耗（64位JVM）：
  • HashMap.Entry：24字節
  • LinkedHashMap.Entry：40字節（增加16字節）

七、實戰注意事項

7.1 線程安全問題

與HashMap相同，LinkedHashMap非線程安全，多線程環境下應該：

Map<String, Object> safeMap = Collections.synchronizedMap(
    new LinkedHashMap<>(16, 0.75f, true));

7.2 初始化參數建議

1. 預估容量避免頻繁擴容：

   // 預期存儲100元素，0.75負載因子
   new LinkedHashMap<>( (int)(100/0.75)+1, 0.75f )
   

2. 訪問順序模式下的并發修改異常：

   // 迭代過程中訪問元素會觸發modCount變化
   for(Key key : map.keySet()) {
      map.get(key); // 拋出ConcurrentModificationException
   }
   

八、總結與進階思考

LinkedHashMap通過精巧的雙向鏈表設計，在幾乎不損失HashMap性能優勢的前提下實現了有序性。理解其實現原理有助于：

1. 更合理地選擇Map實現類
2. 實現高效的LRU緩存策略
3. 深入理解Java集合框架的設計思想

擴展思考：如何基于LinkedHashMap實現一個支持過期時間的緩存系統？（提示：結合定時任務清理機制） “`