集合系列(二十六) -利用LinkedHashMap实现一个LRU缓存

2024-06-19 18:52

本文主要是介绍集合系列(二十六) -利用LinkedHashMap实现一个LRU缓存,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、什么是 LRU

LRU是 Least Recently Used 的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰

简单的说就是,对于一组数据,例如:int[] a = {1,2,3,4,5,6},如果1,2这几个数字经常被使用,那么会排在3,4,5,6的后面,数组变成如下:int[] a = {3,4,5,6,1,2},如果一个数字,经常不被使用,就会排在最前面!

LRU 算法,一般用于热点数据的查询,比如新闻信息,越是能被用户看得多的新闻,越有可能被别的用户所看到,对于那种基本没人访问的新闻,基本都类似存入大海!

在 Java 中,就有这么一个集合类实现了这个功能,它就是LinkedHashMap

二、LinkedHashMap 实现介绍

我们都知道,在java集合中,LinkedHashMap 继承自 HashMap,底层是一个双向链表的数据结构,与 HashMap 不同的是,LinkedHashMap 初始化阶段有个参数accessOrder ,默认是false

public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>{/**双向链表的头节点*/transient LinkedHashMap.Entry<K,V> head;/**双向链表的尾节点*/transient LinkedHashMap.Entry<K,V> tail;/*** 1、如果accessOrder为true的话,则会把访问过的元素放在链表后面,放置顺序是访问的顺序* 2、如果accessOrder为false的话,则按插入顺序来遍历*/final boolean accessOrder;
}

如果传入的是true,则会把最近访问过的元素放在链表后面,放置顺序是访问的顺序,测试如下:

public static void main(String[] args) {//accessOrder默认为falseMap<String, String> accessOrderFalse = new LinkedHashMap<>();accessOrderFalse.put("1","1");accessOrderFalse.put("2","2");accessOrderFalse.put("3","3");accessOrderFalse.put("4","4");System.out.println("acessOrderFalse:"+accessOrderFalse.toString());//accessOrder设置为trueMap<String, String> accessOrderTrue = new LinkedHashMap<>(16, 0.75f, true);accessOrderTrue.put("1","1");accessOrderTrue.put("2","2");accessOrderTrue.put("3","3");accessOrderTrue.put("4","4");accessOrderTrue.get("2");//获取键2accessOrderTrue.get("3");//获取键3System.out.println("accessOrderTrue:"+accessOrderTrue.toString());
}

输出结果如下:

acessOrderFalse:{1=1, 2=2, 3=3, 4=4}
accessOrderTrue:{1=1, 4=4, 2=2, 3=3}

可以得知,当我们将accessOrder设置为true的时候,经常被访问的元素会放入前面!

我们利用这个特性,使用 LinkedHashMap 来实现一个 LRU 缓存,操作如下:

  • 创建一个 LinkedHashMap 对象,将accessOrder设置为true
  • 设定 LinkedHashMap 的容量为n,超过这个值就删除多余的元素;
  • 重写 LinkedHashMap 中removeEldestEntry()方法;

其中removeEldestEntry()表示,如果返回的是true,就会移除最近不被使用的元素,如果返回false,不做任何操作,这个方法每次在add()的时候就会调用。

创建一个 LRU 缓存类,内容如下:

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {//创建一个容量为3的LinkedHashMapprivate static final int MAX_SIZE = 3;/*** 重写LinkedHashMap中removeEldestEntry方法* @param eldest* @return*/protected boolean removeEldestEntry(Map.Entry eldest) {//如果容器中的元素个数大于MAX_SIZE,在每次添加元素的时候,移除容器中最近不被使用的元素return size() > MAX_SIZE;}public LRULinkedHashMap() {//设置LinkedHashMap初始化容量,负载因子为0.75f,accessOrder设置为truesuper(MAX_SIZE, 0.75f, true);}
}

测试使用:

public static void main(String[] args) {LRULinkedHashMap<String,String> cache = new LRULinkedHashMap<String,String>();cache.put("1","a");cache.put("2","b");cache.put("3","c");System.out.println("初始cache内容:" + cache.toString());cache.get("2");System.out.println("查询key为2的元素之后,cache内容:" + cache.toString());cache.put("4","d");System.out.println("添加新的元素之后,cache内容:" + cache.toString());
}

输出结果如下:

初始cache内容:{1=a, 2=b, 3=c}
查询key为2的元素之后,cache内容:{1=a, 3=c, 2=b}
添加新的元素之后,cache内容:{3=c, 2=b, 4=d}

三、小结

在实际的业务开发过程中,LRU 算法应用比较广泛,比如热点排行榜,设置容量为3的时候,会将不常用的新闻移除,保留最新的热点信息。

写到最后

不会有人刷到这里还想白嫖吧?点赞对我真的非常重要!在线求赞。加个关注我会非常感激!

本文已整理到技术笔记中,此外,笔记内容还涵盖 Spring、Spring Boot/Cloud、Dubbo、JVM、集合、多线程、JPA、MyBatis、MySQL、微服务等技术栈。

需要的小伙伴可以点击 技术笔记 获取!

这篇关于集合系列(二十六) -利用LinkedHashMap实现一个LRU缓存的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1075863

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注,收藏不迷路💖 Kubernetes的PodSecurityPolicy(PSP)是一个关键的安全特性,它在Pod创建之前实施安全策略,确保P