集合系列(二十六) -利用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

相关文章

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

idea中创建新类时自动添加注释的实现

《idea中创建新类时自动添加注释的实现》在每次使用idea创建一个新类时,过了一段时间发现看不懂这个类是用来干嘛的,为了解决这个问题,我们可以设置在创建一个新类时自动添加注释,帮助我们理解这个类的用... 目录前言:详细操作:步骤一:点击上方的 文件(File),点击&nbmyHIgsp;设置(Setti

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

MySQL大表数据的分区与分库分表的实现

《MySQL大表数据的分区与分库分表的实现》数据库的分区和分库分表是两种常用的技术方案,本文主要介绍了MySQL大表数据的分区与分库分表的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有... 目录1. mysql大表数据的分区1.1 什么是分区?1.2 分区的类型1.3 分区的优点1.4 分