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

最近最少使用算法(LRU最近最少使用)缓存替换算法

含义

最近最少使用算法(LRU)是一种缓存替换算法,用于在缓存空间有限的情况下,选择最少使用的数据项进行替换。该算法的核心思想是基于时间局部性原理,即刚被访问的数据在未来也很有可能被再次访问。

实现

LRU算法的实现可以通过一个双向链表和一个哈希表来完成。双向链表用于按照访问顺序维护缓存中的数据项,哈希表用于存储数据项的引用,以便快速定位和访问。

如果缓存未满,则直接将新的数据项插入链表头部。
如果缓存已满,则将链表尾部的数据项移除,并将新的数据项插入链表头部。

实现链表

    1. 新数据插入到链表头部;
    1. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
    1. 当链表满的时候,将链表尾部的数据丢弃。

特点

存在问题:

当存在热点数据时,LRU的效率很好,但偶发性的、周期性批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。

复杂度 : 实现简单。
代价 :命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。(即:LRU算法的实现需要维护一个适当的数据结构,所以在实际应用中可能会有一定的开销。)

代码实现LRU

注意事项:

需要保证多线程下数据的一致性;

方法1、使用synchronized 字段保证线程同步;
方法2、 使用Lock ,它是一个接口,用于支持更灵活的线程同步

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.Map;/*** 类说明:利用LinkedHashMap实现简单的缓存, 必须实现removeEldestEntry方法,具体参见JDK文档** @param <K>* @param <V>* @author dennis*/
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {private final int maxCapacity;private static final float DEFAULT_LOAD_FACTOR = 0.75f;private final Lock lock = new ReentrantLock();public LRULinkedHashMap(int maxCapacity) {super(maxCapacity, DEFAULT_LOAD_FACTOR, true);this.maxCapacity = maxCapacity;}@Overrideprotected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {return size() > maxCapacity;}@Overridepublic boolean containsKey(Object key) {try {lock.lock();return super.containsKey(key);} finally {lock.unlock();}}@Overridepublic V get(Object key) {try {lock.lock();return super.get(key);} finally {lock.unlock();}}@Overridepublic V put(K key, V value) {try {lock.lock();return super.put(key, value);} finally {lock.unlock();}}public int size() {try {lock.lock();return super.size();} finally {lock.unlock();}}public void clear() {try {lock.lock();super.clear();} finally {lock.unlock();}}public Collection<Map.Entry<K, V>> getAll() {try {lock.lock();return new ArrayList<Map.Entry<K, V>>(super.entrySet());} finally {lock.unlock();}}
}  
测试代码: 测试结果见备注已经抛弃了test1 而替换为了最近一次使用过的test3
@Test
public  void a1() {LRULinkedHashMap lruLinkedHashMap = new LRULinkedHashMap(3);lruLinkedHashMap.put("test","1235314");lruLinkedHashMap.put("test1","1235314");lruLinkedHashMap.get("test");lruLinkedHashMap.put("test2","1235314");System.out.println(lruLinkedHashMap.getAll()); // [test1=1235314, test=1235314, test2=1235314]lruLinkedHashMap.put("test3","1235314");System.out.println(lruLinkedHashMap.getAll()); // [test=1235314, test2=1235314, test3=1235314]
}

相关文章:

最近最少使用算法(LRU最近最少使用)缓存替换算法

含义 最近最少使用算法&#xff08;LRU&#xff09;是一种缓存替换算法&#xff0c;用于在缓存空间有限的情况下&#xff0c;选择最少使用的数据项进行替换。该算法的核心思想是基于时间局部性原理&#xff0c;即刚被访问的数据在未来也很有可能被再次访问。 实现 LRU算法的…...

sublime_text的快捷键

sublime_text的快捷键 向下复制, 复制光标所在整行并插入到下一行&#xff1a;通过 CtrlShiftD 实现快速复制当前行的功能。 可选多行, 不选则复制当前行 ctrl Shift D 删除当前行&#xff1a;通过 CtrlShiftK 实现快速删除当前行的功能。 可选多行, 不选则删当前行 ctrl S…...

使用Pygame制作“贪吃蛇”游戏

贪吃蛇 是一款经典的休闲小游戏&#xff1a;玩家通过操控一条会不断变长的“蛇”在屏幕中移动&#xff0c;去吃随机出现的食物&#xff0c;同时要避免撞到墙壁或自己身体的其他部分。由于其逻辑相对简单&#xff0c;但可玩性和扩展性都不错&#xff0c;非常适合作为新手练习游戏…...

本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操

本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操 Janus-Pro-7B介绍 Janus-Pro-7B 是由 DeepSeek 开发的多模态 AI 模型&#xff0c;它在理解和生成方面取得了显著的进步。这意味着它不仅可以处理文本&#xff0c;还可以处理图像等其他模态的信息。 模型主要特点:Permalink…...

Java开发vscode环境搭建

1 几个名词 JDK Java Development Kit JRE Java Runtion Environment JVM JDK 包括 Compiler,debugger,JRE等。JRE包括JVM和Runtime Library。 2 配置环境 2.1 安装JDK 类比 C/C的 g工具 官网&#xff1a;https://www.oracle.com/java/technologies/downloads/ 根据自己使…...

深入解析:一个简单的浮动布局 HTML 示例

深入解析&#xff1a;一个简单的浮动布局 HTML 示例 示例代码解析代码结构分析1. HTML 结构2. CSS 样式 核心功能解析1. 浮动布局&#xff08;Float&#xff09;2. 清除浮动&#xff08;Clear&#xff09;3. 其他样式 效果展示代码优化与扩展总结 在网页设计中&#xff0c;浮动…...

