缓存淘汰算法LRU

本文目录导读：

1. 核心工作原理
2. LRU 的典型实现方式（Java 示例）
3. 复杂度分析
4. 实际应用场景
5. LRU 的变体与改进

LRU（Least Recently Used，最近最少使用） 是一种常用的缓存淘汰策略。

它的核心思想是：如果一个数据在最近一段时间内被访问过，那么它在将来被访问的概率也更高。 当缓存空间满了，需要淘汰数据时，LRU 会优先淘汰那些最久没有被访问的数据。

核心工作原理

LRU 算法基于一个简单的假设：“时间局部性”（最近被访问的数据很可能很快再次被访问）和 “空间局部性”。

• 访问数据：当数据被访问（读或写）时，将其移动到缓存的最“新鲜”或“最近使用”的一端。
• 淘汰数据：当缓存容量达到上限需要腾出空间时，移除缓存中“最久没有使用”的一端的数据。

想象一个记事本,你按照时间顺序记录最近查阅过的书籍名字。

• 最近查阅的书,写在最上面。
• 当你需要查阅一本不同的书，就把它写在最上面,并把旧记录往下挤。
• 如果笔记本写满了，想记新书，就必须把最底下那本（最久没看的）划掉。

LRU 的典型实现方式（Java 示例）

LRU 通常通过一种经典的组合数据结构实现：哈希表（HashMap）+ 双向链表（Doubly Linked List）。

• 哈希表：提供 O(1) 的查找速度，通过 key 立即找到对应的链表节点。
• 双向链表：维护数据的访问顺序，越靠近链表头部，数据越新（最近使用）；越靠近链表尾部，数据越旧（最久未使用）。

操作流程：

1. 获取数据 (get)：

   • key 存在于哈希表中,通过哈希表找到链表中的节点。
   • 将该节点从当前位置删除，并插入到链表头部（标记为最近使用）。
   • 返回节点的值。
   • key 不存在，返回 -1 (或 null)。

2. 写入数据 (put)：

   • 情况 A：key 已存在，通过哈希表找到节点，更新其值，然后将节点移动到链表头部（先删后插）。
   • 情况 B：key 不存在。
     • 创建新节点，插入到链表头部,并在哈希表中添加映射。
     • 检查容量：如果添加后链表长度超过了设定的缓存容量，则从链表尾部移除一个节点（最久未使用）,并从哈希表中删除对应的键值对。

Java 代码实现（最经典的面试手写题）

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>> cache = new HashMap<>();
    // 使用虚拟头尾节点，避免处理边界情况（null判断）
    private final Node<K, V> dummyHead = new Node<>(null, null);
    private final Node<K, V> dummyTail = new Node<>(null, null);
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 初始化链表：head <-> tail
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    // 获取数据
    public V get(K key) {
        Node<K, V> node = cache.get(key);
        if (node == null) {
            return null; // 或者根据需求返回特定值
        }
        // 如果存在，将该节点移动到头部
        moveToHead(node);
        return node.value;
    }
    // 写入数据
    public void put(K key, V value) {
        Node<K, V> node = cache.get(key);
        if (node == null) {
            // 1. 创建新节点
            Node<K, V> newNode = new Node<>(key, value);
            // 2. 添加到哈希表
            cache.put(key, newNode);
            // 3. 插入到链表头部
            addToHead(newNode);
            // 4. 检查容量，如果超出则淘汰尾部节点
            if (cache.size() > capacity) {
                Node<K, V> removedNode = removeTail();
                cache.remove(removedNode.key);
            }
        } else {
            // 更新值并移动到头部
            node.value = value;
            moveToHead(node);
        }
    }
    // 将节点移动到链表头部
    private void moveToHead(Node<K, V> node) {
        removeNode(node);
        addToHead(node);
    }
    // 在头部添加节点
    private void addToHead(Node<K, V> node) {
        node.prev = dummyHead;
        node.next = dummyHead.next;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }
    // 移除一个节点（从链表中解除连接）
    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    // 移除尾部节点（真正的最近最少使用）
    private Node<K, V> removeTail() {
        Node<K, V> realTail = dummyTail.prev;
        removeNode(realTail);
        return realTail;
    }
}

复杂度分析

得益于哈希表和双向链表的组合，LRU 的读写操作都非常高效。

实际应用场景

• 操作系统：虚拟内存页置换（部分场景）、文件系统缓存。
• 数据库：MySQL 的 Buffer Pool（管理缓存的数据页），Redis 的淘汰策略之一（allkeys-lru、volatile-lru）。
• Web 开发：浏览器的本地缓存、CDN 缓存、Spring Cache（可以配置为基于 LRU 的缓存管理器，如 Caffeine）。
• 计算机硬件：CPU 的 L1/L2/L3 缓存（通常使用类 LRU 或伪 LRU 算法）。

LRU 的变体与改进

• LRU-K：记录最近 K 次访问时间，而不是仅 1 次，能更好地抵御“批量扫描”污染缓存（比如一次性扫描大量数据导致热点数据被错误淘汰）。
• Two Queues (2Q)：使用两个队列（FIFO 和 LRU），将数据从初次进入的队列提升到高频访问的队列,进一步减少污染。
• LIRS (Low Inter-reference Recency Set)：一种更复杂的算法，在 DB2 等数据库中采用，性能通常优于 LRU。
• W-TinyLFU：在 Caffeine（Java 顶级高性能缓存库）中使用的算法，结合频率和新鲜度,抗扫描能力极强。

一句话总结：LRU 是一个 “基于访问时间” 的淘汰算法，它认为“最近用过的东西最有用”，虽然简单但有缺陷（批量扫描污染），是面试中最高频考察的缓存算法之一。