# 问题

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,还额外维护了 beforeafter 指针:
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after; // 维护双向链表的前后指针
    }
    
    1
    2
    3
  • 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]
1
2
3
4
5
6

# 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);
    }
}
1
2
3
4
5
6
7
8
9
  • 这保证了 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]
1
2
3
4
5
6
7
8
9
10
11
12
  • 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<>();
      
      1
    • 正确方案:
      Map<Integer, String> map = Collections.synchronizedMap(new LinkedHashMap<>());
      
      1
    • synchronizedMap 仅保证 单次操作 线程安全,并发环境建议使用 ConcurrentLinkedHashMapCaffeine
  2. 误认为默认是 LRU 模式

    • accessOrder = false 时,默认按照插入顺序维护,不会自动调整访问顺序
  3. 误以为 removeEldestEntry() 触发后立即删除

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

# 深入追问

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

# 相关面试题

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