LRU 缓存机制详解与实现（Java版） + 力扣解决

---

📌 LRU 缓存机制详解与实现（Java版）

一、📖 问题背景

在日常开发中，我们经常会使用 缓存（Cache） 来提升性能。但由于内存有限，缓存不可能无限增长，于是需要策略决定：当空间满了，谁应该被淘汰？

LRU (Least Recently Used) 缓存淘汰策略应运而生。它的含义是：

如果缓存容量满了，淘汰最近最少使用的那一项。

本题要求我们：

• 实现一个 LRUCache 类：

  • get(int key)：若 key 存在返回对应 value，否则返回 -1。
  • put(int key, int value)：写入或更新 key，若超过容量，淘汰最久未使用的 key。

• 要求 get() 和 put() 操作都必须是 O(1) 时间复杂度。

---

二、🧠 思路解析

1. O(1) 查询要求：我们需要一个哈希表

哈希表 Map<Integer, Node> 用来支持通过 key 快速查找节点。

2. O(1) 更新使用顺序：我们需要一个 双向链表

• 新使用的节点放到链表头部（最近使用）
• 最老的节点位于链表尾部（最久未使用）

为什么是双向链表？

• 删除任意节点需要 O(1) 时间（需要访问 prev 节点）
• 单向链表无法快速删除中间节点

---

三、📦 数据结构设计

class ListNode {int key, val;ListNode prev, next;
}

• 每个节点都记录 key 和 val
• 使用 虚拟头尾节点 dummyHead 和 dummyTail，简化边界处理

链表结构如下：dummyHead <-> node1 <-> node2 <-> ... <-> dummyTail

---

四、✅ 操作流程详解

🔍 get(key)

1. 如果 key 不存在，返回 -1

2. 如果 key 存在：

   • 获取对应的节点
   • 从链表中移除旧位置
   • 将该节点插入到链表头部
   • 返回 value

✏️ put(key, value)

1. 如果 key 已存在：

   • 删除旧节点

2. 如果缓存满了：

   • 删除最久未使用的节点（链表尾部的前一个节点）

3. 插入新节点到链表头部

---

五、🧩 Java 代码实现（完整版）

class LRUCache {// 双向链表节点class ListNode {int key, val;ListNode prev, next;ListNode(int key, int val) {this.key = key;this.val = val;}}Map<Integer, ListNode> map;// 存储key - node映射  加快查询速度ListNode dummyHead, dummyTail;int capacity;public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();dummyHead = new ListNode(0, 0);dummyTail = new ListNode(0, 0);dummyHead.next = dummyTail;dummyTail.prev = dummyHead;}public int get(int key) {if(!map.containsKey(key)) return -1;// 包含ListNode node = map.get(key);remove(node);// 先删除原先位置所在的节点insertToFront(new ListNode(node.key, node.val));return node.val;}public void put(int key, int value) {if(map.containsKey(key))remove(map.get(key));if(map.size() == capacity)remove(dummyTail.prev);insertToFront(new ListNode(key, value));}// 删除当前位置节点private void remove(ListNode node) {map.remove(node.key);node.prev.next = node.next;node.next.prev = node.prev;}// 将节点插入到队头  标记为“最频繁使用”private void insertToFront(ListNode node) {map.put(node.key, node);node.next = dummyHead.next;dummyHead.next.prev = node;node.prev = dummyHead;dummyHead.next = node;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

LRU缓存

---

⏱️ 时间复杂度分析

操作	时间复杂度
get	O(1)
put	O(1)

• 哈希表 O(1) 查找 key
• 双向链表 O(1) 删除和插入节点

---

🧠 思维小结

• 哈希表 + 双向链表 的组合是实现 LRU 的经典做法，广泛应用于：

  • 操作系统的内存页调度
  • Redis 缓存淘汰策略
  • 浏览器历史记录管理

---

🧱 进阶思考

1. 是否可以使用 Java 自带的 LinkedHashMap 实现？

   • 是的！LinkedHashMap 默认就是按插入顺序维护的双向链表
   • 可以通过 accessOrder=true 参数改成按“访问顺序”

2. 如果允许时间复杂度为 O(logN)，可以用 TreeMap 吗？

   • 可以，但失去了题目要求的 O(1) 特性

---

🔚 总结

实现 LRU 缓存的核心是：

用 HashMap 加速查找 + 双向链表维护访问顺序

这一组合思想，是很多设计类题目的范式和精华。

---

🔖 附录：测试用例

LRUCache cache = new LRUCache(2);
cache.put(1, 1);    // cache: {1=1}
cache.put(2, 2);    // cache: {1=1, 2=2}
cache.get(1);       // 返回 1, cache 更新为 {2=2, 1=1}
cache.put(3, 3);    // 淘汰 key=2, cache: {1=1, 3=3}
cache.get(2);       // 返回 -1 (不存在)
cache.put(4, 4);    // 淘汰 key=1, cache: {3=3, 4=4}
cache.get(1);       // 返回 -1
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

---