LRU算法
文章目录
- LRU算法
- LRU 如何实现
- LinkedHashMap来实现的LRU算法的缓存
- HashMap实现LRU算法的缓存
LRU算法
LRU(Least Recently Used)算法可以使用哈希表和双向链表来实现。哈希表用于快速查找数据,双向链表用于记录数据的访问顺序。以下是LRU算法的具体实现:
- 使用一个哈希表和一个双向链表来实现缓存。
- 哈希表中的key是数据的键值,value是对应节点在双向链表中的位置。
- 双向链表中,头部是最近访问过的数据,尾部是最久未被访问的数据。
- 当需要获取缓存数据时,先通过哈希表查找是否存在缓存数据。如果存在,则将对应节点移动到链表头部;否则,返回null。
- 当需要插入新的数据到缓存时,先检查缓存是否已满。如果已满,则删除双向链表的尾部节点,并从哈希表中删除该节点;然后再将新数据插入到链表头部,并在哈希表中添加新节点。
- 当需要删除缓存数据时,先通过哈希表查找节点位置,然后从链表中删除该节点,并同时从哈希表中删除对应项。
总之,LRU算法通过维护一个哈希表和一个双向链表来实现缓存淘汰策略。当缓存满时,将最久未被访问的数据从缓存中删除,保留最近访问过的数据。这样可以有效减少缓存命中率的损失,提高系统性能
LRU 如何实现
最近最少使用策略 LRU(Least Recently Used)是一种缓存淘汰算法,是一种缓存淘汰机制。
使用双向链表实现的队列,队列的最大容量为缓存的大小。在使用过程中,把最近使用的页面移动到队列头,最近没有使用的页面将被放在队列尾的位置
使用一个哈希表,把页号作为键,把缓存在队列中的节点的地址作为值,只需要把这个页 对应的节点移动到队列的前面,如果需要的页面在内存中,此时需要把这个页面加载到内 存中,简单的说,就是将一个新节点添加到队列前面,并在哈希表中跟新相应的节点地 址,如果队列是满的,那么就从队尾移除一个节点,并将新节点添加到队列的前面。
1、概念:其实解释起来很简单,LRU就 是Least Recently Used的缩写,翻译过来就是“最近最少使用”。也就是说LRU算法会将最近最少用的缓存移除,让给最新使⽤的缓存。⽽往往最常读取的,也就是读取次数最多的,所以利⽤好LRU算法,我们能够提供对热点数据的缓存效率,能够提⾼缓存服务的内存使⽤率。
2、实现:
1、思路:
i. 限制缓存大小
ii. 查询出最近最晚⽤的缓存
iii. 给最近最少⽤的缓存做⼀个标识
2、代码:
LinkedHashMap来实现的LRU算法的缓存
package com.lc.lru;import java.util.LinkedHashMap;
import java.util.Map;public class LRUCache<K, V> extends LinkedHashMap<K, V> {private int capacity;public LRUCache(int capacity) {super(capacity, 0.75f, true);this.capacity = capacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}public static void main(String[] args) {LRUCache<Integer, String> cache = new LRUCache<>(2);cache.put(1, "One");cache.put(2, "Two");System.out.println(cache); // 输出:{1=One, 2=Two}cache.put(3, "Three");System.out.println(cache); // 输出:{2=Two, 3=Three}cache.get(2);System.out.println(cache); // 输出:{3=Three, 2=Two}}}
HashMap实现LRU算法的缓存
import java.util.HashMap;
import java.util.Map;/*** @Desc 采用LRU置换算法的缓存* @Author lc* @Date 2022/4/3 19:44*/
public class LRUCache<K, V> {// 静态内部类,双向链表中的节点类,key理解为页面号,val理解为页面内容static class Entry<K, V> {public Entry<K, V> prev;public Entry<K, V> next;public K key;public V val;public Entry() {}public Entry(K key, V val) { this.key = key; this.val = val; }}private Entry<K, V> head, tail; // 虚拟头节点和虚拟尾节点private final int capacity; // 缓存容量private int size; // 缓存占用量Map<K, Entry<K, V>> cache; // 哈希表,记录双向列表节点的地址值public LRUCache(int capacity) {this.capacity = capacity;initCache();}// 初始化LRU缓存private void initCache() {head = new Entry<>();tail = new Entry<>();head.next = tail;tail.prev = head;size = 0;cache = new HashMap<>(this.capacity);}private V get(K key) {Entry<K, V> entry = cache.get(key);if(entry != null) {moveToTail(entry);return entry.val;} else {return null;}}private void put(K key, V val) {Entry<K, V> entry = cache.get(key);if(entry != null) {// 缓存命中entry.val = val;moveToTail(entry);} else {// 缓存未命中if(size == capacity) {// 缓存已满,删除链表头部节点Entry<K, V> h = head.next;deleteEntry(h);cache.remove(h.key);size--;}// 添加新页面到链表尾部Entry<K, V> newEntry = new Entry<>(key, val);addToTail(newEntry);cache.put(key, newEntry);size++;}}private void moveToTail(Entry<K, V> entry) {deleteEntry(entry);addToTail(entry);}private void addToTail(Entry<K, V> entry) {if(entry != null) {entry.next = tail;entry.prev = tail.prev;tail.prev.next = entry;tail.prev = entry;}}private void deleteEntry(Entry<K, V> entry) {if(entry != null) {entry.prev.next = entry.next;entry.next.prev = entry.prev;}}public static void main(String[] args) {LRUCache<Integer, String> cache = new LRUCache<>(2);cache.put(1,"可口可乐");cache.put(2,"雪碧");System.out.println("页面1的内容:" + cache.get(1));cache.put(3,"果粒橙"); // 此时缓存已满,且页面2最久未被使用(因为cache.get(1)访问了页面1),页面2被置换成页面3System.out.println("页面2的内容:" + cache.get(2)); // 页面2已被换出,访问不到}}
相关文章:
LRU算法
文章目录 LRU算法LRU 如何实现LinkedHashMap来实现的LRU算法的缓存HashMap实现LRU算法的缓存 LRU算法 LRU(Least Recently Used)算法可以使用哈希表和双向链表来实现。哈希表用于快速查找数据,双向链表用于记录数据的访问顺序。以下是LRU算法…...
JVM运行时数据区 - 程序计数器
运行时数据区 Java虚拟机在执行Java程序的过程中,会把它管理的内存划分成若干个不同的区域,这些区域有各自的用途、创建及销毁时间,有些区域随着虚拟机的启动一直存在,有些区域则随着用户线程的启动和结束而建立和销毁࿰…...
1.JAVA小项目(零钱通)
一、说明 博客内容:B站韩顺平老师的视频,以及代码的整理。此项目分为两个版本: 面向过程思路实现面向对象思路实现 韩老师视频地址:【【零基础 快速学Java】韩顺平 零基础30天学会Java】 https://www.bilibili.com/video/BV1fh4…...
Redis这一篇就够了
一.概述 Redis是什么? Redis是远程服务字典服务,是一个开源的使用ANSI C语言编写,支持网络,可基于内存亦可持久化的日志型,Key-Value数据库,并提供多种语言的API。 redis会周期性把更新的数据写入磁盘或把…...
Java web应用性能分析之【jvisualvm远程连接云服务器】
Java web应用性能分析之【java进程问题分析概叙】-CSDN博客 Java web应用性能分析之【java进程问题分析工具】-CSDN博客 前面整理了java进程问题分析和分析工具,现在可以详细看看jvisualvm的使用,一般java进程都是部署云服务器,或者托管IDC机…...
springboot发送短信验证码,结合redis 实现限制,验证码有效期2分钟,有效期内禁止再次发送,一天内发送超3次限制
springboot结合redis发送短信验证码,实现限制发送操作 前言(可忽略)实现思路正题效果图示例手机号不符合规则校验图成功发送验证码示例图redis中缓存随机数字验证码,2分钟后失效删除redis缓存图验证码有效期内 返回禁止重复发送图验证码24小时内发送达到3次…...
【Python】使用 Pandas 统计每行数据中的空值
缘分让我们相遇乱世以外 命运却要我们危难中相爱 也许未来遥远在光年之外 我愿守候未知里为你等待 我没想到为了你我能疯狂到 山崩海啸没有你根本不想逃 我的大脑为了你已经疯狂到 脉搏心跳没有你根本不重要 🎵 邓紫棋《光年之外》 在数据分析…...
1pannel部署onenav导航容器编排模板
onenav导航 1pannel部署onenav导航容器编排模板 networks:1panel-network:external: true services:onenav:container_name: onenavimage: helloz/onenav:latestlabels:createdBy: Appsnetworks:- 1panel-networkports:- 127.0.0.1:{port}:80environment:- TZAsia/Shanghaivol…...
linux--实时性优化
linux--实时性优化 1 介绍2 实时性需求3 代表性实时系统4 嵌入式系统嵌入式软件系统结构处理器时钟节拍多任务机制任务调度方式任务调度算法时间片调度算法优先级调度算法基于优先级的时间片调度算法 5 cyclictest 测试工具命令说明命令分析参数含义 6 linux 实时性改进某版本上…...
React-基础样式控制
组件基础样式方案 React组件基础的样式控制有两种方式 1、行内样式(不推荐) 属性名是多个单词的需要使用驼峰写法 也可以把样式都提取到一个变量里,再赋值到style里 2、class类名控制 classnames优化类名控制 classnames是一个简单的JS库&…...
制作ChatPDF之前端Vue搭建(二)
前端界面 接上篇: 制作ChatPDF之Elasticsearch8.13.4搭建(一) 为了实现一个基于 Vue.js 的前端应用,用户可以上传 PDF 文件,输入查询,并在输出框中显示查询结果,你需要以下步骤: 初始化 Vue …...
汽车IVI中控开发入门及进阶(二十一):DAB和FM 收音机
前言: 在过去的十年里,数字收音机对车载娱乐产生了重大影响。现在,几乎每辆新车都标配了这项技术,这也是我们60%以上的人收听收音机的方式。甚至有传言称,在不久的将来,将永久关闭调频发射机,使许多车载收音机过时。但一些相对年轻的汽车在工厂里仍然没有安装DAB,而且…...
智能sql LLM
DB-GPT:彻底改变数据库与私有LLM技术的交互 智能SQL生成:后端技术与LLM的完美结合 智能SQL生成:后端技术与LLM的完美结合_llm sql-CSDN博客 GitHub - eosphoros-ai/DB-GPT: AI Native Data App Development framework with AWEL(Agentic Wor…...
大聪明教你学Java | 深入浅出聊 Stream.parallel()
前言 🍊作者简介: 不肯过江东丶,一个来自二线城市的程序员,致力于用“猥琐”办法解决繁琐问题,让复杂的问题变得通俗易懂。 🍊支持作者: 点赞👍、关注💖、留言Ǵ…...
图解大模型分布式并行各种通信原语
背景 在分布式集群上执行大模型任务时候,往往使用到数据并行,流水线并行,张量并行等技术,这些技术本质上也就是对数据进行各种方案的切分,然后放到不同的节点上运算。不同节点在计算的过程中需要对数据分发或者同步等…...
张大哥笔记:下一个风口是什么?
我们经常会问,下一个风口是什么?我们可以大胆预测一下,2024年的风口是什么呢? 40年前,如果你会开车,那就是响当当的铁饭碗; 30年前,如果你会英语和电脑,那也绝对是个人才…...
AI去衣技术中的几何着色:揭秘数字时尚的魔法
在数字化时代,人工智能(AI)正以前所未有的速度改变我们的生活,从智能家居到自动驾驶汽车,再到个性化医疗。然而,AI的影响远不止于此。它正在重塑我们对艺术、设计和时尚的理解。特别是在数字时尚领域&#…...
Leecode---技巧---只出现一次的数字 / 多数元素
题解: 利用异或运算 a⊕a 0 的性质,可用来消除所有出现了两次的元素,最后剩余的即为所得。 class Solution { public:int singleNumber(vector<int>& nums){// 初始化为0int ans 0;for(int x: nums){// 异或操作ans ^ x;}retur…...
为图片设置经纬度信息
一、java实现 小编看了很多技术博客,但是测试要么下载的jar包中的api和博客对不上,要么就是不对,总之没实现 Java 读取图片信息 java 写入 exif 信息 使用Java读取和修改图片的Exif信息 java获取图片的GPS信息 https://drewnoakes.com/code/e…...
密码和密钥的联系与区别
密码和密钥是两个非常重要的概念,但容易混淆这两者,以下内容介绍了它们的联系和区别: 一、定义 密码(Password),在日常语境中,通常指的是个人为了验证自己的身份而设置的一段秘密的字符序列&am…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
