LinkedHashMap
LinkedHashMap 是在 HashMap 之上多维护了一条双向链表的 Map:哈希桶负责按键查找,链表负责记录条目的顺序。链表可以按插入顺序排,也可以按访问顺序排;按访问顺序排时,链首就是最久没被访问的条目,再加一个容量上限,就得到一个简单的 LRU(Least Recently Used,优先淘汰最久未访问的条目)缓存。用它实现缓存,需要分清两种顺序的区别,确认哪些方法算一次「访问」,并理解读操作为什么也会修改结构。下文以 Java 21 为准。
1. 面试核心
先记住这几条,再读正文- LinkedHashMap 用哈希桶定位条目,用双向链表记录遍历顺序,每个条目同时挂在这两套结构上。
- 默认保留插入顺序;设置
accessOrder=true后按访问顺序排列,链首是最久未访问的条目。卡 · 插入顺序 - 访问顺序模式下,让
removeEldestEntry返回size() > maximumSize,就能实现按条目数限制的 LRU 缓存。卡 · 哈希表与顺序链 - 访问顺序模式的
get命中非尾条目时会重排链表,这是结构修改,所以多个线程只读也需要同步。 containsKey和集合视图遍历不会刷新访问顺序。卡 · 访问重排的方法范围
2. 哈希表与顺序链
按键查找和按顺序遍历需要两套不同的连接关系。LinkedHashMap 沿用 HashMap 的桶结构来定位条目,同时把所有条目串进一条双向链表,用来记录遍历顺序:
table buckets encounter order
0 -> [B] [A] ⇄ [B] ⇄ [C]
1 -> [A] -> [C]
A 和 C 落在同一个哈希桶里,但遍历时沿着顺序链走,依次得到 A、B、C。也就是说,每个条目既属于某个桶,也属于这条全局的顺序链。哈希分布合理时,get、put 仍然平均 O(1);代价是每个条目多存前后两个引用,顺序变化时还要维护这些链接。
3. 插入顺序
插入顺序是键第一次放进 Map 的顺序,也是默认构造器使用的顺序:
Map<String, Integer> counts = new LinkedHashMap<>();
counts.put("A", 1);
counts.put("B", 2);
counts.put("A", 3);
System.out.println(counts.keySet()); // [A, B]
第二次写入 A 只是替换了值,A 的位置不变,所以输出还是 [A, B]。需要稳定输出配置或聚合结果、去重后保留输入顺序,或者 API 要给出可预测的遍历顺序时,插入顺序都很合适。
如果只需要保留插入顺序,用 LinkedHashMap 就够了,不必为此换成 TreeMap,后者按键排序,每次操作都要付出对数级的比较成本。
4. 访问顺序
访问顺序把最近被访问的条目放到链尾,缓存正需要这个信息来判断哪些条目最近用过。构造时把第三个参数 accessOrder 设为 true,get 等访问操作就会把命中的条目移到链尾:
Map<String, String> cache = new LinkedHashMap<>(16, 0.75f, true);
cache.put("A", "value-a");
cache.put("B", "value-b");
cache.get("A");
System.out.println(cache.keySet()); // [B, A]
访问 A 之后,顺序从 [A, B] 变成了 [B, A]。所以在这个模式下,链首是最久未访问的条目,链尾是最近访问的条目。
要注意,get 命中非尾条目时会调整双向链接,这在 LinkedHashMap 里算一次结构修改。这带来两个后果。第一,如果此时有迭代器正在遍历,它会发现修改计数变了,抛出 ConcurrentModificationException(简称 CME),这种检测叫 fail-fast,机制见集合迭代器。第二,多个线程即使只调用 get,也是在并发修改链表,同样需要同步。
4.1 访问重排的方法范围
一次调用算不算访问、会不会刷新 LRU 次序,取决于调用的是哪个方法。在访问顺序模式中:
| 方法 | 访问重排 |
|---|---|
| get、getOrDefault | 命中时移到链尾 |
| put、putIfAbsent、compute 系列、merge | 调用完成后条目仍存在时,构成访问 |
| replace | 成功替换值时,构成访问 |
| containsKey、keySet/entrySet 遍历 | 保持访问顺序 |
所以用 containsKey 检查缓存里有没有某个键,只会得到是否存在的结果,不会改变顺序。反过来,遍历 keySet 时顺手调用 get 取值,命中非尾条目就会触发重排,并让正在进行的遍历抛出 CME。需要同时拿到键和值时,直接遍历 entrySet 就能避开这次额外的访问。
5. removeEldestEntry 与 LRU
有了访问顺序,再加一个容量上限,就是一个简单的 LRU 缓存。removeEldestEntry 是 LinkedHashMap 在新增条目之后调用的方法,返回 true 就移除链首。重写它就能决定什么时候淘汰:
public final class LruCache<K, V> extends LinkedHashMap<K, V> {
private final int maximumSize;
public LruCache(int maximumSize) {
super(Math.max(16, maximumSize), 0.75f, true);
if (maximumSize < 0) {
throw new IllegalArgumentException("maximumSize must be >= 0");
}
this.maximumSize = maximumSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maximumSize;
}
}
put 新增条目后,条目数一旦超过 maximumSize,removeEldestEntry 返回 true,容器就移除链首,也就是最久未访问的那个条目。上限为 0 时,刚新增的条目就是唯一的条目,会立刻被移除;负数上限由构造器直接拒绝。
5.1 简单 LRU 的局限
这个实现只做了两件事:限制条目数,按访问顺序淘汰。真实的缓存通常还有这些缓存管理需求,都需要额外的机制:
- 多个线程同时读写时,要控制并发访问。
- 条目大小差别很大时,要按内存占用等权重限制容量。
- 数据会过时,要设置过期时间或定期刷新。
- 多个请求同时未命中同一个键时,要合并成一次加载,避免它们一起去查数据库。
- 要监控命中率和淘汰次数,判断缓存是否有效。
- 淘汰时如果执行回调,要隔离回调失败的影响。
其中合并同一个键的并发加载叫加载去重,它用来缓解缓存击穿:大量请求同时未命中,一起压到数据源上。LruCache 这样的简单实现适合教学、小规模的局部缓存和约束简单的工具;需要上面这些能力时,应该用 Caffeine 这类专门的缓存组件,或者远程缓存系统。
6. LRU 与其他淘汰策略
LRU 按最近访问时间选淘汰对象,它的假设是最近用过的数据更可能再被用到。这个假设不总成立:一次扫描如果访问了大量不同的键,它们都会变成最近访问项,把反复使用的热点条目挤出去。所以 LRU 的命中率很依赖访问模式。
比较缓存策略时,还要分清下面几种淘汰与过期方式:
- FIFO 按写入顺序淘汰最早加入的条目,访问次数和访问时间都不影响顺序。
- LFU 按访问频率选择,倾向保留被多次访问的条目。
- 混合策略同时看近期访问窗口和频率估计,兼顾最近使用和长期热点。
- TTL 是条目的生存时间,到期后按过期规则处理。它和容量淘汰可以同时使用。
选策略时要结合访问分布、对象大小,以及业务能接受数据旧到什么程度。容量淘汰控制缓存占多少空间,TTL 控制数据多久失效,两者解决的是不同的问题。
7. 迭代与内存成本
LinkedHashMap 沿顺序链遍历,成本是 O(size),只和实际条目数有关。HashMap 遍历还要扫描整个桶数组,所以容量预留得大、又经常完整遍历时,LinkedHashMap 能省掉扫描空桶的时间。
这个好处是用内存换来的:每个条目多了两个顺序链接。访问顺序模式下,get 命中非尾条目还要改这些链接。内存敏感时要按实际对象布局和数据量测量,评估性能时也要把重排的成本算进去。
8. 常见问题
8.1 get 与迭代器冲突
只在访问顺序模式下会冲突。这个模式中 get 命中非尾节点会重排,修改计数随之变化,已有迭代器下一次检查时发现计数不一致,就抛出 CME。插入顺序模式的 get 不改变顺序,所以没有这种冲突。
8.2 淘汰钩子的触发时机
removeEldestEntry 只在新增条目之后被调用。Javadoc 写明的是 put 和 putAll;OpenJDK 21 中,putIfAbsent、computeIfAbsent、compute 和 merge 新增条目时同样会调用它,所以用 computeIfAbsent 加载缓存也会按上限淘汰。时间流逝本身不会触发它。所以靠它实现不了 TTL:要让条目按时间过期,还得在读取时检查过期时间,或者增加定时清理。
8.3 访问顺序与线程安全
多个线程共享并更新 LinkedHashMap 时需要同步;访问顺序模式下,get 也会修改链表,所以只有读操作也一样需要同步。用 Collections.synchronizedMap 这类同步包装时,整个遍历过程还要手动锁住包装对象。并发要求复杂的缓存,更适合用专门的实现。
8.4 条目容量与权重容量
条目大小差不多时,按条目数设上限简单有效。大小差别很大时,一个大值就可能占掉大部分内存,条目数还远没到上限,内存已经不够了。这时应该按权重估算容量,并监控实际的堆占用。
9. 面试题卡片
10. 参考资料
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明