综合练习：LRU 缓存

这一课你将能做到

1. 独立实现 get / put 均为 O(1) 的 LRU（Least Recently Used，最近最少使用）缓存
2. 用单元测试覆盖容量淘汰、更新提级、重复读取三类关键行为
3. 说清手写 LRU 与 JDK LinkedHashMap、生产级 Caffeine 的差异与选型理由

为什么要学

这是整个计算机科学课程的收官实战。LRU 虽小，却同时调用了前 11 课的知识：

• 数据结构（第 2 课）：哈希表负责定位、双向链表负责顺序
• 复杂度（第 3-4 课）：为什么两个结构组合后全部操作能做到 O(1)
• 操作系统（第 6 课）：页面置换算法 LRU 的原始出处
• 系统设计（第 9 课）：缓存容量有限时淘汰谁？Redis 的 maxmemory-policy 就有 allkeys-lru
• 设计模式（第 11 课）：缓存接口与实现分离、装饰器包装

在判题平台，LRU 直接可用：本地缓存热门题目详情、缓存用户会话、缓存编译产物。能独立写出并讲透 LRU，是中高级 Java 面试的硬指标，也是把零散知识整合成「一个能工作的组件」的最佳练习。

先建立图像

LRU 规则一句话：容量满时，淘汰最久没有被访问（读或写）的那个元素。

容量=3，双向链表头部=最近使用，尾部=最久使用

put(A) put(B) put(C)
  head              tail
   [A] ⇄ [B] ⇄ [C]
get(B)  → B 提到头部
   [B] ⇄ [A] ⇄ [C]
put(D)  → 容量满，淘汰尾部 C；D 进头部
   [D] ⇄ [B] ⇄ [A]
put(A,新值) → 值更新且 A 提到头部
   [A] ⇄ [D] ⇄ [B]

为什么需要两个结构？
  哈希表 Map<key, Node> ：O(1) 找到节点（否则要沿链表 O(n) 找）
  双向链表              ：O(1) 删除/移动已知节点（单链表删自己要先找前驱）
  两个 dummy 哨兵 head/tail：消除空链表的边界判断

跟着做

步骤 1：实现核心 LRU

import java.util.HashMap;
import java.util.Map;

public class LruCache<K, V> {

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null);  // 虚拟头（最近使用）
    private final Node<K, V> tail = new Node<>(null, null);  // 虚拟尾（最久使用）

    public LruCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("容量必须大于 0");
        }
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            return null;
        }
        moveToHead(node);       // 访问即提级
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);   // 已存在：更新 + 提级
        } else {
            Node<K, V> created = new Node<>(key, value);
            map.put(key, created);
            addToHead(created);
            if (map.size() > capacity) {
                Node<K, V> lru = removeTail();   // 淘汰最久未用
                map.remove(lru.key);
            }
        }
    }

    public int size() {
        return map.size();
    }

    // ---- 链表操作：全部只动指针，O(1) ----
    private void addToHead(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    private Node<K, V> removeTail() {
        Node<K, V> lru = tail.prev;
        removeNode(lru);
        return lru;
    }
}

复杂度逐项核对：map.get/put 平均 O(1)；链表四个操作都只改固定数量的指针，O(1)。因此 get/put 整体平均 O(1)；空间 O(capacity)。这就是「哈希表 + 双向链表」组合的威力，缺一不可。

步骤 2：写单元测试验证行为

JUnit 5（Spring Boot 3 默认自带）：

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

class LruCacheTest {

    @Test
    void shouldEvictLeastRecentlyUsed() {
        LruCache<String, Integer> cache = new LruCache<>(2);
        cache.put("A", 1);
        cache.put("B", 2);
        cache.get("A");              // B 变为最久未用
        cache.put("C", 3);           // 淘汰 B

        assertNull(cache.get("B"));
        assertEquals(1, cache.get("A"));
        assertEquals(3, cache.get("C"));
        assertEquals(2, cache.size());
    }

    @Test
    void updateShouldRefreshOrder() {
        LruCache<String, Integer> cache = new LruCache<>(2);
        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("A", 10);          // 更新 A 并提级 → 淘汰 B
        assertNull(cache.get("B"));
        assertEquals(10, cache.get("A"));
    }

    @Test
    void illegalCapacityShouldFail() {
        assertThrows(IllegalArgumentException.class, () -> new LruCache<>(0));
    }
}

测试设计思路：不要随机操作后肉眼对结果，而是针对每条规则（淘汰、提级、更新、边界）各写一个最小场景。先写测试再实现（TDD）在这种结构清晰的组件上特别顺手。

步骤 3：对比三种现成方案

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapLru<K, V> {

    // 最简 LRU：accessOrder=true 让 get 也调整迭代顺序
    private final Map<K, V> map;

    public LinkedHashMapLru(int capacity) {
        this.map = Collections.synchronizedMap(new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;     // 插入后超容量自动淘汰最久未用
            }
        });
    }
}

三者选型对照：

• 手写 LRU：面试与学习首选，理解机制；生产中需要 TTL、命中率统计、并发控制时要补很多东西
• LinkedHashMap：JDK 自带、代码最短，适合单线程或外部加锁的简单场景；注意它本身线程不安全
• Caffeine（Spring 默认本地缓存）：生产首选，基于 W-TinyLFU 策略，命中率通常高于纯 LRU，支持异步加载、TTL、统计；并发安全、性能经过大量验证
• Redis：分布式场景，allkeys-lru 策略在多实例间共享容量，代价是网络往返

讲清楚要点

