常见缓存策略（一）：LRU（最近最少使用）原理与实现

缓存的核心就一句话：把热数据留在内存里。但问题来了——内存有限，放不下全部数据。谁该留下？谁该滚蛋？

LRU 就是最常见的淘汰策略。它的逻辑很简单：如果一个数据最近被访问过，那么将来被访问的概率也更高。每次访问就把数据“提到”最前面，淘汰时从尾巴踢人。嗯，听上去就像排队的插队机制。

LRU 的工作原理

我习惯用一个比喻来理解 LRU。想象一个书架，只能放 5 本书。

  1. 你新买了一本书，放在最显眼的位置（最左边）。
  2. 每次你看完一本书，就把它放回最左边。
  3. 如果书架满了，最右边那本长时间没翻过的书，就被扔掉。

这就是 LRU——最近最少使用的书被淘汰。你想想看，这个策略背后的直觉其实挺符合人性的：常用的东西就该留着，不常用的就别占地方。

我曾经在项目中遇到过一个大坑：缓存雪崩的导火索，就是因为 LRU 实现有 bug，导致热点数据被频繁淘汰。那次事故后，我再也不敢轻视缓存策略的实现细节了。

两种常见的 LRU 实现方案

实现方式 核心数据结构 访问时间复杂度 淘汰时间复杂度 内存开销
双向链表 + 哈希表 LinkedList + HashMap O(1) O(1) 较高（节点指针）
数组 + 时间戳 Array + Timestamp O(n) O(n) 较低

为什么要 O(1)？因为缓存本身就是为了高性能。如果每次访问还要遍历一遍数组，那就别谈性能优化了。所以，工业级实现基本都用双向链表 + 哈希表的组合。

核心思路：哈希表负责 O(1) 查找节点在链表中的位置，双向链表负责 O(1) 移动和删除节点。两者配合，完美。

自己动手实现一个 LRU 缓存

下面是我写的一个简化版实现。注意，为了让你看懂核心逻辑，我特意去掉了泛型和并发控制。生产环境千万别这么写。

class Node {
    int key;
    String value;
    Node prev;
    Node next;

    public Node(int key, String value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    private int capacity;
    private HashMap<Integer, Node> map;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(-1, "");  // 哨兵节点，简化边界处理
        tail = new Node(-1, "");
        head.next = tail;
        tail.prev = head;
    }

    public String get(int key) {
        // 没找到，返回 null
        if (!map.containsKey(key)) {
            return null;
        }
        // 找到了，移到头部
        Node node = map.get(key);
        removeNode(node);
        addToHead(node);
        return node.value;
    }

    public void put(int key, String value) {
        // 已存在，更新值并移到头部
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            removeNode(node);
            addToHead(node);
            return;
        }
        // 缓存满了，淘汰尾部
        if (map.size() >= capacity) {
            Node toRemove = tail.prev;
            removeNode(toRemove);
            map.remove(toRemove.key);
        }
        // 插入新节点
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        addToHead(newNode);
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

小技巧：用两个哨兵节点（head 和 tail）来避免处理空指针。我刚开始写时总在边界条件上翻车，加哨兵后一下清爽了。

核心操作的 O(1) 分析

为什么这三个操作都是 O(1)？我们逐个拆开看。

  • 查找：直接走 HashMap 的 get，O(1) 找到节点引用。
  • 移动到头部：拆成两步——先从链表中摘除节点（O(1)），再插入到头部（O(1)）。链表操作都是改几个指针。
  • 淘汰尾部：tail.prev 就是最久未使用的节点，直接删除（O(1)），再在 HashMap 里移除（O(1)）。

说白了，O(1) 的代价是你必须维护额外的指针和哈希表结构。这叫用空间换时间。

避坑指南：我曾经写了一个版本，在 removeNode 时只更新了 next 指针，忘了更新 prev 指针。结果链表断链，数据乱飞，调试了整整一个下午。切记：双向链表改指针时一定成对更新。

LRU 的并发安全问题

上面的代码在单线程下跑没问题，但生产环境几乎都是高并发。多线程同时读写 HashMap 和链表，会出什么乱子？

最常见的三种：

  • HashMap 死循环：JDK 1.7 的 HashMap 在并发扩容时会导致死循环，CPU 直接飙到 100%。JDK 1.8 修复了这个问题，改为红黑树，但 ConcurrentHashMap 仍是首选。
  • 链表指针混乱：两个线程同时执行 removeNode 和 addToHead，可能导致节点丢失或成环。
  • 数据不一致：读线程看到 map 有 key，但链表里其实已经删了——虽然概率很小，但足够让你头疼。

解决方案也不复杂：简单场景上 synchronized 锁住整个方法；高并发场景用 ConcurrentHashMap + ReentrantReadWriteLock，读读不互斥，读写才互斥。我建议你先用 synchronized 实现一版，压测发现瓶颈再优化。

什么时候该用 LRU

LRU 不是万能的。它适合以下几种场景：

  • 访问模式有明显的局部性：比如最近打开的文档、刚浏览的商品。
  • 数据被重复访问的概率高：热点数据会持续被命中。
  • 缓存容量不大：几万到几百万级别，太大的话哈希表和链表的指针开销会占不少内存。

我记得有一次给一个监控系统做缓存优化。他们的设备数据访问模式非常符合 LRU——最近上报的设备最常被查询。我们用 LRU 把内存占用降了 60%，查询延迟从 50ms 降到 2ms。效果立竿见影。

小总结：LRU 是基础，也是硬核面试题。你看懂上面这个实现，JDK 的 LinkedHashMap 源码基本就能秒懂了——它内部就是双向链表 + 哈希表，只是把 LRU 的逻辑封装成 removeEldestEntry 钩子方法。

LRU 缓存核心逻辑（双向链表 + 哈希表） HashMap Key1 → Node1 Key2 → Node2 Key3 → Node3 Key4 → Node4 Key5 → Node5 双向链表（最近访问 → 最久未访问） head Node1 Node2 Node3 Node4 Node5 tail 数据访问流程（get / put） O(1) 查找 淘汰：tail.prev 最久未使用（被淘汰）

最后说一句：LRU 是基础中的基础。你把这个彻底吃透，后面学 LFU、ARC、2Q 这些高级策略时，就轻松多了。先把 LRU 的代码默写出来，再谈优化。嗯，我当年就是这么干的。

← 上一章 📖 返回目录 下一章 →