35、链表-LRU缓存

思路:
首先要了解LRU缓存的原理,首先定下容量,每次get请求和put请求都会把当前元素放最前/后面,如果超过容量那么头部/尾部元素就被移除,所以最近最少使用的元素会被优先移除,保证热点数据持续存在。 不管放在头部还是尾部都可以。看你怎么定义
那么如何实现呢?有两种方式第一种直接继承LinkedHashMap 这个是已经帮我们实现的,代码如下:
class LRUCache extends LinkedHashMap<Integer, Integer>{private int capacity;public LRUCache(int capacity) {super(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; }
}
第二种就是手动去实现了,代码如下:
class LRUCache extends AbstractLRUCache<Integer, Integer> {public LRUCache(int capacity) {super(capacity);}public int get(int key) {Integer ans = super.get(key);return ans == null ? -1 : ans;}public void put(int key, int value) {super.set(key, value);}
}abstract class AbstractLRUCache<K, V> {private Map<K, Node<K, V>> keyNodeMap;private NodeDoubleLinkedList<K, V> nodeList;private final int capacity;public AbstractLRUCache(int cap) {if (cap < 1) {throw new RuntimeException("should be more than 0");}keyNodeMap = new HashMap<>();nodeList = new NodeDoubleLinkedList<>();capacity = cap;}public V get(K key) {if (keyNodeMap.containsKey(key)) {Node<K, V> res = keyNodeMap.get(key);nodeList.moveNodeToTail(res);return res.value;}return null;}public void set(K key, V value) {if (keyNodeMap.containsKey(key)) {Node<K, V> node = keyNodeMap.get(key);node.value = value;nodeList.moveNodeToTail(node);} else {Node<K, V> newNode = new Node<>(key, value);keyNodeMap.put(key, newNode);nodeList.addNode(newNode);if (keyNodeMap.size() == capacity + 1) {removeMostUnusedCache();}}}private void removeMostUnusedCache() {Node<K, V> node = nodeList.removeHead();keyNodeMap.remove(node.key);}class Node<K, V> {public K key;public V value;public Node<K, V> last;public Node<K, V> next;public Node(K key, V value) {this.key = key;this.value = value;}}class NodeDoubleLinkedList<K, V> {private Node<K, V> head;private Node<K, V> tail;public NodeDoubleLinkedList() {head = null;tail = null;}public void addNode(Node<K, V> newNode) {if (newNode == null) {return;}if (head == null) {head = newNode;tail = newNode;} else {tail.next = newNode;newNode.last = tail;tail = newNode;}}public void moveNodeToTail(Node<K, V> node) {if (this.tail == node) {return;}if (this.head == node) {this.head = node.next;this.head.last = null;} else {node.last.next = node.next;node.next.last = node.last;}node.last = this.tail;node.next = null;this.tail.next = node;this.tail = node;}public Node<K, V> removeHead() {if (this.head == null) {return null;}Node<K, V> res = this.head;if (this.head == this.tail) {this.head = null;this.tail = null;} else {this.head = res.next;res.next = null;this.head.last = null;}return res;}}
}
以下是代码实现的功能要点:
-
AbstractLRUCache是一个抽象类,它包含了 LRU 缓存的核心逻辑,如添加节点、移动节点到链表尾部、移除最少使用的节点等。 -
LRUCache是AbstractLRUCache的具体实现,它提供了get和put方法来与缓存进行交互。这些方法调用了抽象类中的方法来实现 LRU 逻辑。 -
Node类代表缓存中的一个条目,包含键、值以及指向前一个和后一个节点的指针。 -
NodeDoubleLinkedList是一个双向链表,用于按照访问顺序维护缓存中的节点。最近访问的节点被移动到链表的尾部,而最少使用的节点位于链表的头部。 -
当缓存达到其容量限制时,最少使用的节点(链表头部的节点)将被移除,以确保缓存大小不超过设定的容量。
相关文章:
35、链表-LRU缓存
思路: 首先要了解LRU缓存的原理,首先定下容量,每次get请求和put请求都会把当前元素放最前/后面,如果超过容量那么头部/尾部元素就被移除,所以最近最少使用的元素会被优先移除,保证热点数据持续存在。 不管放…...
数据结构速成--栈
由于是速成专题,因此内容不会十分全面,只会涵盖考试重点,各学校课程要求不同 ,大家可以按照考纲复习,不全面的内容,可以看一下小编主页数据结构初阶的内容,找到对应专题详细学习一下。 目录 一…...
算法练习第15天|226.翻转二叉树
226.翻转二叉树 力扣链接https://leetcode.cn/problems/invert-binary-tree/description/ 题目描述: 给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。 示例 1: 输入:root [4,2,7,1,3,6,9] 输出&am…...
C#面向对象——封装、封装案例示例
C#面向对象——封装 什么是封装? (1)封装是将数据和操作数据的方法(行为)封装在一起。 (2)程序中封装的体现:属性,方法,类,接口,命名空间&#…...
【InternLM 实战营第二期-笔记3】茴香豆:搭建你的 RAG 智能助理
书生浦语是上海人工智能实验室和商汤科技联合研发的一款大模型,很高兴能参与本次第二期训练营,我也将会通过笔记博客的方式记录学习的过程与遇到的问题,并为代码添加注释,希望可以帮助到你们。 记得点赞哟(๑ゝω╹๑) 茴香豆:搭建…...
Advanced RAG 03:运用 RAGAs 与 LlamaIndex 评估 RAG 应用
编者按:目前,检索增强生成(Retrieval Augmented Generation,RAG)技术已经广泛使用于各种大模型应用场景。然而,如何准确评估 RAG 系统的性能和效果,一直是业界和学界共同关注的重点问题。若无法…...
leetcode
找到字符串中所有字母异位词 给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串(包括相同的字符串) 示例 1: 输入: s "…...
Unity DOTS《群体战斗弹幕游戏》核心技术分析之3D角色动画
最近DOTS发布了正式的版本, 我们来分享现在流行基于群体战斗的弹幕类游戏,实现的核心原理。今天给大家介绍大规模战斗群体3D角色的动画如何来实现。 DOTS 对角色动画支持的局限性 截止到Unity DOTS发布的版本1.0.16,目前还是无法很好的支持3D角色动画。在DOTS 的ba…...
react异步组件如何定义使用 标准使用方法
目录 默认导出和命名导出的格式 默认导出的组件 使用方式 命名导出的组件 使用方式 默认导出和命名导出的格式 默认导出: // person.js const person {name: Alice,age: 30 };export default person;命名导出: // math.js export const add (a, b) > a b; exp…...
React + Ts + Vite + Antd 项目搭建
1、创建项目 npm create vite 项目名称 选择 react 选择 typescript 关闭严格模式 建议关闭严格模式,因为不能自动检测副作用,有意双重调用。将严格模式注释即可。 2、配置sass npm install sass 更换所有后缀css为sass vite.config.ts中注册全局样式 /…...
js爬虫puppeteer库 解决网页动态渲染无法爬取
我们爬取这个网址上面的股票实时部分宇通客车(600066)_股票价格_行情_走势图—东方财富网 我们用正常的方法爬取会发现爬取不下来,是因为这个网页这里是实时渲染的,我们直接通过网址接口访问这里还没有渲染出来 于是我们可以通过下面的代码来进行爬取: …...
代码随想录:二叉树5
目录 102.二叉树的层序遍历 题目 代码(队列实现) 107.二叉树的层序遍历II 题目 代码 199.二叉树的右视图 题目 代码 637.二叉树的层平均值 题目 代码 102.二叉树的层序遍历 题目 给你二叉树的根节点 root ,返回其节点值的 层序遍…...
Tomcat 获取客户端真实IP X-Forwarded-For
Tomcat 获取客户端真实IP X-Forwarded-For 代码实现: 在Host标签下面添加代码: <Valve className"org.apache.catalina.valves.RemoteIpValve" remoteIpHeader"x-forwarded-for" remoteIpProxiesHeader"x-forwarded-by&q…...
记录PS学习查漏补缺
PS学习 PS学习理论快捷键抠图PS专属多软件通用快捷键 PS学习 理论 JPEG (不带透明通道) PNG (带透明通道) 快捷键 抠图 抠图方式 魔棒工具 反选选中区域 CtrlShiftI(反选) 钢笔抠图注意事项 按着Ctrl单击节点 会出现当前节…...
Kafka 架构深入探索
目录 一、Kafka 工作流程及文件存储机制 二、数据可靠性保证 三 、数据一致性问题 3.1follower 故障 3.2leader 故障 四、ack 应答机制 五、部署FilebeatKafkaELK 5.1环境准备 5.2部署ELK 5.2.1部署 Elasticsearch 软件 5.2.1.1修改elasticsearch主配置文件 5.2…...
k-means聚类算法的MATLAB实现及可视化
K-means算法是一种无监督学习算法,主要用于数据聚类。其工作原理基于迭代优化,将数据点划分为K个集群,使得每个数据点都属于最近的集群,并且每个集群的中心(质心)是所有属于该集群的数据点的平均值。以下是…...
Excel文件转Asc文件
单个转换 import os import pandas as pdfilename (10)result01-1.xlsx df pd.read_excel(filename) # 读取Excel文件# 将数据保存为ASC格式 asc_filename os.path.splitext(filename)[0] .asc # 获取文件名并替换扩展名 with open(asc_filename, w) as file:# 写入文件…...
【题目】【信息安全管理与评估】2022年国赛高职组“信息安全管理与评估”赛项样题7
【题目】【信息安全管理与评估】2022年国赛高职组“信息安全管理与评估”赛项样题7 信息安全管理与评估 网络系统管理 网络搭建与应用 云计算 软件测试 移动应用开发 任务书,赛题,解析等资料,知识点培训服务 添加博主wx:liuliu548…...
Webrtc 信令服务器实现
webrtc建联流程图 由上图可知,所谓的信令服务器其实就是将peer的offer/candidate/answer传给对端而已。这样的话实现方式就有很多种了,目前普遍的方式HTTP/HTTPS,WS/WSS。像webrtc-demo-peerconnection就是实现HTTP这种方式。本文使用WS&…...
【Blockchain】连接智能合约与现实世界的桥梁Chainlink
去中心化预言机试图实现依赖因果关系而不是个人关系的去信任和确定性结果。它以与区块链网络相同的方式实现这些结果,即在许多网络参与者之间分配信任。通过利用许多不同的数据源并实施不受单个实体控制的预言机系统,去中心化的预言机网络有可能为智能合…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...
