146. LRU缓存#

从生活中理解LRU#

想象你有一个小书架，上面只能放5本书。每当你需要看一本新书时，都会把它放在最容易拿到的位置（书架最前面）。当书架满了，你需要拿新书时，就会把最久没看（书架最后面）的那本书拿走。这就是LRU（Least Recently Used，最近最少使用）缓存的核心思想。

渐进式思考#

让我们一步步深入理解这个问题：

第一步：我们需要什么基本功能？#

快速查找：能够迅速找到我们要的数据
快速插入：能够迅速放入新数据
快速删除：能够迅速删除最久未使用的数据
更新访问顺序：每次访问数据时，都要把它标记为”最近使用”

第二步：单一数据结构能解决吗？#

数组：查找慢(O(n))
链表：查找慢(O(n))，但更新顺序快(O(1))
哈希表：查找快(O(1))，但无法维护顺序

第三步：组合数据结构的妙用#

如果我们把哈希表和双向链表组合使用：

哈希表负责快速查找
双向链表负责维护访问顺序这就是LRU缓存的经典实现方式！

问题描述#

题目目标#

LeetCode第146题”LRU缓存”要求我们实现这样一个数据结构： 1. 初始化一个固定大小的缓存 2. get(key)：如果key存在则返回value，否则返回-1 3. put(key, value)：插入或更新键值对 4. 所有操作的时间复杂度都必须是O(1)

示例 1#

输入：

["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

text

输出： [null,null,null,1,null,-1,null,-1,3,4] 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

补充说明#

链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。

详细设计#

首先，我们需要一个双向链表节点：

class DLinkedNode {
    int key;              // 键：用于在哈希表中索引
    int value;            // 值：缓存中真正存储的数据
    DLinkedNode prev;     // 前驱指针：支持 O(1) 删除当前节点
    DLinkedNode next;     // 后继指针：支持 O(1) 插入到头部
    public DLinkedNode() {} // 无参构造：用于创建虚拟头/尾节点
    public DLinkedNode(int key, int value) {
        // 初始化普通数据节点的 key/value
        this.key = key;
        this.value = value;
    }
}

java

然后是LRU缓存的完整实现：

class LRUCache {
    // cache：哈希表，key -> 双向链表节点，实现 O(1) 定位
    private Map<Integer, DLinkedNode> cache;
    // head/tail：双向链表的虚拟头尾节点，方便统一插入/删除逻辑
    private DLinkedNode head, tail;
    // capacity：缓存容量上限
    private int capacity;
    // size：当前缓存中实际节点数
    private int size;

    public LRUCache(int capacity) {
        // 记录容量
        this.capacity = capacity;
        // 初始化哈希表
        cache = new HashMap<>();

        // 初始化双向链表哨兵节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        // 建立 head <-> tail 的初始连接
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        // 通过哈希表 O(1) 查找节点
        DLinkedNode node = cache.get(key);
        // 未命中缓存，返回 -1
        if (node == null) {
            return -1;
        }
        // 命中后将该节点移动到链表头部，表示“最近使用”
        moveToHead(node);
        // 返回缓存值
        return node.value;
    }

    public void put(int key, int value) {
        // 先查 key 是否已存在
        DLinkedNode node = cache.get(key);

        if (node == null) {
            // 不存在：创建新节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 写入哈希表
            cache.put(key, newNode);
            // 新节点放到链表头（最近使用）
            addToHead(newNode);
            // 元素计数 +1
            size++;

            // 若超过容量，淘汰链表尾部（最久未使用）节点
            if (size > capacity) {
                // removeTail 返回被淘汰的真实节点
                DLinkedNode tail = removeTail();
                // 同步从哈希表删除
                cache.remove(tail.key);
                // 元素计数 -1
                size--;
            }
        } else {
            // 已存在：更新值
            node.value = value;
            // 并移动到头部，更新“最近使用”顺序
            moveToHead(node);
        }
    }

    // 辅助方法：把节点插入到 head 后（标记为最近使用）
    private void addToHead(DLinkedNode node) {
        // node <-> head.next 之间插入到 head 后
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // 辅助方法：从双向链表中摘除任意节点（O(1)）
    private void removeNode(DLinkedNode node) {
        // 前驱直接连后继，跳过 node
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 辅助方法：把某节点移动到头部（先删后插）
    private void moveToHead(DLinkedNode node) {
        // 先从原位置移除
        removeNode(node);
        // 再插入头部
        addToHead(node);
    }

    // 辅助方法：移除并返回尾部真实节点（最久未使用）
    private DLinkedNode removeTail() {
        // tail.prev 是最后一个真实数据节点
        DLinkedNode res = tail.prev;
        // 将其从链表中删除
        removeNode(res);
        // 返回被删除节点，供上层从哈希表移除
        return res;
    }
}

java

图解过程#

让我们看一个具体例子，假设缓存容量为3：

1) 初始状态：
head ⇔ tail

2) put(1,1):
head ⇔ 1 ⇔ tail

3) put(2,2):
head ⇔ 2 ⇔ 1 ⇔ tail

4) get(1):  // 1被访问，移到头部
head ⇔ 1 ⇔ 2 ⇔ tail

5) put(3,3):
head ⇔ 3 ⇔ 1 ⇔ 2 ⇔ tail

6) put(4,4):  // 超出容量，删除最久未使用的2
head ⇔ 4 ⇔ 3 ⇔ 1 ⇔ tail

plaintext

性能分析#

时间复杂度：所有操作都是O(1)
- get操作：哈希表查找O(1)，移动节点O(1)
- put操作：哈希表操作O(1)，链表操作O(1)
空间复杂度：O(capacity)
- 哈希表和双向链表各存储最多capacity个元素

实现技巧#

使用虚拟头尾节点简化边界处理
双向链表便于节点的删除
哈希表存储key到节点的映射
抽取常用操作为辅助方法

实际应用场景#

LRU缓存在实际开发中应用广泛：

浏览器的前进/后退功能
数据库的缓存层
操作系统的页面置换
Redis的缓存淘汰策略

进阶思考#

如何实现并发安全的LRU缓存？
如何处理超大数据量的情况？
如何实现基于时间的过期策略？
其他缓存置换策略（LFU、FIFO等）的优劣对比？

小结#

LRU缓存的设计教会我们：

如何组合数据结构实现复杂功能
空间和时间的权衡思想
接口设计和代码组织的技巧
实际问题的抽象建模能力

记住：设计数据结构就像设计一个高效的图书管理系统，关键是在各种需求之间找到最佳平衡点！