1. LRU 的「使用」包含读和写：get 与 put 都会让元素变「最近」，这是新手最常漏的一条；put 已存在 key 必须同时做值更新与顺序提级。
2. 双向链表 + 哈希表是 O(1) 的唯一关键组合：单链表无法在不知道前驱时 O(1) 删除；只有链表没有哈希表则定位 O(n)。哨兵节点把「空表/单节点」的特殊情况统一掉，代码更不容易错。
3. LRU 的假设是「近期用过的将来还会用」，与 CPU 缓存的局部性原理同构；但对扫描型访问（偶尔一次性遍历大量 key）纯 LRU 会把热点挤出去，Caffeine 的 TinyLFU 用频率统计改进这一点。
4. 线程安全要看场景：本地缓存在 Spring 单例 Bean 里被多线程访问，手写 LRU 需要加锁或用 ConcurrentHashMap + 同步链表操作；简单做法是直接上 Caffeine。
5. 淘汰策略家族：FIFO（先进先出，不看访问）、LRU（看最近时间）、LFU（看总频率）、LRU-K/ARC/W-TinyLFU（融合时间与频率）；Redis、MySQL Buffer Pool、操作系统各有选择，理解权衡即可。

你可能会懵的地方

• 为什么链表节点里还要存 key？ 淘汰尾部节点时，需要从哈希表删掉对应条目；只存 value 就不知道该删哪个 map key。这个反向引用是实现细节里最容易漏的。

• get 也要改链表顺序，性能不是浪费吗？ moveToHead 只改几个指针，纳秒级；它正是 LRU 语义的一部分。读不改顺序，算法就退化成 FIFO，命中率明显下降。

• LRU 和 LFU 到底选哪个？ LRU 实现简单、对「热点漂移」反应快，但怕偶发批量扫描污染；LFU 抗扫描但一个曾经热门、如今无用的 key 会赖着不走。现代本地缓存选 Caffeine（融合策略），Redis 可按业务在 allkeys-lru 与 allkeys-lfu 间选。

• 为什么不用 Collections.synchronizedMap 包一下自己的 LRU？ 每个方法单独加锁不等于「get 后检查再 put」这类复合操作原子；而 LRU 内部 get 本身就要修改链表结构，粗粒度锁可以保证正确但高并发吞吐有限，Caffeine 这类专用实现的并发设计优秀得多。

• 本地缓存和 Redis 都用 LRU，数据以谁为准？ Redis 是共享层、本地缓存是各实例的加速层（典型二级缓存）；一致性遵循 Cache Aside：数据更新后先改库、删 Redis，再通过广播让各实例失效本地缓存。本地缓存适合 TTL 短、容忍短暂不一致的数据。

错法对照

错法	问题	正解
get 只返回值不提级	顺序语义错误，淘汰错对象	get 中调用 moveToHead
put 新元素后先不判容量	容量超限，缓存无限增长	插入后检查 size > capacity 即淘汰
用单链表实现	删除节点要 O(n) 找前驱	双向链表（或 LinkedHashMap）
忘记节点存 key	淘汰时无法删哈希表条目	Node 同时持有 key 与 value
多线程直接裸用手写 LRU	链表指针错乱、丢数据	加锁封装或直接使用 Caffeine

卡点急救

1. 淘汰结果和预期不符：按时间顺序把每个操作后的链表画出来（头到尾），对照三条规则：读提级、写新元素入头、满则删尾；90% 的错误是漏了某个提级动作。
2. 并发下出现环或节点丢失：说明链表操作未同步；先用粗粒度锁验证逻辑正确，再决定是否优化为细粒度或更换 Caffeine。
3. 缓存命中率不升反降：检查容量是否过小（频繁全量置换）、是否存在扫描型访问污染；开启命中率统计（Caffeine/Redis INFO），用数据定位而不是猜。

面试常问

• 请手写 LRU 并说明复杂度。 HashMap + 双向链表 + 头尾哨兵；get 命中后 moveToHead，put 区分新增/更新，超容量 removeTail 并删 map 项；get/put 平均 O(1)，空间 O(capacity)。讲出节点存 key 和访问提级两个细节，基本就是满分答案。

• LRU 有什么缺点？生产中怎么改进？ 怕扫描污染、需要维护链表、并发处理复杂。改进：LRU-K/2Q 结合频率，Caffeine 用 W-TinyLFU 提升命中率；分布式用 Redis 的 LRU/LFU 策略。

• 在项目中你会把 LRU 用在哪里？和 Redis 怎么配合？ 本地缓存热点题目、会话与编译产物（Caffeine）；跨实例共享数据放 Redis。更新路径：改库 → 删 Redis → 广播失效本地缓存；为热点 key 加互斥回源，防止缓存击穿（呼应第 9 课）。

自测三问

1. 空白纸上 20 分钟内写出完整 LRU，并当场用一组操作手动推演淘汰顺序。
2. 解释清楚四个「为什么」：为什么双向、为什么哈希、为什么哨兵、为什么节点存 key。
3. 判题平台要缓存 1 万道热门题且多实例部署，你如何在 Caffeine 与 Redis 间分工？一致性怎么保证？

小结一句话

LRU 用哈希表解决「找得到」、用双向链表解决「动得快」，把有限容量下的淘汰问题压缩成全部 O(1) 的指针操作——它是整门计算机科学课程最小也最完整的一次知识合奏。

延伸

• Caffeine 官方项目（GitHub）——高性能 Java 本地缓存的设计文档与命中率白皮书
• Redis：缓存淘汰策略官方文档——LRU/LFU 在分布式缓存中的真实实现
• 《算法（第 4 版）》在线书籍（Red Book）——回看哈希与链表章节，体会本课设计的根基
• 课程收官：回到 计算机科学路线图 复盘全部节点；下一步可挑战《SICP》（在线版）或深入 Spring 源码，把本课的直觉继续向两端延伸。