问题

20. LinkedHashMap 在 LRU 缓存中的性能如何？为什么要重写 removeEldestEntry() 方法？

标准答案

LinkedHashMap 作为 基于 HashMap + 双向链表 实现的有序 Map，在 LRU（Least Recently Used）缓存中具有良好的性能：

1. 查询性能 (get()) 近似 O(1)：基于 HashMap 实现，哈希查找性能稳定。
2. 插入和更新 (put()) 近似 O(1)：通过 访问顺序模式（AccessOrder=true），自动调整访问顺序，使最近访问的元素移动到链表尾部。
3. 淘汰策略 O(1)：通过 重写 removeEldestEntry() 方法，控制何时移除最旧的元素（链表头部的节点），实现 LRU 机制。

removeEldestEntry() 方法的作用是 在 put() 时检查是否需要删除最老的元素，如果返回 true，则移除 链表头部（最久未访问的元素），保证缓存不会无限增长。

答案解析

1. LinkedHashMap 的数据结构

LinkedHashMap 继承自 HashMap，并通过 双向链表（Doubly Linked List） 维护元素的插入顺序或访问顺序：

• 普通模式（默认 accessOrder=false）：按照插入顺序遍历。
• LRU 模式（accessOrder=true）：最近访问的元素会被移动到链表尾部，最久未使用的元素在链表头部。

🔹 示例：默认插入顺序（accessOrder=false）

put("A"), put("B"), put("C") → 遍历顺序：A → B → C
get("A") → 遍历顺序不变：A → B → C

🔹 示例：访问顺序模式（accessOrder=true）

put("A"), put("B"), put("C") → 访问顺序：A → B → C
get("A") → A 被移到尾部，顺序变为：B → C → A

2. LRU 需要重写 removeEldestEntry()

当 LinkedHashMap 作为 LRU 缓存 时，我们需要控制 缓存最大容量，这时就需要重写 removeEldestEntry()，自动删除最旧的数据：

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

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true，启用 LRU 访问顺序
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // 超过最大容量时，移除最老的元素
    }
}

removeEldestEntry() 作用：

• 保证超出容量时自动淘汰最旧的元素（即链表头部的元素）。
• 避免手动删除过期数据，降低 put() 时的维护成本。

3. LRU 访问顺序如何优化性能？

LRU 通过 最近访问的数据放到尾部，最久未访问的数据放到头部，有效提升以下场景的性能：

✅ 热点数据访问优化：

• 频繁访问的 key 会留在链表尾部，不易被淘汰，提升缓存命中率。
• 低频访问的数据自然被淘汰，避免缓存污染。

✅ CPU 缓存友好性：

• LRU 访问模式使 最近访问的数据连续存储，提升 CPU Cache 命中率，提高访问效率。

✅ 适用于 Web 缓存、数据库缓存、应用层缓存：

• 例如 Tomcat 的 Session 缓存，定期淘汰长时间未使用的 Session。
• MySQL InnoDB Buffer Pool 采用 LRU 机制，优先保留最近访问的索引和数据页。

4. 常见误区

❌ 误区 1：LinkedHashMap 自带 LRU 机制，不用重写 removeEldestEntry()

• LinkedHashMap 默认不会移除老数据，需要手动重写 removeEldestEntry()，否则缓存会无限增长。

❌ 误区 2：put() 或 get() 不影响 LRU 顺序

• 只有在 accessOrder=true 时，get() 才会调整顺序，默认模式不会改变顺序。

🔹 错误示例（accessOrder=false 时 get() 不会调整顺序）：

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(3, 0.75f, false);
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
map.get(1); // 访问 1 但不会移动
map.put(4, "D"); // 超过容量，仍然移除最早的 1

🔹 正确示例（accessOrder=true 时 get() 会调整顺序）：

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(3, 0.75f, true);
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
map.get(1); // 访问 1，被移到尾部
map.put(4, "D"); // 超过容量，移除最久未使用的 2

最佳实践

1. 使用 accessOrder=true 启用 LRU 访问顺序

   • 让 get() 也能调整顺序，避免高频访问的数据被误删。

2. 重写 removeEldestEntry() 实现自动淘汰

   • 限制缓存大小，避免 OutOfMemoryError（OOM）。

3. 避免使用 synchronized 版 LinkedHashMap

   • Collections.synchronizedMap(new LinkedHashMap<>()) 线程安全，但并不适用于高并发场景。
   • 高并发推荐 ConcurrentLinkedHashMap 或 Caffeine Cache。

深入追问

🔹 1. LinkedHashMap 的 LRU 机制和 ConcurrentHashMap 能否结合？

• LinkedHashMap 本身 不是线程安全的，无法直接用于高并发缓存。
• 解决方案：可以用 ConcurrentHashMap + LinkedList 组合 或 Caffeine Cache。

🔹 2. 为什么 Redis 使用 LRU 而不是 LFU？

• LRU 更适用于一般业务，LFU（Least Frequently Used）适合热点数据更稳定的场景。
• Redis 4.0 以后支持 LFU，但默认仍是 LRU。

🔹 3. LinkedHashMap 和 LRUCache（Guava / Caffeine）相比，哪个更高效？

• LinkedHashMap 适合小规模缓存，但不支持并发。
• Caffeine Cache 采用 Window TinyLFU + Clock Pro，更适合大规模高并发场景。

相关面试题

• LRU、LFU、FIFO 三种缓存策略的对比？
• ConcurrentHashMap 如何实现高并发缓存？
• Guava Cache 和 Caffeine Cache 的核心优化点？
• Redis 的 LRU 淘汰策略如何实现？