综合练习：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;
    }
}