LinkedHashMap 详解

🧱 先理解 HashMap vs LinkedHashMap

HashMap:
┌─────────────────────────────┐
│  bucket[0] → (3, "c")       │  // 无序！
│  bucket[1] → (1, "a")       │
│  bucket[2] → (2, "b")       │
└─────────────────────────────┘

LinkedHashMap = HashMap + 双向链表:
┌─────────────────────────────┐
│  bucket[0] → (3, "c")       │
│  bucket[1] → (1, "a")       │  // 存储同 HashMap
│  bucket[2] → (2, "b")       │
└─────────────────────────────┘
         ↕ 额外维护一条双向链表
    [头head] ⇄ (1,"a") ⇄ (2,"b") ⇄ (3,"c") ⇄ [尾tail]
               最旧                              最新

---

🔑 构造方法的 3 个参数

new LinkedHashMap<>(capacity, loadFactor, accessOrder)
//                  初始容量   负载因子     排序模式

第 3 个参数 accessOrder 是关键！

// accessOrder = false（默认）：按插入顺序排列
LinkedHashMap<Integer, String> map1 = new LinkedHashMap<>();
map1.put(1, "a");
map1.put(2, "b");
map1.put(3, "c");
map1.get(1);  // 访问1，但顺序不变
// 遍历结果：1, 2, 3  （插入顺序）

// accessOrder = true：按访问顺序排列（LRU核心！）
LinkedHashMap<Integer, String> map2 = new LinkedHashMap<>(16, 0.75f, true);
map2.put(1, "a");
map2.put(2, "b");
map2.put(3, "c");
map2.get(1);  // 访问1，1被移到最后
// 遍历结果：2, 3, 1  （1最近访问，排最后）
//           ↑最旧        ↑最新

---

🎬 accessOrder=true 时，链表如何变化

初始放入 1, 2, 3：
head ⇄ [1] ⇄ [2] ⇄ [3] ⇄ tail
        最旧              最新

执行 map.get(1)，访问了1：
head ⇄ [2] ⇄ [3] ⇄ [1] ⇄ tail
        最旧              最新（1被移到尾部）

执行 map.get(2)，访问了2：
head ⇄ [3] ⇄ [1] ⇄ [2] ⇄ tail
        最旧              最新

---

🔧 removeEldestEntry 方法详解

LinkedHashMap<Integer, Integer> lru = new LinkedHashMap<>(capacity, 0.75f, true) {
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        // 每次 put 之后，LinkedHashMap 都会调用这个方法
        // eldest = 链表头部节点 = 最久未访问的那个
        // 返回 true  → 自动删除 eldest（触发淘汰）
        // 返回 false → 不删除
        return size() > capacity;
    }
};

调用时机：

lru.put(1, 1);  // size=1, 1>3? 否 → 不淘汰
lru.put(2, 2);  // size=2, 2>3? 否 → 不淘汰
lru.put(3, 3);  // size=3, 3>3? 否 → 不淘汰
lru.put(5, 5);  // size=4, 4>3? 是 → 淘汰头部最旧节点！

---

🎯 完整 LRU 模拟代码

public class LRUDemo {
    public static void main(String[] args) {
        int capacity = 3;
        
        // accessOrder=true 是 LRU 的核心
        LinkedHashMap<Integer, Integer> lru = 
            new LinkedHashMap<>(capacity, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                    return size() > capacity;
                }
            };
        
        int[] pages = {1, 3, 2, 1, 2, 1, 5, 1, 2, 3};
        int pageFaults = 0;
        
        for (int page : pages) {
            if (!lru.containsKey(page)) {
                // 缺页：不在内存中
                pageFaults++;
                lru.put(page, page); // put 后自动触发 removeEldestEntry
                System.out.printf("缺页[%d] → 书架: %s%n", page, lru.keySet());
            } else {
                // 命中：在内存中，get 会更新访问顺序（移到链表尾部）
                lru.get(page);
                System.out.printf("命中[%d] → 书架: %s%n", page, lru.keySet());
            }
        }
        System.out.println("总缺页次数：" + pageFaults); // 输出：5
    }
}

输出结果：

缺页[1] → 书架: [1]
缺页[3] → 书架: [1, 3]
缺页[2] → 书架: [1, 3, 2]
命中[1] → 书架: [3, 2, 1]   ← 1被移到尾部
命中[2] → 书架: [3, 1, 2]   ← 2被移到尾部
命中[1] → 书架: [3, 2, 1]   ← 1被移到尾部
缺页[5] → 书架: [2, 1, 5]   ← 3被淘汰（头部，最旧）
命中[1] → 书架: [2, 5, 1]
命中[2] → 书架: [5, 1, 2]
缺页[3] → 书架: [1, 2, 3]   ← 5被淘汰（头部，最旧）
总缺页次数：5

---

📌 核心结构总结

LinkedHashMap 内部同时维护两套结构：

1. HashMap 数组（快速查找，O(1)）
   bucket[] → 判断页面是否在内存中

2. 双向链表（维护访问顺序）
   head ⇄ ... ⇄ tail
   最旧              最新
   ↑淘汰这里          ↑新访问插入这里

两者配合 = 既能 O(1) 查找，又能 O(1) 维护LRU顺序

💡 这也是 LeetCode 146题 「LRU缓存」的标准面试答案！
面试中能手写这个实现，绝对是加分项 ✨

参考：

1. LeetCode LRU缓存