LinkedList 实现 LRU 缓存

news/2024/9/25 15:24:05/

LRU(Least Recently Used,最近最少使用)缓存是一种缓存淘汰策略,用于在缓存满时淘汰最久未使用的元素。

关键:

缓存选什么结构?

怎么实现访问顺序?

import java.util.*;public class LRUCache<K, V> {private final int capacity; // 缓存容量private final Map<K, V> cache; // 用于存储缓存数据private final LinkedList<K> order; // 用于维护访问顺序public LRUCache(int capacity) {this.capacity = capacity;this.cache = new HashMap<>(capacity);this.order = new LinkedList<>();}public V get(K key) {if (!cache.containsKey(key)) {return null; // 如果缓存中不存在该键,返回 null}// 将访问的键移到队列的尾部,表示最近使用order.remove(key);order.addLast(key);return cache.get(key);}public void put(K key, V value) {if (cache.containsKey(key)) {// 如果缓存中已经存在该键,更新值并将键移到队列的尾部cache.put(key, value);order.remove(key);order.addLast(key);} else {if (cache.size() >= capacity) {// 如果缓存满了,移除最久未使用的键K oldestKey = order.removeFirst();cache.remove(oldestKey);}// 添加新键值对到缓存cache.put(key, value);order.addLast(key);}}public static void main(String[] args) {LRUCache<String, String> lruCache = new LRUCache<>(3);lruCache.put("1", "one");lruCache.put("2", "two");lruCache.put("3", "three");System.out.println(lruCache.get("1")); // 输出: onelruCache.put("4", "four");System.out.println(lruCache.get("2")); // 输出: null (因为2是最久未使用的)}
}

 测试讲解:

先定义了大小为3的缓存,然后存1,2,3,此时的访问顺序1-2-3,list头部是最早访问的,尾部是最晚访问的,此时缓存已满,然后访问了1,则现在的顺序是2-3-1,可见,2是那个最久没被访问的,我再添加新元素4时,需要删除的是2,顺序变成3-1-4。

        


http://www.ppmy.cn/news/1503593.html

相关文章

第十九天培训笔记

上午 1 、构建 vue 发行版本 [rootserver eleme_web]# nohup npm run serve& // 运行 vue 项目 [rootserver eleme_web]# mkdir /eleme [rootserver eleme_web]# cp -r /root/eleme_web/dist/* /eleme/ // 将项目整体 移动到 /eleme 目录下 [rootserver eleme_web]# …

vue3实现面包屑-基础实现

1.在默认路由router文件下新增两个额外的文件page&#xff1a;存放额外的路由列表&#xff0c;注意这里需要引入有router-view视图的页面&#xff0c;这里我是采用let Main () > import("v/layout/Main.vue");代码&#xff1a; 在page中使用&#xff1a; 2.dyna…

vscode+platformio开发小技巧

使用vscodeplatformio开发&#xff0c;具体安装配置文章很多&#xff0c;这里分享一些方便使用的小技巧&#xff0c;让使用体验在不增加学习成本的情况下更加丝滑。 1、配置依赖库 在使用vscode开发前&#xff0c;arduino环境遗留了一些库文件&#xff0c;这些第三方库可以通…

Spring-Ioc,Di,Bean

博客主页&#xff1a;音符犹如代码系列专栏&#xff1a;JavaWeb关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ 目录 IOC DI Bean 在上一期我们给大家讲解了三层架构和分层解耦&#xff…

嵌入式学习Day19---Linux软件编程

目录 一、标准I/O 1.1.fseek 1.偏移量 2.实例 ​编辑 1.2.ftell 2.实例 ​编辑 二、文件I/O 2.1.打开文件 1.open 2.2.实例 2.2.读写文件 1.write 实例 ​编辑 2.read 实例 2.3.关闭文件 1.close 2.3.lseek 实例 三、标准I/O与文件I/O的区别 3.1.区别 四、其…

【软件建模与设计】-07-静态建模

目录 1、类之间关系 1.1、关联 1.1.1、关联的多重性 1.1.2、三元关联 1.1.3、一元关联 1.1.4、关联类 2、组合与聚合层次 2.1、组合 2.2、聚合 3、泛化/特化层次 4、约束 5、静态建模和UML 5.1、问题域的静态建模 6、系统上下文的静态建模 7、使用UML构造型对类…

PostgreSQL——查询扫描介绍

顺序扫描 概述 顺序扫描&#xff08;Sequential Scan&#xff09;是PostgreSQL中一种基本的数据检索方式&#xff0c;它通过按顺序读取表中的所有页面来查找满足查询条件的记录。这种方式不依赖于索引&#xff0c;因此在某些情况下可能是唯一的选择&#xff0c;尤其是当表没有…

轻松入门Linux—CentOS,直接拿捏 —/— <5>

一、Linux常用工具 1、tar打包命令详解 当 tar 命令用于打包操作时&#xff0c;该命令的基本格式为&#xff1a; tar [选项] 源文件或目录 常用选项&#xff1a; 1.1 打包文件 例如&#xff0c;我有几个文件&#xff0c;将他们打包成一个文件&#xff0c;以tar结尾的后缀名 …