# 问题
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; // 维护双向链表的前后指针 }
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]
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);
}
}
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]
2
3
4
5
6
7
8
9
10
11
12
removeEldestEntry()
返回true
时,LinkedHashMap 会自动删除最老的元素,实现 LRU 逻辑。- 最久未使用的元素始终位于链表头部,当
size()
超过限制时,直接删除eldest
元素。
# 4. 为什么 LinkedHashMap 比手写 LRU 代码更高效?
内置双向链表,操作 O(1)
- 手写 LRU 可能使用
HashMap + LinkedList
,需要手动维护链表顺序,性能较低。 LinkedHashMap
通过before
/after
指针 O(1) 时间复杂度 维护顺序。
- 手写 LRU 可能使用
HashMap 直接存取,提高查询效率
- 传统 LRU 可能使用
LinkedList
,查找 O(n),但LinkedHashMap
基于HashMap
,查找 O(1)。
- 传统 LRU 可能使用
JDK 自带,线程安全版本可用
Collections.synchronizedMap()
- 避免手写 LRU 代码的 bug,减少开发成本。
# 5. LinkedHashMap 的常见问题
❌ 常见误区
误认为 LinkedHashMap 是线程安全的
- 错误示例:
Map<Integer, String> map = new LinkedHashMap<>();
1 - 正确方案:
Map<Integer, String> map = Collections.synchronizedMap(new LinkedHashMap<>());
1 - 但
synchronizedMap
仅保证 单次操作 线程安全,并发环境建议使用ConcurrentLinkedHashMap
或Caffeine
。
- 错误示例:
误认为默认是 LRU 模式
accessOrder = false
时,默认按照插入顺序维护,不会自动调整访问顺序。
误以为 removeEldestEntry() 触发后立即删除
- 其实
put()
操作完成后才会检查removeEldestEntry()
,不会在get()
时删除。
- 其实
# 深入追问
🔹 LinkedHashMap 与 LRUCache(手写)相比有哪些优势?
🔹 accessOrder = true
的内部原理是如何实现的?
🔹 如何在并发环境下使用 LRU 缓存?
🔹 为什么 removeEldestEntry()
只有 put()
时才会触发,而 get()
不会?
# 相关面试题
• 如何实现一个 LRU 缓存?有哪些方式?
• LinkedHashMap 和 HashMap 的区别?
• ConcurrentHashMap 是否支持访问顺序?如何实现并发 LRU?
• Caffeine 缓存如何优化 LRU ?