LinkedHashMap 是什么？如何用它实现 LRU 缓存？

简化版

LinkedHashMap = HashMap + 一条双向链表，在哈希表的基础上额外维护了元素的顺序（默认按插入顺序，也可设为访问顺序）。正因为能按「访问顺序」排列、还提供了 removeEldestEntry 钩子，它成了实现 LRU（最近最少使用）缓存的现成工具——几行代码就能搞定。

详细版

LinkedHashMap 相比 HashMap 多了什么：HashMap 是无序的（遍历顺序和插入无关）。LinkedHashMap 在每个节点上多挂了 before/after 两个指针，串成一条双向链表，从而记住顺序。它有两种模式：

插入顺序（默认）：遍历顺序 = 放进去的先后；
访问顺序（构造时 accessOrder=true）：每次 get/put 访问一个元素，就把它移到链表尾部。于是链表头部永远是「最久没被访问」的元素——这正是 LRU 需要的。

两个关键点让它能做 LRU：

构造时开启访问顺序：new LinkedHashMap<>(capacity, 0.75f, true)；
重写 removeEldestEntry()：当元素超过容量上限时返回 true，让它自动淘汰链表头部（最久未用）的元素。

完整版教学

一、LRU 是什么，为什么 LinkedHashMap 天生合适

LRU（Least Recently Used） 是一种缓存淘汰策略：缓存满了要删元素时，删掉最久没被使用的那个。它的假设是「最近用过的，接下来更可能再用」。

实现 LRU 需要两个能力：

O(1) 的查找（判断 key 在不在、拿 value）；
按「最近使用」排序，且能快速把刚用的挪到「最新」、快速找到「最旧」的删掉。

LinkedHashMap 恰好两个都满足：哈希表给 O(1) 查找，双向链表给顺序维护，且访问顺序模式下每次访问自动把元素移到尾部。所以它是 LRU 的天选实现。

二、二十行实现一个 LRU 缓存

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // accessOrder=true：按访问顺序排列，最近访问的移到尾部
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    // 每次 put 后回调：返回 true 就淘汰最老的元素（链表头）
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

// 用法
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "a"); cache.put(2, "b"); cache.put(3, "c");
cache.get(1);          // 访问 1，1 被移到最新
cache.put(4, "d");     // 超容量，淘汰最久没用的 2
// 此时缓存里是 {3, 1, 4}，2 被淘汰

关键就两处：构造器里 accessOrder=true 打开访问顺序，removeEldestEntry 在超容量时触发淘汰。LinkedHashMap 内部会在每次 put 后自动调用 removeEldestEntry 并按需删头节点。

三、原理拆解：访问顺序是怎么维护的

accessOrder=true 时，LinkedHashMap 重写了 HashMap 预留的回调钩子 afterNodeAccess：每当 get 或 put 命中一个节点，就把它从链表当前位置摘下、接到链表尾部。于是：

尾部 = 最近访问的；
头部 = 最久未访问的（LRU 要淘汰的目标）。

而 afterNodeInsertion（插入后回调）里会检查 removeEldestEntry，为 true 就删掉头节点（head，即最旧的）。这套「HashMap 留钩子、LinkedHashMap 填实现」的设计，让排序和淘汰几乎零成本地嵌进了原有的哈希表操作里。

四、生产中该用什么

手写 LinkedHashMap 版 LRU 适合面试和轻量单机场景，但它非线程安全。生产环境更推荐成熟方案：

Caffeine / Guava Cache：高性能本地缓存，支持容量/时效淘汰、并发安全、统计，实际用的是比纯 LRU 更优的 W-TinyLFU 算法；
Redis：分布式缓存，maxmemory-policy 支持 LRU/LFU 淘汰策略。

面试能手写 LinkedHashMap 版 LRU + 说清「生产用 Caffeine/Redis」是加分组合。（另一种经典手写法是 HashMap + 自定义双向链表，不依赖 LinkedHashMap，是 LeetCode 146 的标准解，也值得会。）

五、淘汰时机、访问定义与容量成本

removeEldestEntry 在插入新映射之后被回调，因此容量上限为 3 时，第 4 个新 key 短暂进入 Map，随后才根据返回值删除头节点。它用于限制条目数很方便，却不会因为时间到期主动执行，也不知道每个 value 占多少字节；按重量、过期时间和异步加载淘汰应交给 Caffeine 等缓存库。

容量 3，访问顺序模式
put 1,2,3       链表：1 → 2 → 3
get 1           链表：2 → 3 → 1
put 4           临时：2 → 3 → 1 → 4
淘汰 eldest=2   结果：3 → 1 → 4

访问顺序下，get 会改变链表结构，因此它不再是纯只读操作；没有外部同步时，并发 get 也可能破坏链表。即使用 Collections.synchronizedMap 包装，返回迭代器后仍要在同一个包装对象上锁住整个遍历过程。

能力	LinkedHashMap 简易 LRU	Caffeine 等生产缓存
条目数上限	支持	支持
访问顺序	支持	支持更先进的准入/淘汰策略
按时间过期	需自行实现且难严谨	原生支持
按权重控制	需自行统计	原生支持
并发安全	否	是
命中率统计/异步加载	无	通常支持

六、常见误区与追问

误区：LinkedHashMap 只保持插入顺序。 构造参数 accessOrder=true 后会按访问顺序维护链表。
误区：忘记 accessOrder=true 也能实现 LRU。 默认模式只反映插入先后，超容量淘汰的是最早插入项，更接近 FIFO。
误区：重写 removeEldestEntry 时要手工 remove。 钩子只返回是否淘汰，LinkedHashMap 会负责删除 eldest。
追问：哪些操作会刷新访问顺序？ get、命中已有键的 put/compute 等访问型操作会按具体 API 语义触发，不能只把写入当访问。
追问：为什么并发 get 也不安全？ 访问顺序模式会把节点摘下并接到尾部，get 实际修改双向链表。
追问：简易 LRU 为什么不等于生产缓存？ 它缺少并发、过期、权重、加载、统计和更高命中率策略等完整能力。

记忆钩子：哈希表回答“值在哪”，双向链表回答“谁最旧”；打开访问顺序后，连 get 都会重排这条时间线。

七、加强记忆

LinkedHashMap 在 HashMap 节点外增加 before/after 链接，可按插入或访问顺序遍历。LRU 模式要把 accessOrder 设为 true，使每次访问把节点移到尾部，再由 removeEldestEntry 在插入后淘汰头部最旧节点。该方案按条目数控制、非线程安全且不提供过期和权重策略，适合面试与轻量单机场景，生产缓存优先使用 Caffeine 或分布式缓存系统。

简化版

详细版