忍者算法

Appearance

从生活场景到LRU缓存：优雅实现高性能数据访问 ​

从生活中理解LRU ​

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

渐进式思考 ​

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

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

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

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

  • 数组：查找慢(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)

详细设计 ​

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

java
class DLinkedNode {
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;
    public DLinkedNode() {}
    public DLinkedNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

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

java
class LRUCache {
    // 核心数据结构
    private Map<Integer, DLinkedNode> cache;
    private DLinkedNode head, tail;  // 虚拟头尾节点
    private int capacity;
    private int size;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        
        // 初始化双向链表
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 将访问的节点移到头部
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        
        if (node == null) {
            // 创建新节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            
            // 如果超出容量，删除尾部节点
            if (size > capacity) {
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        } else {
            // 更新已存在节点的值
            node.value = value;
            moveToHead(node);
        }
    }
    
    // 辅助方法：将节点添加到头部
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    // 辅助方法：移除节点
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    // 辅助方法：将节点移到头部
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    
    // 辅助方法：移除尾部节点
    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

图解过程 ​

让我们看一个具体例子，假设缓存容量为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

性能分析 ​

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

实现技巧 ​

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

实际应用场景 ​

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

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

进阶思考 ​

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

小结 ​

LRU缓存的设计教会我们：

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

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

作者：忍者算法 公众号：忍者算法

📚 回复【刷题清单】获取更多经典题目解析 👥 回复【加群】加入算法/面试交流群，一起学习进步 🧑‍💻 回复【代码】获取GitHub完整题解项目，包含Java/Python/JavaScript/Go/C++多语言实现