蓝桥杯JavaB组之设计LRU缓存

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

---

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

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

📌 LRU 设计核心 缓存的最大容量 capacity支持 get(key) 操作（O(1) 时间复杂度）支持 put(key, value) 操作（O(1) 时间复杂度）当缓存满时，删除最近最少使用的元素

---

📖 二、解题思路 🔹 1. 使用的数据结构

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

HashMap<Integer, Node>（哈希表）：O(1) 查找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)); // 返回 1 cache.put(3, 3); // 触发淘汰 key = 2 System.out.println(cache.get(2)); // 返回 -1 (不存在) cache.put(4, 4); // 触发淘汰 key = 1 System.out.println(cache.get(1)); // 返回 -1 (不存在) System.out.println(cache.get(3)); // 返回 3 System.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() 直接插入，未删除 LRUif (map.size() > capacity) removeLRU();❌ 错误的 removeNode() 实现可能导致链表断开prev.next = next; next.prev = prev;

---

📖 七、学习建议

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

---

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

---

🎯 练习建议

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