当前位置: 首页 > 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;去中心化的预言机网络有可能为智能合…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...