图解LRU缓存
图解LRU缓存
OJ链接
介绍
LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
-
双向链表按照被使用的顺序存储了这些键值对,靠近尾部的键值对是最近使用的,而靠近头部的键值对是最久未使用的。
-
哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。
这样一来,我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置,随后将其移动到双向链表的尾部,即可在O(1)的时间内完成 get 或者 put 操作。
先介绍两个常用函数:removeToTail(node)和add(node),removeToTail(node)是在双向链表中,将使用过的node移到链表尾部,add(node)是往双向链表增加一个节点。
removeToTail(node)
add(node)
下面就是主要函数的介绍
get()
对于 get 操作,首先判断 key 是否存在:
-
如果 key 不存在,则返回 −1;
-
如果 key 存在,则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置,并将其移动到双向链表的尾部,最后返回该节点的值。
put()
对于 put 操作,首先判断 key 是否存在:
-
如果 key 不存在,使用 key 和 value 创建一个新的节点,将 key 和该节点添加进哈希表中,并在双向链表的尾部添加该节点。然后判断哈希表的节点数是否超出容量,如果超出容量,则删除哈希表中对应的项,并删除双向链表的头部节点;
-
如果 key 存在,则与 get 操作类似,先通过哈希表定位,再将该节点移到双向链表的尾部,并将对应的节点的值更新为 value。
复杂度分析
上述各项操作中,访问哈希表的时间复杂度为 O(1),在双向链表的尾部添加节点、在双向链表的头部删除节点的复杂度也为 O(1)。
代码
import java.util.HashMap;public class $146 {class Node {int key;int value;Node prev;Node next;public Node(int key, int value) {this.key = key;this.value = value;}}HashMap<Integer, Node> hashMap = new HashMap<>();Node head = null;Node tail = null;int capacity;public $146(int capacity) {this.capacity = capacity;}//双向链表,将节点移动到tail后面,表示该节点是最近使用的public void removeToTail(Node node) {if (node == tail) {} else if (node == head) {tail.next = node;node.prev = tail;tail = tail.next;head = head.next;} else {node.prev.next = node.next;node.next.prev = node.prev;tail.next = node;node.prev = tail;tail = tail.next;}}//双向链表,增加某节点public void add(Node node) {if (tail == null) {head = node;tail = node;} else {tail.next = node;node.prev = tail;tail = tail.next;}}public int get(int key) {//1.哈希表不存在key,返回-1if (!hashMap.containsKey(key)) {return -1;} else { //2.哈希表存在key,从哈希表中获得value,将key移到链表尾部int res = hashMap.get(key).value;removeToTail(hashMap.get(key));return res;}}public void put(int key, int value) {//1.哈希表不存在keyif (!hashMap.containsKey(key)) {//1.1创建新节点Node node = new Node(key, value);//1.2插入//插入到哈希表hashMap.put(key, node);//插入到链表add(node);//1.3判断哈希表容量if (hashMap.size() > capacity) {//1.3.1删除//哈希表删除链表头元素hashMap.remove(head.key);//链表删除头元素// remove(head);head = head.next;}} else { //2.哈希表存在key//2.1更新//更新链表,将key移到链表尾部removeToTail(hashMap.get(key));//更新哈希表,key对应的valuehashMap.get(key).value = value;}}public static void main(String[] args) {$146 a = new $146(4);a.put(8,80);a.put(9,90);a.put(7,70);a.put(6,60);a.get(8);a.get(7);a.put(5,50);}// //双向链表,删除某节点
// public void remove(Node node) {
// // head = head.next;
// if (node == tail) {
// tail = tail.prev;
// } else if (node == head) { //均是头结点
// head = head.next;
// } else {
// node.prev.next = node.next;
// node.next.prev = node.prev;
// }
// }
}
相关文章:
图解LRU缓存
图解LRU缓存 OJ链接 介绍 LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。 双向链表按照被使用的顺序存储了这些键值对,靠近尾部的键值对是最近使用的,而靠近头部的键值对是最久未…...
FFmpeg常见命令行
1、ffmpeg命令行 视频生成图片 ffmpeg -i test.mp4 -r 25 -f image2 data/image%3d.jpg这个命令行使用FFmpeg工具将视频文件(test.mp4)转换为一系列图像文件。 让我们逐个解释每个参数的含义: -i test.mp4: 指定输入文件为test.mp4。-i是F…...
智能优化算法应用:基于斑马算法3D无线传感器网络(WSN)覆盖优化 - 附代码
智能优化算法应用:基于斑马算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于斑马算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.斑马算法4.实验参数设定5.算法结果6.参考文献7.MA…...
《C++避坑神器·二十五》简单搞懂json文件的读写之遍历json文件读写
json.hpp库放在文章末尾 1、遍历json文件读写 (1)插入新键值对到json之情形1 原来json文件如下所示: {"Connection": {"IpAddress": "192.168.20.1","Rock": 0,"Solt": 1}, "Data…...
使用 fixture 机制重构 appium_helloworld
一、前置说明 在 pytest 基础讲解 章节,介绍了 pytest 的特性和基本用法,现在我们可以使用 pytest 的一些机制,来重构 appium_helloworld 。 appium_helloworld 链接: 编写第一个APP自动化脚本 appium_helloworld ,将脚本跑起来 代码目录结构: pytest.ini 设置: [pyt…...
基于python的excel检查和读写软件
软件版本:python3.6 窗口和界面gui代码: class mygui:def _init_(self):passdef run(self):root Tkinter.Tk()root.title(ExcelRun)max_w, max_h root.maxsize()root.geometry(f500x500{int((max_w - 500) / 2)}{int((max_h - 300) / 2)}) # 居中显示…...
Podman配置mongodb
文章目录 查询镜像拉取镜像查看镜像运行容器创建root用户 查询镜像 podman search mongo拉取镜像 podman pull docker.io/library/mongo查看镜像 podman images运行容器 podman run -d -p 27017:27017 --namemongodb-test docker.io/library/mongo创建root用户 podman exe…...
java实现矩阵谱峰搜索算法
矩阵谱峰搜索算法,也称为矩阵谱峰查找算法,是一种用于搜索二维矩阵中谱峰的方法。谱峰是指在矩阵中的一个元素,它比其上下左右四个相邻元素都大或相等。 该算法的基本思想是从矩阵的中间列开始,找到该列中的最大元素,…...
Jenkins的特殊操作定时自动执行任务以及测试报告调优
java -Dhudson.model.DirectoryBrowserSupport.CSP -jar Jenkins.war 测试报告 不美丽 执行上面的代码 重启jenkins 就好了...
【Grafana】Grafana匿名访问以及与LDAP连接
上一篇文章利用Docker快速部署了Grafana用来展示Zabbix得监控数据,但还需要给用户去创建账号允许他们登录后才能看展示得数据,那有什么办法让非管理员更方便得去访问Grafana呢?下面介绍两个比较方便实现的: 在开始设置前ÿ…...
elasticsearch-py 8.x的一些优势
早在 2022 年 2 月,当 Elasticsearch 8.0 发布时,Python 客户端也发布了 8.0 版本。它是对 7.x 客户端的部分重写,并带有许多不错的功能(如下所述),但也带有弃用警告和重大更改。今天,客户端的 7.17 版本仍然相对流行,每月下载量超过 100 万次,占 8.x 下载量的 ~50…...
RK3588平台开发系列讲解(AI 篇)RKNN 数据结构详解
文章目录 一、rknn_sdk_version二、rknn_input_output_num三、rknn_tensor_attr四、rknn_perf_detail五、rknn_perf_run六、rknn_mem_size七、rknn_tensor_mem八、rknn_input九、rknn_output沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇章主要讲解 RKNN 相关的数…...
2023版本QT学习记录 -6- UDP通信之UDP接收端
———————UDP接收端——————— 🎄动图演示 🎄发送端通信步骤思维导图 🎄添加组件 QT core gui network🎄添加头文件 #include "qudpsocket.h"🎄创建接收对象 QUdpSocket *recvsocket;&…...
C预处理 | pragma详解
欢迎关注博主 Mindtechnist 或加入【Linux C/C/Python社区】一起学习和分享Linux、C、C、Python、Matlab,机器人运动控制、多机器人协作,智能优化算法,滤波估计、多传感器信息融合,机器学习,人工智能等相关领域的知识和…...
轻松搭建知识付费小程序:让知识传播更便捷
明理信息科技saas知识付费平台 在当今数字化时代,知识付费已经成为一种趋势,越来越多的人愿意为有价值的知识付费。然而,公共知识付费平台虽然内容丰富,但难以满足个人或企业个性化的需求和品牌打造。同时,开发和维护…...
沉浸式go-cache源码阅读!
大家好,我是豆小匠。 这期来阅读go-cache的源码,了解本地缓存的实现方式,同时掌握一些阅读源码的技巧~ 1. 源码获取 git clone https://github.com/patrickmn/go-cache.git用Goland打开可以看到真正实现功能的也就两个go文件,ca…...
伪协议和反序列化 [ZJCTF 2019]NiZhuanSiWei
打开题目 代码审计 第一层绕过 if(isset($text)&&(file_get_contents($text,r)"welcome to the zjctf")){ echo "<br><h1>".file_get_contents($text,r)."</h1></br>"; 要求我们get传参的text内容必须为w…...
性能优化之资源优化
性能优化之资源优化 资源优化性能关键检测流程。浅析一下基于Unity3D 美术规则约束一、模型层面二、贴图层面三、动画层面四、声音层面:(音频通用设置)五、UI层面: 题外点:诚然在优化中,美术占比是很重要的…...
ChatGPT免费 | 8个免费使用GPT-4的方法
这篇文章为寻找免费使用GPT-4技术的读者提供了一份实用的指南。 每个推荐的平台都包括了简要的描述和链接,方便读者直接访问。 以下是根据你提供的内容,稍作整理的文章结构: 1. HuggingFace 描述: 提供GPT-4等多种语言模型的平台。 如何使用:…...
解决Qt“报无法定位程序输入点xxx于动态连接库“问题
今天,在使用QtVS2019编译工程时,弹出"无法定位程序输入点xxx于动态链接库"问题,如图(1)所示: 图(1) 报"无法定位程序输入点xxx于动态链接库"问题 出现这种问题的原因有很多: (1) 工程Release/Deb…...
wpf-MVVM绑定时可能出现的内存泄漏问题
文章速览 引言错误示范示例1示例2 坚持记录实属不易,希望友善多金的码友能够随手点一个赞。 共同创建氛围更加良好的开发者社区! 谢谢~ 引言 正确结构: Model <——> ViewModel <——> View 但很多时候,很容易出现…...
【飞凌 OK113i-C 全志T113-i开发板】一些有用的常用的命令测试
一些有用的常用的命令测试 一、系统信息查询 可以查询板子的内核信息、CPU处理器信息、环境变量等 二、CPU频率 从上面的系统信息查询到,这是一颗具有两个ARMv7结构A7内核的处理器,主频最高1.2GHz 可以通过命令查看当前支持的频率以及目前所使用主频 …...
基于iOS平台的车牌识别表情识别项目
基于iOS平台的车牌识别&&表情识别项目 简介 该项目客户端搭载于iOS平台,服务端搭载于阿里云服务器,主要功能是通过拍照或选取相册图片来进行车牌的识别以及人脸表情识别。本文便是对项目整体流程设计思路和具体实现做一个详细介绍。 整体实…...
Matlab仿真2ASK/OOK、2FSK、2PSK、QPSK、4QAM在加性高斯白噪声信道中的误码率与归一化信噪比的关系
本文为学习所用,严禁转载。 本文参考链接 https://zhuanlan.zhihu.com/p/667382398 QPSK代码及高斯白噪声如何产生 https://ww2.mathworks.cn/help/signal/ref/butter.html 滤波器 https://www.python100.com/html/4LEF79KQK398.html 低通滤波器 本实验使用matlab仿…...
九:爬虫-MongoDB基础
MongoDB介绍 MongoDB是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,因此可以存储比较复杂的数据类型。Mongo最大的特点是它支持的查询语言非常强大,其…...
机器学习之实验过程01
import pandas as pd import numpy as np import matplotlib.pyplot as plt data_path /home/py/Work/labs/data/SD.csv # 请确保您的数据文件路径是正确的 df pd.read_csv(data_path) df.head() # 创建散点图 # 创建散点图 plt.figure(figsize(10, 6)) plt.scatter…...
【【迭代16次的CORDIC算法-verilog实现】】
迭代16次的CORDIC算法-verilog实现 -32位迭代16次verilog代码实现 CORDIC.v module cordic32#(parameter DATA_WIDTH 8d32 , // we set data widthparameter PIPELINE 5d16 // Optimize waveform)(input …...
IntelliJ IDEA 2023.3 安装教程
引言 IntelliJ IDEA,通常简称为 IDEA,是由 JetBrains 开发的一款强大的集成开发环境,专为提升开发者的生产力而设计。它支持多种编程语言,包括 Java、Kotlin、Scala 和其他 JVM 语言,同时也为前端开发和移动应用开发提…...
Go 错误处理
Go 错误处理 Go 语言通过内置的错误接口提供了非常简单的错误处理机制。 error类型是一个接口类型,这是它的定义: type error interface {Error() string }我们可以在编码中通过实现 error 接口类型来生成错误信息。 函数通常在最后的返回值中返回错误…...
HarmonyOS构建第一个ArkTS应用(Stage模型)
构建第一个ArkTS应用(Stage模型) 创建ArkTS工程 若首次打开DevEco Studio,请点击Create Project创建工程。如果已经打开了一个工程,请在菜单栏选择File > New > Create Project来创建一个新工程。 选择Application应用开发…...
故障排查利器-错误日志详解
目录 什么是错误日志 错误日志的作用 错误日志的内容 错误日志的格式 错误日志的生成方式 错误日志的解析和处理 错误日志的最佳实践 小结 错误日志是软件开发和运维中非常重要的一部分,记录了应用程序运行过程中发生的错误和异常信息,如错误类型…...
微信小程序(uniapp)api讲解
Uniapp是一个基于Vue.js的跨平台开发框架,可以同时开发微信小程序、H5、App等多个平台的应用。下面是Uniapp常用的API讲解: Vue.js的API Uniapp采用了Vue.js框架,因此可以直接使用Vue.js的API。例如:v-show、v-if、v-for、comput…...
overtureDNS使用介绍
Overture是一个定制的DNS中继服务器。 在此下在二进制版本 https://github.com/shawn1m/overture/releases默认配置文件./config.yml bindAddress: :53 debugHTTPAddress: 127.0.0.1:5555 dohEnabled: false primaryDNS:- name: DNSPodaddress: 119.29.29.29:53protocol: udp…...
平衡二叉树的构建(递归
目录 1.概念:2.特点:3.构建方法:4.代码:小结: 1.概念: 平衡二叉树(Balanced Binary Tree),也称为AVL树,是一种二叉树,它满足每个节点的左子树和右…...
flutter开发实战-设置bottomNavigationBar中间按钮悬浮效果
flutter开发实战-设置bottomNavigationBar中间按钮悬浮的效果 在使用tabbar时候,可以使用bottomNavigationBar来设置中间凸起的按钮,如下 一、效果图 中间按钮凸起的效果图如下 二、实现代码 我们使用BottomAppBar 一个容器,通常与[Sscaf…...
不同参数规模大语言模型在不同微调方法下所需要的显存总结
原文来自DataLearnerAI官方网站: 不同参数规模大语言模型在不同微调方法下所需要的显存总结 | 数据学习者官方网站(Datalearner)https://www.datalearner.com/blog/1051703254378255 大模型的微调是当前很多人都在做的事情。微调可以让大语言模型适应特定领域的任…...
Crow:Middlewares 庖丁解牛6 middleware_call_helper
Crow:http请求到Rule绑定的handler_的调用链-CSDN博客 介绍了handler_的调用顺序,其中的一个调用过程是Connection::->handle void handle() {...ctx_ = detail::context<Middlewares...>();req_.middleware_context = static_cast<void*>(&ctx_);req_.m…...
MyBatis:Generator
MyBatis Generator附批量操作分页查询存储过程 Generator 介绍网址:Introduction to MyBatis Generator Generator ,一个用于 MyBatis 的代码生成工具,可以根据数据库表结构自动生成对应的实体类、DAO 接口和 SQL 映射文件,提高…...
rabbitmq的事务实现、消费者的事务实现
RabbitMQ提供了事务机制,可以确保消息在发送和确认过程中的一致性。使用事务机制可以将一系列的消息操作(发送、确认、回滚)作为一个原子操作,要么全部执行成功,要么全部回滚。 下面是使用RabbitMQ事务的一般步骤&…...
龙芯杯个人赛串口——做一个 UART串口——RS-232
文章目录 Async transmitterAsync receiver1. RS-232 串行接口的工作原理DB-9 connectorAsynchronous communicationHow fast can we send data? 2.波特率时钟生成器Parameterized FPGA baud generator 3.RS-232 transmitter数据序列化完整代码: 4.RS-232 receiver…...
验证码服务使用指南
验证码服务使用指南 1 部署验证码服务 1.1 基础环境 Java 1.8 Maven3.3.9 1.2 安装Redis 参考“Redis安装指南” 1.3 部署验证码服务 1.3.1 下载源码 使用git从远程下载验证码服务代码(开源)。 1.3.2 使用idea打开项目 使用idea打开上一步下载的sailing目录…...
js中Math.min(...arr)和Math.max(...arr)的注意点
当arr变量为空数组时,这两个函数和不传参数时的结果是一样的 Math.max() // -Infinity Math.max(...[]) // -InfinityMath.min() // Infinity Math.min(...[]) // Infinity...
【zookeeper特点和集群架构】
文章目录 1. Zookeeper介绍2、ZooKeeper数据结构3、Zookeeper集群架构 1. Zookeeper介绍 ZooKeeper 是一个开源的分布式协调框架,是Apache Hadoop 的一个子项目,主要用来解决分 布式集群中应用系统的一致性问题。Zookeeper 的设计目标是将那些复杂且容易…...
MySQL集群架构搭建以及多数据源管理实战
MySQL集群架构搭建以及多数据源管理实战 数据库的分库分表操作,是互联网大型应用所需要面对的最核心的问题。因为数据往往是一个应用最核心的价值所在。但是,在最开始的时候,需要强调下,在实际应用中,对于数据库&a…...
C# WPF上位机开发(从demo编写到项目开发)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 C# WPF编程,特别是控件部分,其实学起来特别快。只是后面多了多线程、锁、数据库、网络这部分稍微复杂一点,不过…...
微信小程序引入 vant组件(详细步骤)
vant官方地址 https://vant-contrib.gitee.io/vant-weapp/#/quickstart 步骤一、 通过 npm 安装 # 通过 npm 安装 npm i vant/weapp -S --production# 通过 yarn 安装 yarn add vant/weapp --production# 安装 0.x 版本 npm i vant-weapp -S --production步骤二 修改 app.js…...
Django之按钮(actions)
开篇就是道歉,哈哈哈哈,托更了好久好久,最近太忙了没啥时间更新,各位看官有催更的阔以给我私信哇,希望各位看官给个三连!!!😍😍😍😍 …...
从YOLOv1到YOLOv8的YOLO系列最新综述【2023年4月】
作者:Juan R. Terven 、Diana M. Cordova-Esparaza 摘要:YOLO已经成为机器人、无人驾驶汽车和视频监控应用的核心实时物体检测系统。我们对YOLO的演变进行了全面的分析,研究了从最初的YOLO到YOLOv8每次迭代的创新和贡献。我们首先描述了标准…...
浙江大唐乌沙山电厂选择ZStack Cloud打造新一代云基础设施
浙江大唐乌沙山电厂选择云轴科技ZStack Cloud云平台为其提供高性能、高可用的云主机、云存储和云网络,构建了简单、稳定、安全、高效的云基础设施;通过ZStackCloud为其提供可视化服务编排、多租户自服务等模块,帮助电厂提高IT资源利用率&…...
电脑开机快捷启动,启动菜单没有u盘怎么办
电脑开机快捷启动键找不到u盘怎么办 对于快捷启动键找不到u盘的问题,小编很了解其中的门道,因为开机找不到u盘是我们使用电脑时候的常见问题。那么我们到底要如何解决开机找不到u盘的问题呢?其实方法还是蛮简单的,下面小编就来教大家电脑开…...