蓝桥杯 Java B 组之设计 LRU 缓存

Day 7：综合练习 - 设计 LRU 缓存

---

📖 一、什么是 LRU（Least Recently Used）缓存？

LRU（Least Recently Used）缓存是一种基于最近最少使用策略的缓存机制，用于管理固定大小的缓存，当缓存满时，会淘汰最久未被使用的元素。

📌 LRU 设计核心

1. 缓存的最大容量 capacity
2. 支持 get(key) 操作（O(1) 时间复杂度）
3. 支持 put(key, value) 操作（O(1) 时间复杂度）
4. 当缓存满时，删除最近最少使用的元素

---

📖 二、解题思路

🔹 1. 使用的数据结构

为了满足 O(1) 复杂度，我们使用：

1. HashMap<Integer, Node>（哈希表）：O(1) 查找
2. Double Linked List（双向链表）：
   • 头部存放最近访问的元素
   • 尾部存放最久未访问的元素
   • put() 时：
     • 已存在：更新值，并移到头部
     • 不存在：新建节点插入到头部，若超出 capacity，移除尾部
   • get() 时：
     • 存在：返回值，并移到头部
     • 不存在：返回 -1

---

📖 三、完整代码

✅ LRU 缓存实现

import java.util.HashMap;class LRUCache {// 定义双向链表节点class Node {int key, value;Node prev, next;public Node(int k, int v) { key = k; value = v; }}private int capacity; // 缓存容量private HashMap<Integer, Node> map; // 存储 key -> Node 映射private Node head, tail; // 头节点和尾节点（最近 & 最久未使用）public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>();// 初始化头尾节点（哨兵）head = new Node(-1, -1);tail = new Node(-1, -1);head.next = tail;tail.prev = head;}// 获取缓存中 key 对应的值public int get(int key) {if (!map.containsKey(key)) return -1;Node node = map.get(key);moveToHead(node); // 访问后移动到头部return node.value;}// 插入或更新缓存public void put(int key, int value) {if (map.containsKey(key)) {Node node = map.get(key);node.value = value; // 更新值moveToHead(node); // 移到头部} else {Node newNode = new Node(key, value);map.put(key, newNode);addToHead(newNode);if (map.size() > capacity) { // 超出容量，删除尾部removeLRU();}}}// 移动节点到头部（最近使用）private void moveToHead(Node node) {removeNode(node);addToHead(node);}// 从链表中删除节点private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}// 将节点添加到头部private void addToHead(Node node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;}// 移除最近最少使用的节点（尾部）private void removeLRU() {Node lru = tail.prev; // 取出尾部的前一个节点removeNode(lru);map.remove(lru.key);}
}// 测试 LRU 缓存
public class LRUCacheTest {public static void main(String[] args) {LRUCache cache = new LRUCache(2);cache.put(1, 1);cache.put(2, 2);System.out.println(cache.get(1)); // 返回 1cache.put(3, 3); // 触发淘汰 key = 2System.out.println(cache.get(2)); // 返回 -1 (不存在)cache.put(4, 4); // 触发淘汰 key = 1System.out.println(cache.get(1)); // 返回 -1 (不存在)System.out.println(cache.get(3)); // 返回 3System.out.println(cache.get(4)); // 返回 4}
}

---

📖 四、代码详解

🔹 1. get(key) 查询

• 在 O(1) 时间复杂度内查找 map
• 将该元素移至链表头部（表示最近访问）

🔹 2. put(key, value) 插入

• 若 key 已存在：
  • 先更新值
  • 然后移动到头部
• 若 key 不存在：
  • 创建新节点，加入 map，插入链表头部
  • 超出 capacity 时，删除尾部元素（最近最少使用）

🔹 3. moveToHead(node)

• 删除 该节点（removeNode(node)）
• 重新插入 该节点到链表头部（addToHead(node)）

🔹 4. removeLRU()

• 取出 tail.prev（尾部的前一个节点）
• 删除该节点 并移除 map 记录

---

📖 五、时间复杂度分析

操作	时间复杂度	解释
get(key)	O(1)	哈希表查找 + 维护链表
put(key, value)	O(1)	哈希表插入 + 维护链表
总复杂度	O(1)	所有操作均为 O(1)

---

📖 六、常见错误与优化

错误	描述	解决方案
❌ 忘记更新 LRU 顺序	get(key) 时未移动到头部	调用 moveToHead(node)
❌ 未考虑 capacity 超出	put() 直接插入，未删除 LRU	if (map.size() > capacity) removeLRU();
❌ 错误的 removeNode() 实现	可能导致链表断开	prev.next = next; next.prev = prev;

---

📖 七、学习建议

✅ 熟练掌握 HashMap + 双向链表 组合数据结构
✅ 练习 LRU 相关题目，如 LRUCache、LFUCache
✅ 理解 O(1) 操作如何使用 HashMap 维护索引

---

📖 八、总结

考点	数据结构	时间复杂度
LRU 缓存	HashMap + 双向链表	O(1) 查询 & 插入

---

🎯 练习建议

1. 实现 LFU（Least Frequently Used）缓存（结合最小堆）
2. 扩展：支持不同的淘汰策略（FIFO、LFU、MRU）
3. 面试常见问题：如何优化 LRU？如何并发安全？