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

LRU缓存

news 来源：原创 2025/7/20 15:26:16

什么是LRU缓存?

LRU（Least Recently Used）是最近最少使用算法，是操作系统中用于分页置换的算法，如果要向内存中添加分页，并且内存分页已满的情况下，就选出最近一段时间最不常用的分页进行置换（例如将最不常用的分页暂时放到磁盘，这时内存就有一个空闲分页，将新增分页放过来即可）。

题目

链接：leetcode.146. LRU 缓存

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

实现 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) 的平均时间复杂度运行。

分析

一、容器内容的设计

我们可以用一个容器对数据进行缓存，第一个元素表示最近最不经常使用，最后一个元素表示最近最经常使用，从前往后依次过渡

二、数据结构的选型

① 使用数组

假设将内容全部用数组进行缓存

现在使用元素2，那么应该将2移到尾部，3、4、5全部向前移动。这样查询的时间复杂度为O(1)，移动的时间复杂度为O(n)。

那么题目要求的get时间复杂度就为O(n)，put时间复杂度为O(n)。显然不能使用数组。

② 使用链表

如果使用元素2，那么需要找到元素2，然后将元素2放到尾部即可。这样查询的时间复杂度为O(n)，移动的时间复杂度为O(1)，

显然对于查询操作我们可以使用哈希去优化，使得查询的时间复杂度为O(1)

③ 哈希+ 链表

这样查询2只需要通过key映射，查询效率为O(1)，将2移动到链表尾部，1指向3即可，移动效率为O(1)，完美!

但是这里有个问题，我们通过key定位到元素2时，如何获取2前面的元素？

聪明的小伙伴已经想出来了，答案就是将单链表变为双向链表

④ 哈希 + 双向链表

这样不管是查询还是移动，复杂度都是O(1)

解答

① 设计双向链表节点结构

class ListNode {//	节点前驱ListNode pre;//	节点后继ListNode next;//	哈希中的keyint key;//	数据域，记录缓存内容int val;//	构造函数public ListNode() {}public ListNode(int key, int val) {this.key = key;this.val = val;}
}

这里节点中为什么要设计key呢？因为如果添加元素时缓存区已满，就需要删除链表中第一个元素（最近最不常使用的元素），同时还要在哈希中移除，所以需要记录这个数据的key

② 使用带假节点的双向链表

为什么使用假节点？原因很简单，操作方便。对于一个单链表，添加元素时要判断头指针是否为空，删除元素时需要判断是不是头部元素，如果是头部元素，就需要将头指针向后移，但是使用假节点之后便不再需要进行这些操作。结构如下：

可以看出，对于带有假节点的链表，head后邻节点是有效的第一个节点（在不是rear的情况下），rear前邻节点是最后一个有效节点（在不是head的情况下）

③ 初始化LRU容器

//	头部指针
private ListNode head;
//	尾部指针
private ListNode rear;
//	哈希表
private HashMap<Integer, ListNode> hash = new HashMap<>();
//	缓存容量
private final int capacity;public LRUCache(int capacity) {//	缓存容量this.capacity = capacity;//  初始化双向链表//	头部假节点this.head = new ListNode();//	尾部假节点this.rear = new ListNode();//	首尾相连head.next = rear;rear.pre = head;
}

目前为止，双向链表还是一个空链表

④ 获取缓存元素

思路如下：

元素不存在，直接返回-1
元素存在
1. 将元素移到链表尾部
2. 返回元素

代码实现：

public int get(int key) {//  从哈希表中查找节点ListNode node = hash.get(key);//  节点不存在，返回-1if (node == null) {return -1;}//  节点存在，将节点移动到链表尾部moveToLast(node);//  返回缓存数据return node.val;
}

⑤ 放置缓存元素

思路如下：

元素不存在
1. 如果缓存已满，删除链表第一个元素
2. 添加新节点到链表尾部
元素存在
1. 将元素移动到链表尾部
2. 更节点数据

代码实现：

