当前位置： 首页 > news >正文

【LeetCode】LRU 缓存 题解

news 2025/7/28 8:11:55

什么是 LRU Cache？

LRU (Least Recently Used) 缓存是一种常用的缓存淘汰策略，当缓存满了需要删除数据时，优先删除最久未使用的数据。

核心思想

LRU Cache 需要同时满足两个要求：

  1. 快速访问：O(1) 时间复杂度的 get 和 put 操作
  2. 维护访问顺序：能够快速找到最久未使用的元素

数据结构设计

为了同时满足上述要求，我们使用 HashMap + 双向链表 的组合：

  • HashMap：提供 O(1) 的查找速度
  • 双向链表：维护元素的使用顺序，头部是最久未使用的，尾部是最近使用的
public class LRUCache {private int capacity;private Map<Integer, Node> cacheMap = new HashMap<>();private DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
}

核心操作

1. GET 操作

public int get(int key) {Node node = cacheMap.get(key);if (node == null) {return -1;  // 未找到} else {// 将访问的节点移到链表尾部（标记为最近使用）doubleLinkedList.moveToLast(node);return node.value;}
}

2. PUT 操作

public void put(int key, int value) {Node newNode = doubleLinkedList.add(key, value);Node existNode = cacheMap.get(key);// 如果超过容量限制if ((cacheMap.size() + 1) > capacity && !cacheMap.isEmpty()) {if (existNode != null) {// 更新已存在的键doubleLinkedList.removeNode(existNode);} else {// 删除最久未使用的元素（链表头部）Node removeNode = doubleLinkedList.removeHeadNode();cacheMap.remove(removeNode.key);}} else {// 容量未满，但键已存在，需要更新if (existNode != null) {doubleLinkedList.removeNode(existNode);}}// 存放新元素cacheMap.put(key, newNode);
}

双向链表实现

节点结构

public class Node {int key;int value;Node next;Node prev;
}

关键方法：移动到链表尾部

public void moveToLast(Node node) {if (node.next == null) {return; // 已经是尾节点}if (node.prev == null) {// 头节点情况node.next.prev = null;head = node.next;} else {// 中间节点情况node.prev.next = node.next;node.next.prev = node.prev;}// 移动到尾部tail.next = node;node.prev = tail;tail = node;node.next = null;
}

测试示例

LRUCache cache = new LRUCache(2);cache.put(1, 1);  // 缓存: {1=1}
cache.put(2, 2);  // 缓存: {1=1, 2=2}
cache.get(1);     // 返回 1，缓存: {2=2, 1=1}
cache.put(3, 3);  // 移除 key 2，缓存: {1=1, 3=3}
cache.get(2);     // 返回 -1 (未找到)
cache.get(3);     // 返回 3
cache.get(1);     // 返回 1

关键要点

  1. 双向链表：能够快速删除中间节点
  2. HashMap存储节点引用：实现 O(1) 查找
  3. 尾插法：新元素和最近访问的元素都放在链表尾部
  4. 头删法：容量满时删除链表头部的最久未使用元素

时间复杂度

  • GET 操作：O(1)
  • PUT 操作：O(1)
  • 空间复杂度：O(capacity)

完整代码

public class LRUCache {// 容量int capacity;// 缓存 MapMap<Integer, DoubleLinkedList.Node> cacheMap = new HashMap<>();DoubleLinkedList doubleLinkedList = new DoubleLinkedList();public LRUCache(int capacity) {this.capacity = capacity;}public int get(int key) {// 1. 查找元素DoubleLinkedList.Node valueNode = cacheMap.get(key);// 1.1 没找到元素的情况if (Objects.isNull(valueNode)) {return -1;} else {// 1.2 找到元素的情况// 更新双向链表中节点的顺序doubleLinkedList.moveToLast(valueNode);return valueNode.value;}}public void put(int key, int value) {DoubleLinkedList.Node newNode = doubleLinkedList.add(key, value);DoubleLinkedList.Node existNode = cacheMap.get(key);// 超过容量限制if ((cacheMap.size() + 1) > capacity && !cacheMap.isEmpty()) {// Map key 重复的情况if (!Objects.isNull(existNode)) {doubleLinkedList.removeNode(existNode);} else {// 剔除最长未使用的元素，放入新元素DoubleLinkedList.Node removeNode = doubleLinkedList.removeHeadNode();// 移除最老未使用的元素cacheMap.remove(removeNode.key);}} else {// Map key 重复的情况if (!Objects.isNull(existNode)) {// 剔除指定的 existNode 元素doubleLinkedList.removeNode(existNode);}}// 存放新元素cacheMap.put(key, newNode);}class DoubleLinkedList {// 头节点指针DoubleLinkedList.Node head;// 尾节点指针DoubleLinkedList.Node tail;public void printList() {Node current = head;System.out.print("链表顺序: ");while (current != null) {System.out.print(current.key);if (current.next != null) {System.out.print(" -> ");}current = current.next;}System.out.println();}/*** 节点*/public class Node {int key;int value;// 指向后一个节点指针DoubleLinkedList.Node next;// 指向钱一个节点指针DoubleLinkedList.Node prev;}/*** 添加元素(尾插法)*/public DoubleLinkedList.Node add(int key, int value) {// 1. 空链表的情况DoubleLinkedList.Node newNode = initNodeValue(key, value);if (head == null) {// 头节点指向当前节点head = newNode;// 尾节点指向当前节点tail = newNode;} else {// 2. 非空链表的情况// 节点指向新节点tail.next = newNode;// 新节点操作newNode.prev = tail;newNode.next = null;// 尾节点指向新的节点tail = newNode;}return newNode;}/*** 双向链表移除第一个节点*/public DoubleLinkedList.Node removeHeadNode() {// 空链表if (head == null) {return null;}// 记录保存第一个节点DoubleLinkedList.Node firstNode = head;// 只有一个节点的情况if (head == tail) {// 把这个节点清理掉head = null;tail = null;} else {// 第二个节点当头节点啦head.next.prev = null;// head 指向第二个节点head = head.next;}// 第一个节点断手断尾firstNode.prev = null;firstNode.next = null;return firstNode;}/*** 双向链表移除最后一个节点*/public DoubleLinkedList.Node removeTailNode() {// 空链表if (head == null) {return null;}// 记录保存最后一个节点DoubleLinkedList.Node oldLastNode = tail;// 只有一个节点的情况if (head == tail) {// 把这个节点清理掉head = null;tail = null;} else {// 多个节点的情况// tail 指向前一个节点tail = tail.prev;// 断开尾节点tail.next = null;}oldLastNode.prev = null;oldLastNode.next = null;return oldLastNode;}/*** 移除指定节点*/public void removeNode(Node node) {if (node.prev == null) {// 头节点的情况，移除头节点removeHeadNode();return;}if (node.next == null) {// 尾节点的情况，移除尾节点removeTailNode();return;}// 断开当前 node 节点的前后指针node.prev.next = node.next;node.next.prev = node.prev;// 断开当前的 node 节点，等着被垃圾回收器回收node.prev = null;node.next = null;}public void moveToLast(Node node) {// 尾节点的情况if (node.next == null) {// 本次链表用的是尾插法，已经是尾了，不用再做操作啦return;}// 首节点的情况if (node.prev == null) {// 下一个节点变为首节点node.next.prev = null;head = node.next;// 当前节点移到最后，成为尾节点tail.next = node;node.prev = tail;tail = node;node.next = null;return;}// 中间节点的情况node.prev.next = node.next;node.next.prev = node.prev;tail.next = node;node.prev = tail;tail = node;node.next = null;}private DoubleLinkedList.Node initNodeValue(int key, int value) {DoubleLinkedList.Node node = new DoubleLinkedList.Node();node.key = key;node.value = value;node.prev = null;node.next = null;return node;}}}

总结

LRU Cache 的核心在于巧妙地结合 HashMap 和双向链表：

  • HashMap 解决了快速查找的问题
  • 双向链表解决了维护访问顺序的问题
  • 通过将最近访问的元素移到链表尾部，最久未使用的元素自然就在链表头部

这种设计既保证了操作的高效性，又满足了 LRU 策略的需求。

http://www.xdnf.cn/news/1198063.html

相关文章：

  • MySQL 全详解：从入门到精通的实战指南
  • LeetCode 刷题【16. 最接近的三数之和、17. 电话号码的字母组合】
  • 【前端】【vscode】【.vscode/settings.json】为单个项目配置自动格式化和开发环境
  • 关系与逻辑运算 —— 寄存器操作的 “入门钥匙”
  • 分布式系统中Token续期问题解决方案
  • AIC 2025 热点解读：如何构建 AI 时代的“视频神经中枢”？
  • 四、搭建springCloudAlibaba2021.1版本分布式微服务-加入openFeign远程调用和sentinel流量控制
  • 嵌入式——单片机的独立按键
  • git stash 命令详解
  • leetcode_560 和为K的子数组
  • C语言——————学习笔记（自己看）
  • 2025.7.27总结—新励成
  • Leetcode 3629. Minimum Jumps to Reach End via Prime Teleportation
  • 学习游戏制作记录（改进投掷剑的行为）7.27
  • 孤儿进程、僵尸进程和守护进程
  • 【element-ui】HTML引入本地文件出现font找不到/fonts/element-icons.woff
  • Android CameraX 使用指南：简化相机开发
  • 从零搭建3D激光slam框架-基于mid360雷达节点实现
  • [10月考试] C
  • 论文阅读-IGEV
  • Java进阶7：Junit单元测试
  • Windows10系统使用Cmake4.1.0构建工具+Visual Studio2022编译Opencv4.11教程
  • LabelImg：简洁高效的图像标注工具和下载
  • B站直播视频 | 深度讲解 Yocto 项目：从历史、架构到实战与趋势
  • Vue vuex模块化编码
  • 网络基础19：OSPF多区域实验
  • 中级全栈工程师笔试题
  • Maven之多模块项目管理
  • 什么是加密货币中的节点？
  • 【Linux系统编程】环境变量，进程地址空间与进程控制