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

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;}}
}

以下是代码实现的功能要点:

  1. AbstractLRUCache 是一个抽象类,它包含了 LRU 缓存的核心逻辑,如添加节点、移动节点到链表尾部、移除最少使用的节点等。

  2. LRUCache 是 AbstractLRUCache 的具体实现,它提供了 get 和 put 方法来与缓存进行交互。这些方法调用了抽象类中的方法来实现 LRU 逻辑。

  3. Node 类代表缓存中的一个条目,包含键、值以及指向前一个和后一个节点的指针。

  4. NodeDoubleLinkedList 是一个双向链表,用于按照访问顺序维护缓存中的节点。最近访问的节点被移动到链表的尾部,而最少使用的节点位于链表的头部。

  5. 当缓存达到其容量限制时,最少使用的节点(链表头部的节点)将被移除,以确保缓存大小不超过设定的容量。

相关文章:

35、链表-LRU缓存

思路&#xff1a; 首先要了解LRU缓存的原理&#xff0c;首先定下容量&#xff0c;每次get请求和put请求都会把当前元素放最前/后面&#xff0c;如果超过容量那么头部/尾部元素就被移除&#xff0c;所以最近最少使用的元素会被优先移除&#xff0c;保证热点数据持续存在。 不管放…...

数据结构速成--栈

由于是速成专题&#xff0c;因此内容不会十分全面&#xff0c;只会涵盖考试重点&#xff0c;各学校课程要求不同 &#xff0c;大家可以按照考纲复习&#xff0c;不全面的内容&#xff0c;可以看一下小编主页数据结构初阶的内容&#xff0c;找到对应专题详细学习一下。 目录 一…...

算法练习第15天|226.翻转二叉树

226.翻转二叉树 力扣链接https://leetcode.cn/problems/invert-binary-tree/description/ 题目描述&#xff1a; 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&am…...

C#面向对象——封装、封装案例示例

C#面向对象——封装 什么是封装? &#xff08;1&#xff09;封装是将数据和操作数据的方法&#xff08;行为&#xff09;封装在一起。 &#xff08;2&#xff09;程序中封装的体现&#xff1a;属性&#xff0c;方法&#xff0c;类&#xff0c;接口&#xff0c;命名空间&#…...

【InternLM 实战营第二期-笔记3】茴香豆:搭建你的 RAG 智能助理

书生浦语是上海人工智能实验室和商汤科技联合研发的一款大模型,很高兴能参与本次第二期训练营&#xff0c;我也将会通过笔记博客的方式记录学习的过程与遇到的问题&#xff0c;并为代码添加注释&#xff0c;希望可以帮助到你们。 记得点赞哟(๑ゝω╹๑) 茴香豆&#xff1a;搭建…...

Advanced RAG 03:运用 RAGAs 与 LlamaIndex 评估 RAG 应用

编者按&#xff1a;目前&#xff0c;检索增强生成&#xff08;Retrieval Augmented Generation&#xff0c;RAG&#xff09;技术已经广泛使用于各种大模型应用场景。然而&#xff0c;如何准确评估 RAG 系统的性能和效果&#xff0c;一直是业界和学界共同关注的重点问题。若无法…...

leetcode

找到字符串中所有字母异位词 给定两个字符串 s 和 p&#xff0c;找到 s 中所有 p 的 异位词 的子串&#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串&#xff08;包括相同的字符串&#xff09; 示例 1: 输入: s "…...

Unity DOTS《群体战斗弹幕游戏》核心技术分析之3D角色动画

最近DOTS发布了正式的版本, 我们来分享现在流行基于群体战斗的弹幕类游戏&#xff0c;实现的核心原理。今天给大家介绍大规模战斗群体3D角色的动画如何来实现。 DOTS 对角色动画支持的局限性 截止到Unity DOTS发布的版本1.0.16,目前还是无法很好的支持3D角色动画。在DOTS 的ba…...

react异步组件如何定义使用 标准使用方法

目录 默认导出和命名导出的格式 默认导出的组件 使用方式 命名导出的组件 使用方式 默认导出和命名导出的格式 默认导出: // person.js const person {name: Alice,age: 30 };export default person;命名导出&#xff1a; // math.js export const add (a, b) > a b; exp…...

React + Ts + Vite + Antd 项目搭建

1、创建项目 npm create vite 项目名称 选择 react 选择 typescript 关闭严格模式 建议关闭严格模式&#xff0c;因为不能自动检测副作用&#xff0c;有意双重调用。将严格模式注释即可。 2、配置sass npm install sass 更换所有后缀css为sass vite.config.ts中注册全局样式 /…...

js爬虫puppeteer库 解决网页动态渲染无法爬取

我们爬取这个网址上面的股票实时部分宇通客车(600066)_股票价格_行情_走势图—东方财富网 我们用正常的方法爬取会发现爬取不下来&#xff0c;是因为这个网页这里是实时渲染的&#xff0c;我们直接通过网址接口访问这里还没有渲染出来 于是我们可以通过下面的代码来进行爬取: …...

代码随想录:二叉树5

目录 102.二叉树的层序遍历 题目 代码&#xff08;队列实现&#xff09; 107.二叉树的层序遍历II 题目 代码 199.二叉树的右视图 题目 代码 637.二叉树的层平均值 题目 代码 102.二叉树的层序遍历 题目 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍…...

Tomcat 获取客户端真实IP X-Forwarded-For

Tomcat 获取客户端真实IP X-Forwarded-For 代码实现&#xff1a; 在Host标签下面添加代码&#xff1a; <Valve className"org.apache.catalina.valves.RemoteIpValve" remoteIpHeader"x-forwarded-for" remoteIpProxiesHeader"x-forwarded-by&q…...

记录PS学习查漏补缺

PS学习 PS学习理论快捷键抠图PS专属多软件通用快捷键 PS学习 理论 JPEG &#xff08;不带透明通道&#xff09; PNG (带透明通道) 快捷键 抠图 抠图方式 魔棒工具 反选选中区域 CtrlShiftI&#xff08;反选&#xff09; 钢笔抠图注意事项 按着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算法是一种无监督学习算法&#xff0c;主要用于数据聚类。其工作原理基于迭代优化&#xff0c;将数据点划分为K个集群&#xff0c;使得每个数据点都属于最近的集群&#xff0c;并且每个集群的中心&#xff08;质心&#xff09;是所有属于该集群的数据点的平均值。以下是…...

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 信息安全管理与评估 网络系统管理 网络搭建与应用 云计算 软件测试 移动应用开发 任务书&#xff0c;赛题&#xff0c;解析等资料&#xff0c;知识点培训服务 添加博主wx&#xff1a;liuliu548…...

Webrtc 信令服务器实现

webrtc建联流程图 由上图可知&#xff0c;所谓的信令服务器其实就是将peer的offer/candidate/answer传给对端而已。这样的话实现方式就有很多种了&#xff0c;目前普遍的方式HTTP/HTTPS&#xff0c;WS/WSS。像webrtc-demo-peerconnection就是实现HTTP这种方式。本文使用WS&…...

【Blockchain】连接智能合约与现实世界的桥梁Chainlink

去中心化预言机试图实现依赖因果关系而不是个人关系的去信任和确定性结果。它以与区块链网络相同的方式实现这些结果&#xff0c;即在许多网络参与者之间分配信任。通过利用许多不同的数据源并实施不受单个实体控制的预言机系统&#xff0c;去中心化的预言机网络有可能为智能合…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...