public void put(int key, int value) {//  判断key是否存在ListNode valueNode = hash.get(key);//  元素不存在if (valueNode == null) {//  判断缓存是否到达上限if (hash.size() == capacity) {//  删除最不经常使用的节点ListNode firstNode = head.next;removeNode(firstNode);}//  添加新节点到链表尾部addNodeToBack(new ListNode(key, value));} else {//  节点存在，将节点移到尾部，并修改节点值moveToLast(valueNode);valueNode.val = value;}
}

⑥ 操作节点函数的封装

将节点放置到尾部

private void moveToLast(ListNode node) {//  如果节点在链表中，那么更新他的前驱与后继的指针指向if (node.pre != null && node.next != null) {ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;}//  将节点插入到尾部ListNode rearPre = rear.pre;rearPre.next = node;node.pre = rearPre;node.next = rear;rear.pre = node;
}

添加节点到尾部并放入哈希表

private void addNodeToBack(ListNode newNode) {//	将节点移动到尾部moveToLast(newNode);//	将节点映射信息放入哈希表hash.put(newNode.key, newNode);
}

删除节点

private void removeNode(ListNode node) {//	移除哈希表中存储的信息hash.remove(node.key);//	移除链表中的节点ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;
}

代码实现

class LRUCache {private static class ListNode {public ListNode pre;public ListNode next;public int key;public int val;public ListNode() {}public ListNode(int key, int val) {this.key = key;this.val = val;}}private ListNode head;private ListNode rear;private HashMap<Integer, ListNode> hash = new HashMap<>();private final int capacity;public LRUCache(int capacity) {this.capacity = capacity;//  初始化双向链表this.head = new ListNode();this.rear = new ListNode();head.next = rear;rear.pre = head;}public int get(int key) {//  从哈希表中查找节点ListNode node = hash.get(key);//  节点不存在，返回-1if (node == null) {return -1;}//  节点存在，将节点移动到链表尾部moveToLast(node);//  返回缓存数据return node.val;}public void put(int key, int value) {//  判断key是否存在ListNode valueNode = hash.get(key);//  元素不存在if (valueNode == null) {//  判断缓存是否到达上限if (hash.size() == capacity) {//  删除最不经常使用的节点ListNode firstNode = head.next;removeNode(firstNode);}//  添加新节点到链表尾部addNodeToBack(new ListNode(key, value));} else {//  节点存在，将节点移到尾部，并修改节点值moveToLast(valueNode);valueNode.val = value;}}private void addNodeToBack(ListNode newNode) {moveToLast(newNode);hash.put(newNode.key, newNode);}private void moveToLast(ListNode node) {//  如果节点在链表中，那么更新他的前驱与后继的指针指向if (node.pre != null && node.next != null) {ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;}//  将节点插入到尾部ListNode rearPre = rear.pre;rearPre.next = node;node.pre = rearPre;node.next = rear;rear.pre = node;}private void removeNode(ListNode node) {hash.remove(node.key);ListNode pre = node.pre;ListNode next = node.next;pre.next = next;next.pre = pre;}
}

LRU缓存

什么是LRU缓存? LRU（Least Recently Used）是最近最少使用算法，是操作系统中用于分页置换的算法，如果要向内存中添加分页，并且内存分页已满的情况下，就选出最近一段时间最不常用的分页进行置换（…...

编程日记 2025/7/20 15:26:16

.net6 使用 FreeSpire.XLS 实现 excel 转 pdf - docker 部署

FreeSpire.XLS && Aspose.Cells包都可以实现。实现过程中发现如下问题： 本地测试通过， docker部署服务器后报错： The type initializer for Spire.Xls.Core.Spreadsheet.XlsPageSetupBase threw an exception. 由于缺少依赖&#xf…...

编程日记 2025/7/20 15:03:07

HttpServletRequest req和前端的关系，req.getParameter详细解释，req.getParameter和前端的关系

HttpServletRequest 对象在后端和前端之间起到了桥梁的作用，它包含了来自客户端的所有请求信息。通过 HttpServletRequest 对象，后端可以获取前端发送的请求参数、请求头、请求方法等信息，并根据这些信息进行相应的处理。以下是对 HttpServle…...

编程日记 2025/7/19 4:54:48

[Python3] Sanic 框架构建高并发的 Web 服务

在 Python3 中使用 Sanic 框架来构建高并发的 Web 服务时，Sanic 因其异步和基于事件驱动的架构能够很好地处理高并发请求。下面是如何使用 Sanic 的一些要点和示例代码。 1. 安装 Sanic 首先确保你安装了 Sanic，可以通过以下命令安装： pip…...

编程日记 2025/7/20 15:22:03

5.5 W5500 TCP服务端与客户端

文章目录 1、TCP介绍2、W5500简介2.1 关键函数socketlistensendgetSn_RX_RSRrecv自动心跳包检测getSn_SR 1、TCP介绍 TCP 服务端： 创建套接字[socket]：服务器首先创建一个套接字，这是网络通信的端点。绑定套接字[bind]：服务器将…...

编程日记 2025/7/20 15:15:34

【Flutter】搭建Flutter开发环境，安卓开发

Flutter是谷歌开源的一个跨平台开发的框架，方便好用，这里以Windows 上构建 Flutter Android 应用为例，记录下我搭建环境时碰到的一些问题以及解决。第一步：参考官网：开发 Android 应用 | Flutter 中文文档 - Flutter …...

编程日记 2025/7/16 17:41:40

【机器学习】——朴素贝叶斯模型

💻博主现有专栏： C51单片机（STC89C516），c语言，c，离散数学，算法设计与分析，数据结构，Python，Java基础，MySQL，linux&#xf…...

编程日记 2025/7/15 17:13:43

k8s rainbond centos7/win10 -20241124

参考 https://www.rainbond.com/ 国内一站式云原生平台对centos7环境支持不太行 [lighthouseVM-16-5-centos ~]$ curl -o install.sh https://get.rainbond.com && bash ./install.sh 2024-11-24 09:56:57 ERROR: Ops! Docker daemon is not running. Start docke…...

编程日记 2025/7/20 7:50:58

ctfshow单身杯2024wp

文章目录 ctfshow单身杯2024wp签到好玩的PHPezzz_sstiez_inject ctfshow单身杯2024wp 签到好玩的PHP 考点：序列化反序列化 <?phperror_reporting(0);highlight_file(__FILE__);class ctfshow {private $d ;private $s ;private $b ;private $ctf ;public …...

编程日记 2025/7/19 19:13:44

深入解密 K 均值聚类：从理论基础到 Python 实践

1. 引言在机器学习领域，聚类是一种无监督学习的技术，用于将数据集分组成若干个类别，使得同组数据之间具有更高的相似性。这种技术在各个领域都有广泛的应用，比如客户细分、图像压缩和市场分析等。聚类的目标是使得同类样本之间的…...

编程日记 2025/7/20 14:47:33

【代码pycharm】动手学深度学习v2-08 线性回归 + 基础优化算法

课程链接线性回归的从零开始实现 import random import torch from d2l import torch as d2l# 人造数据集 def synthetic_data(w,b,num_examples):Xtorch.normal(0,1,(num_examples,len(w)))ytorch.matmul(X,w)bytorch.normal(0,0.01,y.shape) # 加入噪声return X,y.reshape…...

编程日记 2025/7/20 14:57:31

Python绘制太极八卦

文章目录系列目录写在前面技术需求1. 图形绘制库的支持2. 图形绘制功能3. 参数化设计4. 绘制控制5. 数据处理6. 用户界面完整代码代码分析1. rset() 函数2. offset() 函数3. taiji() 函数4. bagua() 函数5. 绘制过程6. 技术亮点写在后面系列目录序号直达链接爱心系列1Pyth…...

编程日记 2025/7/20 14:40:00

sklearn学习

介绍：scaler：换算的意思 1. 归一化MinMaxScaler() 归一化的意思是将一堆数，如果比较离散，为了让数据更适合模型训练，将离散的数据压缩到0到1之间，以方便模型更高效优质的学习，而对数据的预处理…...

编程日记 2025/7/20 14:50:12

# [Unity] 【游戏开发】Unity开发基础2-Unity脚本编程基础详解

Unity脚本编程是创建互动式游戏体验的核心技能之一。本文将详细讲解Unity脚本编程的基础知识，包括变量和数据类型、程序逻辑、方法等方面，并通过实例展示如何使用这些基本知识完成简单功能的实现。 1. 新建Unity脚本的基本结构当在Unity中创建一个脚本时，Unity会生成如下基…...

编程日记 2025/7/20 14:46:21

【强化学习的数学原理】第02课-贝尔曼公式-笔记

学习资料：bilibili 西湖大学赵世钰老师的【强化学习的数学原理】课程。链接：强化学习的数学原理西湖大学赵世钰文章目录一、为什么return重要？如何计算return？二、state value的定义三、Bellman公式的详细推导四、公式向量形式…...

编程日记 2025/7/20 14:48:36

C语言-数学基础问题

一.奇数、偶数问题 1.从键盘上输入一个整数，判断并输出它是奇数还是偶数。 //从键盘上输入一个整数，判断并输出它是奇数还是偶数。 main() {int i;printf("输入一个整数:\n");scanf("%d",&i);if(i%20)printf("它是偶数\n…...

编程日记 2025/7/14 11:52:38

2024算法基础公选课练习四（综合2）

一、前言最后几个题确实有难度，这次有两题没整出来二、题目总览三、具体题目 3.1 问题 A: 水题系列1-B(班级排位) 思路最暴力的思路是写线段树，然后暴力枚举两个端点，总体时间复杂度为O(n^2*logn)最坏会到1e9的数量级，可能…...

编程日记 2025/7/20 1:19:20

小程序-使用 iconfont 图标库报错：Failed to load font

官方默认可以忽略此错误，在清除缓存后首次刷新会显示此错误，重新渲染错误消失解决方法： 在 iconfont 图标库选择项目设置选中 Base64 保存，重新点击链接 -> 复制代码到项目中操作步骤：...

编程日记 2025/7/3 2:22:30

鲸鱼机器人和乐高机器人的比较

鲸鱼机器人和乐高机器人各有其独特的优势和特点，家长在选择时可以根据孩子的年龄、兴趣、经济能力等因素进行综合考虑，选择最适合孩子的教育机器人产品。优势鲸鱼机器人 1）价格亲民：鲸鱼机器人的产品价格相对乐高更为亲民&…...

编程日记 2025/7/17 14:14:04

解决单元测试时找不到类名

场景： springboot单元测试mockito对mapper进行mock时： tk.mybatis.mapper.mapperexception: 无法获取实体类 XX.xx 对应的表名分析： 使用了一个方法：Example examplenew Example(User.class); 进入源码后发现Entityhelper没…...

编程日记 2025/7/16 1:30:38

簡單易懂：如何在Windows系統中修改IP地址？

無論是為了連接到一個新的網路，還是為了解決網路連接問題，修改IP地址都是一個常見的操作。本文將詳細介紹如何在Windows系統中修改IP地址，包括靜態IP地址的設置和動態IP地址的獲取。 IP地址是什麼？ IP地址是互聯網協議地址的簡稱…...

编程日记 2025/7/15 22:31:38

（详细文档！）java swing学生信息管理系统 +mysql

第一章：系统功能分析 1.1、系统简介与开发背景学生信息管理系统是在信息化时代，特别是在教育领域中产生的。随着学校规模的不断扩大和信息化技术的不断发展，传统的纸质档案管理方式已经无法满足学校对学生信息管理的需求，因此需…...

编程日记 2025/7/19 10:40:51

OSG开发笔记（三十三）：同时观察物体不同角度的多视图从相机技术

若该文为原创文章，未经允许不得转载本文章博客地址：https://blog.csdn.net/qq21497936/article/details/143932273 各位读者，知识无穷而人力有穷，要么改需求，要么找专业人士，要么自己研究长沙红胖子Qt…...

编程日记 2025/7/17 19:28:27

[极客大挑战 2019]BabySQL--详细解析

信息搜集进入界面： 输入用户名为admin，密码随便输一个： 发现是GET传参，有username和password两个传参点。我们测试一下password点位能不能注入： 单引号闭合报错，根据报错信息，我们可以判断…...

编程日记 2025/7/18 22:47:46

Java的字符串操作（二）（代码示例）

1. 字符串的定义 // 直接赋值方式定义字符串 String str1 "Hello World";// 使用new关键字定义字符串 String str2 new String("Hello World");// 可以通过打印对象的哈希码来查看是否是同一个对象（在一定程度上反映引用情况） Sy…...

编程日记 2025/7/18 16:49:33

2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest(ABCGJLN)

文章目录 N. Fixing the Expression思路code J. Waiting for...思路code C. DIY思路code L. Bridge Renovation思路code A. Bonus Project思路code G. Guess One Character思路code B. Make It Equal思路code N. Fixing the Expression 思路签到题，只改变中间的字…...

编程日记 2025/7/17 0:00:10

SpringBoot（9）-Dubbo+Zookeeper

目录一、了解分布式系统二、RPC 三、Dubbo 四、SpringBootDubboZookeeper 4.1 框架搭建 4.2 实现RPC 一、了解分布式系统分布式系统：由一组通过网络进行通信，为了完成共同的任务而协调工作的计算机节点组成的系统二、RPC RPC：远程…...

编程日记 2025/7/19 4:50:28

现代密码学

概论计算机安全的最核心三个关键目标（指标）/为：保密性 Confidentiality、完整性 Integrity、可用性 Availability ，三者称为 CIA三元组数据保密性：确保隐私或是秘密信息不向非授权者泄漏，也不被非授权者使…...

编程日记 2025/7/20 10:09:52

websocket是什么？

一、定义 Websocket是一种在单个TCP连接上进行全双工通信的协议，它允许服务器主动向客户端推送数据，而不需要客户端不断的轮询服务器来获取数据与http协议不同，http是一种无状态的，请求，响应模式的协议(单向通信)&a…...

编程日记 2025/7/18 20:32:47

idea怎么打开两个窗口，运行两个项目

今天在开发项目的时候，前端希望运行一下以前的项目，于是就需要开两个 idea 窗口，运行两个项目这里记录一下如何设置：首先依次点击： File -> Settings -> Appearance & Behavior ->System Settings 看到如…...

编程日记 2025/7/18 14:36:25

aws服务--机密数据存储KMS（1）介绍和使用

在AWS（Amazon Web Services）中存储机密数据时，安全性和合规性是最重要的考虑因素。AWS 提供了多个服务和工具，帮助用户确保数据的安全性、机密性以及合规性。AWS Secrets Manager、KMS（Key Management Service）是推荐的存储机密数据的AWS服务和最佳实践。这里先看KMS。 …...

编程日记 2025/7/18 4:46:30

怎么编译OpenWrt镜像？-基于Widora开发板

1.准备相应的环境，我使用的环境是VMware16ubuntu20.04，如图1所示安装编译所需的依赖包； sudo apt-get install build-essential asciidoc binutils bzip2 gawk gettext git libncurses5-dev libz-dev patch python3 python2.7 unzip zlib1g-…...

编程日记 2025/7/18 12:49:43

Android opencv使用Core.hconcat 进行图像拼接

Android 集成OpenCV-CSDN博客 import org.opencv.android.Utils; import org.opencv.core.Core; import org.opencv.core.CvType; import org.opencv.core.Mat; import org.opencv.imgcodecs.Imgcodecs; import android.graphics.Bitmap; import android.graphics.BitmapFactor…...

编程日记 2025/7/16 1:43:12