车载软件 --- 大一新生入门汽车零部件嵌入式开发

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 简单&#xff0c;单纯&#xff0c;喜欢独处&#xff0c;独来独往&#xff0c;不易合同频过着接地气的生活…...

DDD - 领域驱动设计分层架构:构建可演化的微服务架构

文章目录 引言1. 什么是DDD分层架构&#xff1f;1.1 DDD分层架构的演变1.2 四层架构的起源与问题1.3 依赖倒置和五层架构 2. DDD分层架构的核心层次2.1 用户接口层&#xff08;User Interface Layer&#xff09;2.2 应用层&#xff08;Application Layer&#xff09;2.3 领域层…...

2025数学建模美赛|赛题翻译|E题

2025数学建模美赛&#xff0c;E题赛题翻译 更多美赛内容持续更新中......

DeepSeek-V3 与 DeepSeek R1 对比分析:技术与应用的全面解析

一、背景 在当今科技飞速发展的时代&#xff0c;深度学习技术如同一股强大的浪潮&#xff0c;席卷了自然语言处理&#xff08;NLP&#xff09;、计算机视觉&#xff08;CV&#xff09;以及多模态模型等众多领域。从智能语音助手到图像识别技术&#xff0c;从文本生成工具到多模…...

qt-Quick3D笔记之官方例程Runtimeloader Example运行笔记

qt-Quick3D笔记之官方例程Runtimeloader Example运行笔记 文章目录 qt-Quick3D笔记之官方例程Runtimeloader Example运行笔记1.例程运行效果2.例程缩略图3.项目文件列表4.main.qml5.main.cpp6.CMakeLists.txt 1.例程运行效果 运行该项目需要自己准备一个模型文件 2.例程缩略图…...

Linux内核中的页面错误处理机制与按需分页技术

在现代操作系统中,内存管理是核心功能之一,而页面错误(Page Fault)处理机制是内存管理的重要组成部分。当程序访问一个尚未映射到物理内存的虚拟地址时,CPU会触发页面错误异常,内核需要捕获并处理这种异常,以决定如何响应,例如加载缺失的页面、处理权限错误等。Linux内…...

PHP实现混合加密方式,提高加密的安全性(代码解密)

代码1&#xff1a; <?php // 需要加密的内容 $plaintext 授权服务器拒绝连接;// 1. AES加密部分 $aesKey openssl_random_pseudo_bytes(32); // 生成256位AES密钥 $iv openssl_random_pseudo_bytes(16); // 生成128位IV// AES加密&#xff08;CBC模式&#xff09…...

使用openwrt搭建ipsec隧道

背景&#xff1a;最近同事遇到了个ipsec问题&#xff0c;做的ipsec特性&#xff0c;ftp下载ipv6性能只有100kb, 正面定位该问题也蛮久了&#xff0c;项目没有用openwrt, 不过用了开源组件strongswan, 加密算法这些也是内核自带的&#xff0c;想着开源的不太可能有问题&#xff…...

大语言模型(LLM)模拟金融市场参与者行为

大语言模型(LLM)模拟金融市场参与者行为 研究背景 传统深度学习模型通过识别市场数据历史模式预测市场,但未捕捉个体决策过程。LLM 虽能学习人类对不同提示的反应,但在模拟金融市场参与者时面临挑战:个体投资者不总是理性决策,LLM 可能无法捕捉;LLM 数值和金融知识可靠…...

用一个例子详细说明python单例模式

单例模式是一种设计模式&#xff0c;它确保一个类只有一个实例&#xff0c;并提供一个全局访问点来访问该实例。这在需要控制资源&#xff08;如数据库连接、文件系统等&#xff09;的访问时非常有用。 下面是一个使用Python实现单例模式的例子&#xff1a; class Singleton:…...

第1章 量子暗网中的血色黎明

月球暗面的危机与阴谋 量子隧穿效应催生的幽蓝电弧&#xff0c;于环形山表面肆意跳跃&#xff0c;仿若无数奋力挣扎的机械蠕虫&#xff0c;将月球暗面的死寂打破&#xff0c;徒增几分诡异。艾丽伫立在被遗弃的“广寒宫”量子基站顶端&#xff0c;机械义眼之中&#xff0c;倒映着…...

LeetCode--84. 柱状图中最大的矩形【单调栈】

84. 柱状图中最大的矩形 正文 题目如下 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。 求在该柱状图中&#xff0c;能够勾勒出来的矩形的最大面积。 这道题暴力很简单&#xff0c;但是时间复杂度是O(N^2)&#xf…...

网络工程师 (8)存储管理

一、页式存储基本原理 &#xff08;一&#xff09;内存划分 页式存储首先将内存物理空间划分成大小相等的存储块&#xff0c;这些块通常被称为“页帧”或“物理页”。每个页帧的大小是固定的&#xff0c;例如常见的页帧大小有4KB、8KB等&#xff0c;这个大小由操作系统决定。同…...

【Leetcode 每日一题】541. 反转字符串 II

问题背景 给定一个字符串 s s s 和一个整数 k k k&#xff0c;从字符串开头算起&#xff0c;每计数至 2 k 2k 2k 个字符&#xff0c;就反转这 2 k 2k 2k 字符中的前 k k k 个字符。 如果剩余字符少于 k k k 个&#xff0c;则将剩余字符全部反转。如果剩余字符小于 2 k…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...