最近最少使用算法(LRU最近最少使用)缓存替换算法
含义
最近最少使用算法(LRU)是一种缓存替换算法,用于在缓存空间有限的情况下,选择最少使用的数据项进行替换。该算法的核心思想是基于时间局部性原理,即刚被访问的数据在未来也很有可能被再次访问。
实现
LRU算法的实现可以通过一个双向链表和一个哈希表来完成。双向链表用于按照访问顺序维护缓存中的数据项,哈希表用于存储数据项的引用,以便快速定位和访问。
如果缓存未满,则直接将新的数据项插入链表头部。
如果缓存已满,则将链表尾部的数据项移除,并将新的数据项插入链表头部。
实现链表
-
- 新数据插入到链表头部;
-
- 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
-
- 当链表满的时候,将链表尾部的数据丢弃。
特点
存在问题:
当存在热点数据时,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最近最少使用)缓存替换算法
含义 最近最少使用算法(LRU)是一种缓存替换算法,用于在缓存空间有限的情况下,选择最少使用的数据项进行替换。该算法的核心思想是基于时间局部性原理,即刚被访问的数据在未来也很有可能被再次访问。 实现 LRU算法的…...
sublime_text的快捷键
sublime_text的快捷键 向下复制, 复制光标所在整行并插入到下一行:通过 CtrlShiftD 实现快速复制当前行的功能。 可选多行, 不选则复制当前行 ctrl Shift D 删除当前行:通过 CtrlShiftK 实现快速删除当前行的功能。 可选多行, 不选则删当前行 ctrl S…...
使用Pygame制作“贪吃蛇”游戏
贪吃蛇 是一款经典的休闲小游戏:玩家通过操控一条会不断变长的“蛇”在屏幕中移动,去吃随机出现的食物,同时要避免撞到墙壁或自己身体的其他部分。由于其逻辑相对简单,但可玩性和扩展性都不错,非常适合作为新手练习游戏…...
本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操
本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操 Janus-Pro-7B介绍 Janus-Pro-7B 是由 DeepSeek 开发的多模态 AI 模型,它在理解和生成方面取得了显著的进步。这意味着它不仅可以处理文本,还可以处理图像等其他模态的信息。 模型主要特点: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工具 官网:https://www.oracle.com/java/technologies/downloads/ 根据自己使…...
深入解析:一个简单的浮动布局 HTML 示例
深入解析:一个简单的浮动布局 HTML 示例 示例代码解析代码结构分析1. HTML 结构2. CSS 样式 核心功能解析1. 浮动布局(Float)2. 清除浮动(Clear)3. 其他样式 效果展示代码优化与扩展总结 在网页设计中,浮动…...
车载软件 --- 大一新生入门汽车零部件嵌入式开发
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 简单,单纯,喜欢独处,独来独往,不易合同频过着接地气的生活…...
DDD - 领域驱动设计分层架构:构建可演化的微服务架构
文章目录 引言1. 什么是DDD分层架构?1.1 DDD分层架构的演变1.2 四层架构的起源与问题1.3 依赖倒置和五层架构 2. DDD分层架构的核心层次2.1 用户接口层(User Interface Layer)2.2 应用层(Application Layer)2.3 领域层…...
2025数学建模美赛|赛题翻译|E题
2025数学建模美赛,E题赛题翻译 更多美赛内容持续更新中......
DeepSeek-V3 与 DeepSeek R1 对比分析:技术与应用的全面解析
一、背景 在当今科技飞速发展的时代,深度学习技术如同一股强大的浪潮,席卷了自然语言处理(NLP)、计算机视觉(CV)以及多模态模型等众多领域。从智能语音助手到图像识别技术,从文本生成工具到多模…...
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: <?php // 需要加密的内容 $plaintext 授权服务器拒绝连接;// 1. AES加密部分 $aesKey openssl_random_pseudo_bytes(32); // 生成256位AES密钥 $iv openssl_random_pseudo_bytes(16); // 生成128位IV// AES加密(CBC模式)…...
使用openwrt搭建ipsec隧道
背景:最近同事遇到了个ipsec问题,做的ipsec特性,ftp下载ipv6性能只有100kb, 正面定位该问题也蛮久了,项目没有用openwrt, 不过用了开源组件strongswan, 加密算法这些也是内核自带的,想着开源的不太可能有问题ÿ…...
大语言模型(LLM)模拟金融市场参与者行为
大语言模型(LLM)模拟金融市场参与者行为 研究背景 传统深度学习模型通过识别市场数据历史模式预测市场,但未捕捉个体决策过程。LLM 虽能学习人类对不同提示的反应,但在模拟金融市场参与者时面临挑战:个体投资者不总是理性决策,LLM 可能无法捕捉;LLM 数值和金融知识可靠…...
用一个例子详细说明python单例模式
单例模式是一种设计模式,它确保一个类只有一个实例,并提供一个全局访问点来访问该实例。这在需要控制资源(如数据库连接、文件系统等)的访问时非常有用。 下面是一个使用Python实现单例模式的例子: class Singleton:…...
第1章 量子暗网中的血色黎明
月球暗面的危机与阴谋 量子隧穿效应催生的幽蓝电弧,于环形山表面肆意跳跃,仿若无数奋力挣扎的机械蠕虫,将月球暗面的死寂打破,徒增几分诡异。艾丽伫立在被遗弃的“广寒宫”量子基站顶端,机械义眼之中,倒映着…...
LeetCode--84. 柱状图中最大的矩形【单调栈】
84. 柱状图中最大的矩形 正文 题目如下 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 这道题暴力很简单,但是时间复杂度是O(N^2)…...
网络工程师 (8)存储管理
一、页式存储基本原理 (一)内存划分 页式存储首先将内存物理空间划分成大小相等的存储块,这些块通常被称为“页帧”或“物理页”。每个页帧的大小是固定的,例如常见的页帧大小有4KB、8KB等,这个大小由操作系统决定。同…...
【Leetcode 每日一题】541. 反转字符串 II
问题背景 给定一个字符串 s s s 和一个整数 k k k,从字符串开头算起,每计数至 2 k 2k 2k 个字符,就反转这 2 k 2k 2k 字符中的前 k k k 个字符。 如果剩余字符少于 k k k 个,则将剩余字符全部反转。如果剩余字符小于 2 k…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例
目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码:冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...
