题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

思路

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

  • 双向链表：最近使用的发到链表头，按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
  • 哈希表：为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。作用：快速定位节点，和链表保持数据一致性，确保淘汰过程正确，控制容量

get和put操作流程

get流程：

  1. 判断key是否存在，不存在则返回-1
  2. key存在，难到这个key的节点Node，并将当前这个Node移动到链表的头部
  3. 返回Node结点的value

put流程：

  1. 判断key是否存在哈希表中，不存在，则使用key和calue创建应该新的节点Node，并将这个Node添加到链表的头部，再判断链表中的节点数是否超过容量，超出则删除链表尾部节点Node 和 哈希表中对应的项
  2. 如果key存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

通过分析上面的流程分析，我们需要定义几个数据结构和方法

  • 节点Node的定义：使用双向链表
    • 优点：快速移动到头节点，快速删除尾部节点，维护访问顺序
    • 代码：
      class DLinkedNode {int key;int value;// 前节点DLinkedNode prev;// 后节点DLinkedNode next;// 无参构造public DLinkedNode() {}// 构造public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
}
  • 删除节点：
    private void removeNode(DLinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;
}
  • 删除尾节点：
private DLinkedNode removeTail() {DLinkedNode res = tail.prev;removeNode(res);return res;
}
  • 新增节点：在头部添加
    private void addToHead(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;
}
  • Node移动到头部的操作：removeToHead
    private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);
}
  • LRUCache参数：初始化容量、实时容量、map缓存、头尾节点
    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
// 实时记录缓存元素数量：跟踪当前缓存中的数据量，用于容量控制
private int size;
// 容量阈值：定义缓存最大承载量
private int capacity;
// head：表操作锚点：作为双向链表的固定起始点，简化头部插入操作
// tail：LRU节点标识：标记链表末端，便于快速定位待淘汰节点
private DLinkedNode head, tail;
  • 初始化zhegLRUCache
    public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;
}
  • get操作
    public int get(int key) {DLinkedNode node = cache.get(key);if (node == null) {return -1;}// 如果 key 存在，先通过哈希表定位，再移到头部moveToHead(node);return node.value;
}
  • put 操作
    public void put(int key, int value) {DLinkedNode node = cache.get(key);if (node == null) {// 如果 key 不存在，创建一个新的节点DLinkedNode newNode = new DLinkedNode(key, value);// 添加进哈希表cache.put(key, newNode);// 添加至双向链表的头部addToHead(newNode);++size;if (size > capacity) {// 如果超出容量，删除双向链表的尾部节点DLinkedNode tail = removeTail();// 删除哈希表中对应的项cache.remove(tail.key);--size;}}else {// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部node.value = value;moveToHead(node);}
}

算法

public class LRUCache {class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int _key, int _value) {key = _key; value = _value;}}private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();private int size;private int capacity;private DLinkedNode head, tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkedNode node = cache.get(key);if (node == null) {return -1;}// 如果 key 存在，先通过哈希表定位，再移到头部moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if (node == null) {// 如果 key 不存在，创建一个新的节点DLinkedNode newNode = new DLinkedNode(key, value);// 添加进哈希表cache.put(key, newNode);// 添加至双向链表的头部addToHead(newNode);++size;if (size > capacity) {// 如果超出容量，删除双向链表的尾部节点DLinkedNode tail = removeTail();// 删除哈希表中对应的项cache.remove(tail.key);--size;}}else {// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部node.value = value;moveToHead(node);}}private void addToHead(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(DLinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}private DLinkedNode removeTail() {DLinkedNode res = tail.prev;removeNode(res);return res;}
}

但是在日常工作中，还是直接使用LinkedHashMap便可以了

  • 插入模式（默认）： 新节点追加至链表尾部

    示例插入顺序 A → B → C → D

  • 访问模式

    • accessOrder=true：访问/插入节点均移至尾部，LRU缓存淘汰策略
      • （accessOrder=true）： 被访问节点移至链表尾部

        访问B后的顺序 A → C → D → B

    • 默认值：新节点始终追加尾部，保留原始插入顺序
