Java实现简单LRU缓存机制的方法
一、什么是 LRU 算法
就是一种缓存淘汰策略。
计算机的缓存容量有限,如果缓存满了就要删除一些内容,给新内容腾位置。但问题是,删除哪些内容呢?我们肯定希望删掉哪些没什么用的缓存,而把有用的数据继续留在缓存里,方便之后继续使用。
LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。
二、LRU的使用
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废
第一步:创建一个长度为2的LRUCache
第二步:cache.put(1, 1);放入key=1,value=1的数据
第三步:cache.put(2,2);放入key = 2,value = 2的数据
(因为2刚使用,所有把2移动到前面)
第四步:cache.get(1);获取key = 1的数据
(因为我们刚使用了1,所以把1移动到前面)
第五步:cache.put(3,3);放入key = 3,value = 3的数据
(因为3刚放进,所以放前面,又因为容量只有2,需要移除原先的1个。只因key = 2是最近最少使用的(key = 1刚get()过),所以移除2。
三、LRU的实现机制
算法:
LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
1)双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。
2)哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。
一、初始化:
二、cache.put(1,1):
三、cache.put(2,2):
四、cache.get(1):
五、cache.put(3,3):
四、代码如下
import java.io.*; import java.util.HashMap; public class test { public static void main(String args[]) throws IOException { LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4 } } /** * 设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put */ class LRUCache { private HashMap<Integer,LinkedNode> cache = new HashMap();//方便通过key快速定位结点 private int size; private int capacity; private LinkedNode head,tail; class LinkedNode{ int key; int value; LinkedNode pre; LinkedNode next; } public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; head = new LinkedNode(); tail = new LinkedNode(); head.next = tail; tail.pre = head; } /** * 移除节点 * @param node */ private void removeNode(LinkedNode node) { LinkedNode preNode = node.pre; LinkedNode nextNode = node.next; preNode.next = nextNode; nextNode.pre = preNode; } /** * 添加节点到头部 * @param node */ private void addNode(LinkedNode node) { node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; } /** * 将节点移动到头部 * @param node */ private void moveToHead(LinkedNode node) { removeNode(node); addNode(node); } /** * 获取数据 * @param key * @return */ public int get(int key) { LinkedNode node = cache.get(key); if(node != null) { moveToHead(node); }else{ return -1; } return node.value; } /** * 写入数据 * @param key * @param value */ public void put(int key, int value) { LinkedNode node = cache.get(key); //存在 if(node != null) { node.value = value;//可能更新数据 moveToHead(node); } //不存在 else{ LinkedNode newNode = new LinkedNode(); newNode.key = key; newNode.value = value; cache.put(key,newNode);//更新Map addNode(newNode);//添加结点到头部 size++;//更新结点数 if(size > capacity) {//如果结点数超过容量大小 LinkedNode tailPre = tail.pre; cache.remove(tailPre.key);//更新Map removeNode(tailPre);//删除最后一个结点(尾结点的前一个结点) size--; } } } }
总结:自己实现的简单LRU总归太简单了,要是想完善或者实现更真实的LRU,不妨参考一下Redis中的LRU。(◔◡◔)
到此这篇关于Java实现简单LRU缓存机制的方法的文章就介绍到这了,更多相关Java LRU缓存内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了IDEA中的clean,清除项目缓存图文教程,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-09-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20