LRU缓存设计总结

什么是LRU缓存

LRU（Least Recently Used，最近最少使用）缓存是一种常见的缓存淘汰策略。当缓存空间不足时，LRU算法会优先淘汰最久未被访问的数据，从而为新数据腾出空间。

LRU缓存的核心操作

LRU缓存需要支持两个基本操作：

获取数据（get）：如果关键字存在于缓存中，返回关键字的值，并将其标记为"最近使用"
写入数据（put）：如果关键字已存在，更新其数据值，并将其标记为"最近使用"；如果关键字不存在，将该组数据写入缓存，如果缓存已满，则淘汰"最久未使用"的数据

设计思路与挑战

设计LRU缓存的主要挑战在于：

如何在O(1)时间内判断一个元素是否在缓存中
如何在O(1)时间内找到"最久未使用"的元素
如何在O(1)时间内将一个元素标记为"最近使用"

数据结构选择

为了满足上述需求，我们需要组合使用两种数据结构：

哈希表（HashMap）：
- 提供O(1)时间的查找、插入和删除操作
- 用于快速判断一个元素是否在缓存中
双向链表（Doubly Linked List）：
- 维护元素的访问顺序
- 最近使用的元素放在链表头部
- 最久未使用的元素放在链表尾部
- 支持O(1)时间的节点移动和删除

实现思路

数据存储：
- 使用哈希表存储键到链表节点的映射
- 链表节点包含键值对信息以及前驱和后继指针
获取数据（get操作）：
- 通过哈希表O(1)时间查找节点
- 如果存在，将节点移到链表头部（表示最近使用）
- 如果不存在，返回-1或null
写入数据（put操作）：
- 如果键已存在，更新值，并将节点移到链表头部
- 如果键不存在：
  - 创建新节点，添加到链表头部
  - 将键和节点的映射添加到哈希表
  - 如果缓存已满，删除链表尾部节点（最久未使用），并从哈希表中移除对应映射
使用虚拟头尾节点：
- 简化边界条件处理
- 避免空指针异常
- 使链表操作更加统一

优化技巧

虚拟头尾节点：
- 在链表中使用虚拟头尾节点（dummy head和dummy tail）
- 简化边界情况处理，使代码更简洁
- 避免空链表判断和空指针异常
封装链表操作：
- 将常用的链表操作（如添加到头部、删除节点、移动节点）封装为辅助方法
- 提高代码可读性和可维护性
直接访问最久未使用节点：
- 通过tail.prev直接访问最久未使用的节点
- 避免遍历链表寻找最久未使用的节点

复杂度分析

时间复杂度：
- get操作：O(1) - 哈希表查找 + 链表节点移动
- put操作：O(1) - 哈希表操作 + 链表节点操作
空间复杂度：
- O(capacity) - 存储最多capacity个键值对的节点和哈希表项

代码实现

public class LRUCache {
// 定义双向链表节点
class Node {
   int key;
   int value;
   Node prev;
   Node next;

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

private int capacity;
private java.util.HashMap<Integer, Node> cache; // 存储key到节点的映射
private Node head; // 虚拟头节点
private Node tail; // 虚拟尾节点

public LRUCache(int capacity) {
   this.capacity = capacity;
   this.cache = new java.util.HashMap<>();

   // 初始化虚拟头尾节点
   head = new Node(0, 0);
   tail = new Node(0, 0);
   head.next = tail;
   tail.prev = head;
}

public int get(int key) {
   Node node = cache.get(key);
   if (node == null) {
       return -1; // 如果key不存在，返回-1
   }

   // 将访问的节点移到链表头部（表示最近使用）
   moveToHead(node);
   return node.value;
}

public void put(int key, int value) {
   Node node = cache.get(key);

   if (node != null) {
       // 如果key已存在，更新值
       node.value = value;
       // 将节点移到链表头部
       moveToHead(node);
   } else {
       // 如果key不存在，创建新节点
       Node newNode = new Node(key, value);

       // 添加到HashMap
       cache.put(key, newNode);

       // 添加到链表头部
       addToHead(newNode);

       // 如果超出容量，删除最久未使用的节点（链表尾部）
       if (cache.size() > capacity) {
           // 获取并删除链表尾部节点
           Node tail = removeTail();
           // 从HashMap中移除对应的key
           cache.remove(tail.key);
       }
   }
}

// 辅助方法：将节点移到链表头部
private void moveToHead(Node node) {
   // 从当前位置删除节点
   removeNode(node);
   // 添加到链表头部
   addToHead(node);
}

// 辅助方法：添加节点到链表头部
private void addToHead(Node node) {
   // 在head和head.next之间插入节点
   node.next = head.next;
   node.prev = head;
   head.next.prev = node;
   head.next = node;
}

// 辅助方法：删除节点
private void removeNode(Node node) {
   // 将node的前驱和后继相连，删除node
   node.prev.next = node.next;
   node.next.prev = node.prev;
}

// 辅助方法：删除链表尾部节点（最久未使用的节点）
private Node removeTail() {
   // 获取真实的尾部节点（tail.prev）
   Node realTail = tail.prev;
   // 删除该节点
   removeNode(realTail);
   // 返回被删除的节点
   return realTail;
}

// 测试LRUCache
public static void main(String[] args) {
   LRUCache cache = new LRUCache(2);

   // 测试用例
   cache.put(1, 1); // 缓存是 {1=1}
   cache.put(2, 2); // 缓存是 {1=1, 2=2}
   System.out.println(cache.get(1));    // 返回 1
   cache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
   System.out.println(cache.get(2));    // 返回 -1 (未找到)
   cache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
   System.out.println(cache.get(1));    // 返回 -1 (未找到)
   System.out.println(cache.get(3));    // 返回 3
   System.out.println(cache.get(4));    // 返回 4
}
} 
取 消保 存

LRU缓存设计总结

什么是LRU缓存

LRU缓存的核心操作

设计思路与挑战

数据结构选择

实现思路

优化技巧

复杂度分析

代码实现

欢迎联系