class LRUCache extends LinkedHashMap<Integer, Integer>{private int capacity;public LRUCache(int capacity) {// accessOrder=truesuper(capacity, 0.75F, true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {// 触发淘汰最久未使用项return size() > capacity; }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/web/86278.shtml
繁体地址，请注明出处：http://hk.pswp.cn/web/86278.shtml
英文地址，请注明出处：http://en.pswp.cn/web/86278.shtml

如若内容造成侵权/违法违规/事实不符，请联系英文站点网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Go Web开发框架实践：模板渲染与静态资源服务

Go Web开发框架实践：模板渲染与静态资源服务

Gin 不仅适合构建 API 服务&#xff0c;也支持 HTML 模板渲染和静态资源托管&#xff0c;使其可以胜任中小型网站开发任务。 一、模板渲染基础 1. 加载模板文件 使用 LoadHTMLGlob 或 LoadHTMLFiles 方法加载模板&#xff1a; r : gin.Default() r.LoadHTMLGlob("templ…
阅读更多...
缓存与加速技术实践-Kafka消息队列

缓存与加速技术实践-Kafka消息队列

目录 #1.1消息队列 1.1.1什么是消息队列 1.1.2消息队列的特征 1.1.3为什么需要消息队列 #2.1ksfka基础与入门 2.1.1kafka基本概念 2.1.2kafka相关术语 2.1.3kafka拓扑架构 #3.1zookeeper概述介绍 3.1.1zookeeper应用举例 3.1.2zookeeper的工作原理是什么&#xff1f; 3.1.3z…
阅读更多...
鸿蒙前后端部署教程

鸿蒙前后端部署教程

第一步&#xff1a;部署Java后端 打开IDEA编辑器 第二步&#xff1a;用DevEco Studio运行鸿蒙端项目 然后按WinR键调出Win的命令行&#xff0c;输入ipconfig 打开后端IDEA可以查看数据库情况&#xff0c;如下图
阅读更多...
Python 常用定时任务框架介绍及代码举例

Python 常用定时任务框架介绍及代码举例

文章目录 Python 常用定时任务框架简介&#x1f9e9; 一、轻量级方案&#xff08;适合简单任务&#xff09;1. **schedule库** ⚙️ 二、中级方案&#xff08;平衡功能与复杂度&#xff09;2. **APScheduler**3. **Celery Celery Beat** &#x1f680; 三、异步专用方案&#…
阅读更多...
使用redis服务的redisson架构实现分布式锁

使用redis服务的redisson架构实现分布式锁

加锁 /*** 尝试为指定的许可证 ID 获取分布式锁。如果锁已被占用&#xff0c;则立即抛出业务异常。** param licenseId 需要加锁的许可证 ID&#xff08;即锁名称&#xff09;* return true 表示成功获取锁&#xff0c;但请注意&#xff1a;* 锁实际持有时间为 30 秒…
阅读更多...
HTML表格元素

HTML表格元素

HTML表格元素深度解析与实战应用 一、表格基本结构与语义化 1. 基础表格元素详解 <table> 容器元素 核心作用&#xff1a;定义表格容器重要属性&#xff1a; border&#xff1a;已废弃&#xff0c;应使用CSS设置边框aria-label/aria-labelledby&#xff1a;为屏幕阅读…
阅读更多...
如何使用 Dockerfile 创建自定义镜像

如何使用 Dockerfile 创建自定义镜像

使用 Dockerfile 创建自定义镜像的过程非常清晰&#xff0c;通常包括定义基础镜像、安装依赖、复制代码、设置环境变量和启动命令等步骤。下面详细讲解从零创建自定义镜像的完整流程。 一、什么是 Dockerfile&#xff1f; Dockerfile 是一个文本文件&#xff0c;定义了如何构建…
阅读更多...
设置AWS EC2默认使用加密磁盘

设置AWS EC2默认使用加密磁盘

问题 EC2磁盘需要使用默认加密。这里需要设置一下默认加密。 EC2
阅读更多...
【树的概念及其堆的实现】

【树的概念及其堆的实现】

树的概念及其堆的实现 1.树的概念2.树的相关概念3.二叉树的概念4. 满二叉树和完全二叉树5.二叉树的存储结构6.二叉树顺序结构的实现的7.堆的结构及其实现 1.树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系…
阅读更多...
鸿蒙系统（HarmonyOS）经典红色风格登录页布局

鸿蒙系统（HarmonyOS）经典红色风格登录页布局

预览 简介 基于鸿蒙系统&#xff08;HarmonyOS&#xff09;开发的现代化登录界面&#xff0c;采用了科技感十足的红色主题设计。该界面结合了流畅的动画效果、精心设计的视觉元素和人性化的交互体验&#xff0c;为用户提供了一个安全、美观且易用的登录入口。 &#x1f3a8; …
阅读更多...
C++虚函数多态

C++虚函数多态

class C{ public:void x1(){};void x2(){};};C c; cout << sizeof(c) <<"\n";1字节 class D{ public:void x1(){};void x2(){};virtual void x3(){};//void *vptr看不见的虚函数表指针 }; D d; cout << sizeof(d) <<"\n";8字节类A…
阅读更多...
新编辑器编写指南--给自己的备忘

新编辑器编写指南--给自己的备忘

欢迎使用Markdown编辑器 你好&#xff01; 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章&#xff0c;了解一下Markdown的基本语法知识。 新的改变 我们对Markdown编辑器进行了一些功能拓展与语法支持&#x…
阅读更多...
目标检测neck算法之MPCA和FSA的源码实现

目标检测neck算法之MPCA和FSA的源码实现

目标检测neck算法之MPCA和FSA的源码实现 使用BIBM2024 Spatial-Frequency Dual Domain Attention Network For Medical Image Segmentation的Frequency-Spatial Attention和Multi-scale Progressive Channel Attention改进neck. 接下来&#xff0c;我将讲解它的源码操作的实现…
阅读更多...
MyBatis-Plus的3.5.7和PageHelper的那个版本对应

MyBatis-Plus的3.5.7和PageHelper的那个版本对应

MyBatis-Plus的3.5.7和PageHelper的那个版本对应 根据你的知识库中提到的信息&#xff1a; MyBatis-Plus 3.5.7 使用的是 JSqlParser 4.6 版本。PageHelper 若使用了不同版本的 JSqlParser&#xff08;如 4.7&#xff09;&#xff0c;会导致冲突。 ✅ 推荐对应关系 为了保证…
阅读更多...
Apifox 6 月产品更新｜支持 AI 能力、交互优化、在线文档新增 SEO 设置、gRPC 项目支持前/后置操作

Apifox 6 月产品更新｜支持 AI 能力、交互优化、在线文档新增 SEO 设置、gRPC 项目支持前/后置操作

在 2025 年的 API 开发领域&#xff0c;Apifox 作为一款集 API 设计、调试、Mock 和测试于一体的协作平台&#xff0c;已成为开发者的“得力助手”。然而&#xff0c;随着业务需求的不断增长&#xff0c;开发者对工具的效率和功能提出了更高的要求。6 月份&#xff0c;Apifox 推…
阅读更多...
Acrobat JavaScript 从浏览器到 PDF 环境的转换

Acrobat JavaScript 从浏览器到 PDF 环境的转换

目录 什么是 JavaScript？JavaScript 核心语言与 Acrobat 特定 API学习 JavaScript 核心语言的挑战浏览器与 Acrobat JavaScript 的关键差异在 Acrobat 中运行 JavaScript 代码替代浏览器特定函数的方法后续学习建议什么是 JavaScript？ JavaScript 最初于 1995 年作为 Netsca…
阅读更多...
OpenCV CUDA模块设备层-----指数运算函数exp()

OpenCV CUDA模块设备层-----指数运算函数exp()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 OpenCV 的 CUDA 设备端数学函数 中的一个内联函数&#xff0c;用于在 GPU 上对 uchar1 类型&#xff08;单通道图像像素&#xff09;执行指数运算…
阅读更多...
C++面向对象5——C++关键字、构造函数与拷贝构造函数

C++面向对象5——C++关键字、构造函数与拷贝构造函数

this关键字 C关键字this的深度解析 1. this指针的本质 在C中&#xff0c;this是一个特殊的隐式指针&#xff0c;它存在于每个非静态成员函数内部&#xff0c;指向调用该函数的当前对象。其类型为&#xff1a; 对于非const成员函数&#xff1a;ClassName* const&#xff08;…
阅读更多...
人工智能专业：探索未来的智慧前沿

人工智能专业：探索未来的智慧前沿

亲戚家的小孩刚高考完&#xff0c;问我人工智能专业是学什么、做什么的。趁机就写一篇吧&#xff01; 人工智能专业&#xff1a;探索未来的智慧前沿 人工智能&#xff08;Artificial Intelligence&#xff0c;简称AI&#xff09;无疑是当今最热门、最具颠覆性的技术之一。它正…
阅读更多...
618风控战升级，瑞数信息“动态安全+AI”利剑出鞘

618风控战升级，瑞数信息“动态安全+AI”利剑出鞘

每年的618电商促销季&#xff0c;都是各大电商平台和商家的兵家必争之地。数以亿计的消费者涌入线上平台&#xff0c;期待已久的优惠券、秒杀商品如潮水般涌现&#xff0c;海量交易在瞬间达成&#xff0c;无疑是一场商业狂欢。 然而&#xff0c;在这场狂欢背后&#xff0c;自动…
阅读更多...
最新文章

Copyright @ 2022~2023