约 7 分钟3 张卡

LinkedHashMap

LinkedHashMap 用双向链表记录条目顺序，同时保留 HashMap 按键查找的能力。本文以 Java 21 为准，先区分插入顺序和访问顺序，再讲解简单 LRU 缓存的实现与成本。LRU 指优先淘汰最久未访问条目的策略。

1. 面试核心

先记住这几条，再读正文

结构分工。 LinkedHashMap 用哈希桶定位条目，用双向链表记录遍历顺序。
遍历顺序。 LinkedHashMap 默认保留插入顺序，设置 accessOrder=true 后按访问顺序排列，链首是最久未访问条目。卡 · 插入顺序
LRU 淘汰。 访问顺序模式中，让 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. 插入顺序

常考卡 · LinkedHashMap 的插入顺序与访问顺序有什么区别

默认构造保留键首次插入的顺序：

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, B]。这种插入顺序适合以下需求：

稳定输出配置和聚合结果。
去重后保留输入顺序。
API 需要可预测遍历顺序。

如果只需要保留插入顺序，就可以使用 LinkedHashMap，省去 TreeMap 按键排序所需的对数级比较。

4. 访问顺序

常考卡 · LinkedHashMap 的插入顺序与访问顺序有什么区别

缓存常需要知道哪些条目最近被使用过。构造时将 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 命中非尾条目时，会调整双向链接。这属于结构修改，已有迭代器发现修改计数变化时，会抛出 ConcurrentModificationException，简称 CME。跨线程访问也需要同步，即使多个线程只调用 get。

这种修改检测称为 fail-fast，具体机制见集合迭代器。

5. removeEldestEntry 与 LRU

常考卡 · 怎样使用 HashMap 和双向链表实现 LRU

有了访问顺序，再加上容量上限，就能实现简单 LRU。removeEldestEntry 是容器在新增条目后调用的方法，可以通过重写它决定是否淘汰链首：

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 新增条目后会调用 removeEldestEntry。示例在条目数超过 maximumSize 时返回 true，容器便移除链首，也就是最久未访问的条目。上限为 0 时，每次新增条目都会立即被移除；负数上限则由构造器拒绝。

5.1 简单 LRU 的局限

这个实现只限制条目数，并按访问顺序淘汰。业务如果还有以下缓存管理需求，就需要额外机制：

多个线程同时读写时，需要控制并发访问。
条目大小差异明显时，需要按内存占用等权重限制容量。
数据会过时时，需要设置过期时间或刷新内容。
多个请求同时未命中时，需要合并加载，避免它们同时查询数据库等数据源。
需要监控命中率和淘汰次数，判断缓存是否有效。
淘汰时若执行额外回调，需要隔离回调失败的影响。

把同一个键的并发加载合并称为加载去重，用于缓解大量未命中请求同时访问数据源的缓存击穿问题。这个简单实现适合教学、小规模局部缓存和约束简单的工具。需要上述能力时，可以使用 Caffeine 等专门缓存组件，或远程缓存系统。

6. LRU 与其他淘汰策略

LRU 根据最近访问时间选择淘汰对象，依据是最近用过的数据更有机会再次被使用。如果一次扫描访问大量不同键，它们都会成为最近访问项，从而挤出反复使用的热点条目。因此，访问模式会直接影响 LRU 的命中率。

比较缓存策略时，还需要区分以下淘汰与过期方式：

FIFO 按写入顺序淘汰最早加入的条目，访问次数和时间都不影响顺序。
LFU 按访问频率选择，倾向保留被多次访问的条目。
混合策略结合近期访问窗口与频率估计，同时考虑最近使用和长期热点。
TTL 表示条目的生存时间，到期后按过期规则处理。它可以与容量淘汰同时使用。

选择时要结合访问分布和对象大小，还要明确业务能接受数据旧到什么程度。容量淘汰控制缓存占用，TTL 则控制数据有效期，两者解决的问题不同。

7. 迭代与内存成本

LinkedHashMap 沿顺序链遍历，成本为 O(size)，只与实际条目数有关。HashMap 则还要扫描桶数组，所以容量预留较大且频繁完整遍历时，顺序链可以减少空桶扫描。

这个收益需要用额外内存换取：每个条目都增加两个顺序链接。访问顺序模式中，get 命中非尾条目时还要修改这些链接。因此，内存敏感时要按实际对象布局和数据量测量，性能评估也要包含重排成本。

8. 访问重排的方法范围

常考卡 · containsKey 或遍历 entrySet 会刷新 LRU 访问顺序吗？

读取或更新条目是否刷新 LRU 次序，取决于调用的方法。在访问顺序模式中，各方法的效果如下：

方法	访问重排
get、getOrDefault	命中时移到链尾
put、putIfAbsent、compute 系列、merge	调用完成后条目仍存在时，构成访问
replace	成功替换值时，构成访问
containsKey、keySet/entrySet 遍历	保持访问顺序

因此，用 containsKey 检查缓存是否存在，只会得到存在性结果，访问顺序保持不变。遍历 keySet 时再调用 get，却会在命中非尾条目时触发重排。若需要同时读取键和值，直接遍历 entrySet 就能避免这次额外访问。