问题

9. LinkedHashMap 如何维护访问顺序？它是如何实现 LRU 缓存的？

标准答案

LinkedHashMap 通过 双向链表（Doubly Linked List） 维护元素的插入顺序或访问顺序。

• 通过构造方法 LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 传入 accessOrder = true，使其按照 最近访问顺序 维护。
• LRU（Least Recently Used）缓存 通过 重写 removeEldestEntry() 方法实现，判断是否需要删除最旧的访问记录。

答案解析

1. LinkedHashMap 的数据结构

LinkedHashMap 继承自 HashMap，但在 HashMap 基础上增加了一个双向链表，用于维护元素的顺序。其底层数据结构是：

• 数组 + 双向链表：数组用于哈希存储，双向链表用于维护顺序。
• 每个 Entry 结构不仅包含 key-value，还额外维护了 before 和 after 指针：

  static class Entry<K,V> extends HashMap.Node<K,V> {
      Entry<K,V> before, after; // 维护双向链表的前后指针
  }
  

• 当 accessOrder = true 时，每次 get()、put() 操作都会将访问的 Entry 移动到链表尾部，保证最近访问的数据在链表尾部，最久未使用的数据在头部。

示例：

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
map.get(1); // 访问 1 后，它会被移动到链表尾部
System.out.println(map.keySet()); // 输出 [2, 3, 1]

2. 访问顺序如何维护？

当 accessOrder = true 时，每次访问元素后，都会将其移动到链表的尾部。核心逻辑在 afterNodeAccess() 方法中：

void afterNodeAccess(Node<K,V> e) { 
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) { 
        // 将 e 节点移动到双向链表尾部
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>) e;
        removeNode(p);
        linkNodeLast(p);
    }
}

• 这保证了 get()、put() 后的节点按照最近访问顺序排列，最久未使用的数据始终位于链表头部。

3. 如何实现 LRU 缓存？

LRU（Least Recently Used）缓存，即最近最少使用的元素会被淘汰，可以通过 重写 removeEldestEntry() 方法 实现：

LinkedHashMap<Integer, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > 3; // 超过 3 个元素时，删除最老的元素
    }
};
lruCache.put(1, "A");
lruCache.put(2, "B");
lruCache.put(3, "C");
lruCache.get(1); // 访问 1，使其变为最新
lruCache.put(4, "D"); // 触发 LRU 机制，移除最久未使用的 2
System.out.println(lruCache.keySet()); // 输出 [3, 1, 4]

• removeEldestEntry() 返回 true 时，LinkedHashMap 会自动删除最老的元素，实现 LRU 逻辑。
• 最久未使用的元素始终位于链表头部，当 size() 超过限制时，直接删除 eldest 元素。

4. 为什么 LinkedHashMap 比手写 LRU 代码更高效？

1. 内置双向链表，操作 O(1)

   • 手写 LRU 可能使用 HashMap + LinkedList，需要手动维护链表顺序，性能较低。
   • LinkedHashMap 通过 before / after 指针 O(1) 时间复杂度 维护顺序。

2. HashMap 直接存取，提高查询效率

   • 传统 LRU 可能使用 LinkedList，查找 O(n)，但 LinkedHashMap 基于 HashMap，查找 O(1)。

3. JDK 自带，线程安全版本可用 Collections.synchronizedMap()

   • 避免手写 LRU 代码的 bug，减少开发成本。

5. LinkedHashMap 的常见问题

❌ 常见误区

1. 误认为 LinkedHashMap 是线程安全的

   • 错误示例：

     Map<Integer, String> map = new LinkedHashMap<>();
     

   • 正确方案：

     Map<Integer, String> map = Collections.synchronizedMap(new LinkedHashMap<>());
     

   • 但 synchronizedMap 仅保证 单次操作 线程安全，并发环境建议使用 ConcurrentLinkedHashMap 或 Caffeine。

2. 误认为默认是 LRU 模式

   • accessOrder = false 时，默认按照插入顺序维护，不会自动调整访问顺序。

3. 误以为 removeEldestEntry() 触发后立即删除

   • 其实 put() 操作完成后才会检查 removeEldestEntry()，不会在 get() 时删除。

深入追问

🔹 LinkedHashMap 与 LRUCache（手写）相比有哪些优势？
🔹 accessOrder = true 的内部原理是如何实现的？
🔹 如何在并发环境下使用 LRU 缓存？
🔹 为什么 removeEldestEntry() 只有 put() 时才会触发，而 get() 不会？

相关面试题

• 如何实现一个 LRU 缓存？有哪些方式？
• LinkedHashMap 和 HashMap 的区别？
• ConcurrentHashMap 是否支持访问顺序？如何实现并发 LRU？
• Caffeine 缓存如何优化 LRU ？