LRU缓存介绍与实现 (Java)

最新推荐文章于 2024-04-23 18:52:22 发布
VIP文章 最新推荐文章于 2024-04-23 18:52:22 发布
阅读量5.3w 收藏 99
点赞数 9
分类专栏： 算法 (Algorithm) 文章标签： java cache inheritance import class string
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/beiyeqingteng/article/details/7010411
版权

引子：

我们平时总会有一个电话本记录所有朋友的电话，但是，如果有朋友经常联系，那些朋友的电话号码不用翻电话本我们也能记住，但是，如果长时间没有联系了，要再次联系那位朋友的时候，我们又不得不求助电话本，但是，通过电话本查找还是很费时间的。但是，我们大脑能够记住的东西是一定的，我们只能记住自己最熟悉的，而长时间不熟悉的自然就忘记了。

其实，计算机也用到了同样的一个概念，我们用缓存来存放以前读取的数据，而不是直接丢掉，这样，再次读取的时候，可以直接在缓存里面取，而不用再重新查找一遍，这样系统的反应能力会有很大提高。但是，当我们读取的个数特别大的时候，我们不可能把所有已经读取的数据都放在缓存里，毕竟内存大小是一定的，我们一般把最近常读取的放在缓存里（相当于我们把最近联系的朋友的姓名和电话放在大脑里一样）。现在，我们就来研究这样一种缓存机制。

LRU缓存：

LRU缓存利用了这样的一种思想。LRU是Least Recently Used 的缩写，翻译过来就是“最近最少使用”，也就是说，LRU缓存把最近最少使用的数据移除，让给最新读取的数据。而往往最常读取的，也是读取次数最多的，所以，利用LRU缓存，我们能够提高系统的performance.

实现：

要实现LRU缓存，我们首先要用到一个类 LinkedHashMap。 用这个类有两大好处：一是它本身已经实现了按照访问顺序的存储，也就是说，最近读取的会放在最前面，最最不常读取的会放在最后（当然，它也可以实现按照插入顺序存储）。第二，LinkedHashMap本身有一个方法用于判断是否需要移除最不常读取的数，但是，原始方法默认不需要移除（这是，LinkedHashMap相当于一个linkedlist），所以，我们需要override这样一个方法，使得当缓存里存放的数据个数超过规定个数后，就把最不常用的移除掉。LinkedHashMap的API写得很清楚，推荐大家可以先读一下。

要基于LinkedHashMap来实现LRU缓存，我们可以选择inheritance, 也可以选择 delegation， 我更喜欢delegation。基于delegation的实现已经有人写出来了，而且写得很漂亮，我就不班门弄斧了。代码如下：

import java.util.LinkedHashMap;
import java.util.Collection;
import java.util.Map;
import java.util.ArrayList;

/**
* An LRU cache, based on <code&g
最低0.47元/天 解锁文章
beiyeqingteng
关注
  • 9
    点赞
  • 踩
  • 99
    收藏
    觉得还不错? 一键收藏
  • 9
    评论
专栏目录
详解Java实现LRU缓存
08-18
主要介绍了详解Java实现LRU缓存，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
LRU缓存
weixin_43624024的博客
10-16 2860
一、什么是LRU算法 LRU，Least Recently Used算法，即一种缓存淘汰策略。 计算机的缓存容量有限，若缓存满了则需要删除一些内容，给新的缓存腾出空间，但问题是要删除哪些内容呢？当然是把用的少的缓存删掉，把最有用的数据继续保留以便于继续使用。那么如何判定哪些数据是有用的呢？ 缓存淘汰的策略有很多，而LRU则是一种较为简单常用的算法，LRU判定最近使用过的数据为有用的，很久都没...
一篇搞懂什么是LRU缓存｜一篇搞懂LRU缓存的实现｜LRUCache详解和实现
后端开发为主+人工智能
03-09 1550
一篇搞懂LRU缓存的原理
LRU算法java实现课程设计大作业
12-09
理解LRU或CLOCK改进算法等置换算法； 设计与算法相关的数据结构，如：LRU的堆栈或CLOCK改进算法中的循环结构； 按照最多5块的内存分配情况，编程实现所选算法，动态输入访问内存的块号序列，输出置换结果； 测试：输入合法、非法的访问序列数据，检查程序的正确性和健壮性。
C++实现LRU算法（LeetCode 146 LRU缓存机制）
暮色年华的博客
11-24 1670
LRU算法： LRU算法（Least Recently Used）是一种缓存淘汰策略，最近使用的数据是有用的， 如果缓存满了，删除最久没用过的数据 LRU算法描述： （1）设置缓存大小 （2）get：在缓存中根据key索引value，如果缓存中没有，返回-1 （3）put：如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。 class LRUCache { public
LRU (最近最少使用) 缓存实现的两种方式
weixin_51935690的博客
03-29 1410
题目如下 LRU最近最少使用，是一种常用的页面置换算法，在容量一定的情况下，删除内存中最近最久未使用的数据。 首先第一种方式：Map 利用在Map当中键值的方式进行存储数据，它的特性就是我们新加入set进去的键值对在其内部是有顺序排列的，及我们set一个键值对它就会去放在后面，这时如果我们容量已满，那么只需要删除掉第一个键值即可（因为常使用（把他移到后方）的和新进入的都会在后方添加进去），然后就实现了一个LRU算法 具体解释都已在代码详细注释 // 第一种方式Map方式 // Map中set加入的键值对是
实现 LRU 缓存算法
cr7258的博客
05-18 4105
1 LRU 缓存介绍 LRU 算法全称是最近最少使用算法（Least Recently Use），是一种简单的缓存策略。顾名思义，LRU 算法会选出最近最少使用的数据进行淘汰。 那么什么是缓存呢？缓存专业点可以叫一种提高数据读取性能的技术，可以有效解决存储器性能和容量的矛盾，是一种空间换时间的设计思想，比如我们常见的内存是硬盘的缓存，Cache 是内存的缓存，浏览器本地存储是网络访问的缓存...... LRU 有许多应用场景，例如： 操作系统底层的内存管理。 缓存服务，例如 Redis，当数据满的时候就要
【常见缓存算法原理及其C++实现】LRU篇（包含过期时间详解）
saxon_li的博客
04-05 6349
一、缓存算法简介 （一）缓存算法应用背景 缓存的应用场景和范围十分广泛，下面给出其十分常见的两种应用背景： 首先，在操作系统内部，由于内存资源十分有限，而每个进程又都希望独享一块很大的内存空间。所以诞生了一种“虚拟内存”机制，它将进程的一部分内容暂留在磁盘中，在需要时再进行数据交换将其放入内存，这个过程就需要用到缓存算法机制进行置换。 其次，对于各类应用项目开发而言，在巨大的数据量面前，Catch 是不可或缺的。因为无论是针对本地端的浏览器缓存，还...
LeetCode 146：LRU 缓存
机械工程跑路哥
07-20 850
因为在删除节点时，使用removeFirst()删除链表头部也就是最长时间未使用的节点，然后需要再根据该方法返回的这个节点的key，去删除hashmap中对应的键值对；而事实上，在一个时间段内，只需要访问一小部分数据即可正常运行，这就导致内存中驻留了大量用不到的数据；因为删除链表时，双向链表的前驱操作可以保证时间复杂度为O(1)，而单向链表的删除要从头遍历直到找到节点，时间复杂度为O(n)；LRU的全称是LeastRecentlyUsed，也就是说我们认为最近使用过的数据应该是是「有用的」，........
LRU缓存机制
技术分享博客
09-07 1061
计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。那么，什么样的数据，我们判定为「有用的」的数据呢？LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。常见的场景如手机的后台运行缓存，我们依次打开了[王者荣耀] [淘宝] [微信] [抖音]，假设手机只允许同时打开个应用程序，那么在我们打开抖音的那一刻，就会将最久未使用的 [王者荣耀] 关闭，腾出空间给 抖音。
Java实现简单LRU缓存机制的方法
08-19
主要介绍了Java实现简单LRU缓存机制的方法,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
Java实现简单LRU缓存算法
05-20
这里的LRUCache类维护了一个双向链表和一个哈希表，用于实现LRU算法。具体实现细节如下： - get方法：首先在哈希表中查找对应的键值对，如果不存在，则返回-1；如果存在，则将对应的节点从双向链表中删除，并将其...
Java实现LRU缓存的实例详解
08-29
主要介绍了Java实现LRU缓存的实例详解的相关资料,这里提供实例帮助大家理解掌握这部分内容，需要的朋友可以参考下
Java和Android的Lru缓存及其实现原理
01-20
　Android提供了LRUCache类，可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap，可以用该类很方便的实现LRU算法，Java的LRULinkedHashMap是直接继承了LinkedHashMap，进行了极少的改动后可以实现LRU...
mybatisPlus使用MetaObjectHandler对字段进行更新
最新发布
m0_56356631的博客
04-23 233
都是符合我们的预期的。
string模拟实现
m0_73969414的博客
04-23 1339
c++中string的模拟实现，面试必会知识点
实现自定义注解、实现自定义幂等性注解
qq_44721738的博客
04-23 482
添加 Spring AOP 依赖。创建自定义注解。创建一个新的 Java 注解类，通过@interface关键字来定义，并可以添加元注解以及属性。@Target(ElementType.METHOD) //表示作用于方法上@Retention(RetentionPolicy.RUNTIME) // 表示这个注解在运行时是可见的，这样 AOP 代理才能在运行时读取到这个注解编写 AOP 拦截（自定义注解）的逻辑代码。@Aspect@Component// 方法执行前的处理。
javaweb-SpringBoot基础
kussm_的博客
04-20 1253
Spring的官网(Spring的简介：Spring makes Java simple。Spring Boot 可以帮助我们非常快速的构建应用程序、简化开发、提高效率。创建一个子包controller。
Java如何实现LRU缓存淘汰算法
06-07
Java实现LRU缓存淘汰算法的方法与Python类似，也可以使用哈希表和双向链表来实现。下面是一个Java实现的LRU缓存淘汰算法的代码示例： ```java class LRUCache { private Map<Integer, Node> map; private int capacity; private Node head; private Node tail; public LRUCache(int capacity) { this.capacity = capacity; map = new HashMap<>(); head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; } public int get(int key) { if (map.containsKey(key)) { Node node = map.get(key); remove(node); add(node); return node.value; } else { return -1; } } public void put(int key, int value) { if (map.containsKey(key)) { Node node = map.get(key); node.value = value; remove(node); add(node); } else { if (map.size() == capacity) { Node node = tail.prev; remove(node); map.remove(node.key); } Node node = new Node(key, value); map.put(key, node); add(node); } } private void add(Node node) { Node next = head.next; head.next = node; node.prev = head; node.next = next; next.prev = node; } private void remove(Node node) { Node prev = node.prev; Node next = node.next; prev.next = next; next.prev = prev; } private class Node { int key; int value; Node prev; Node next; public Node(int key, int value) { this.key = key; this.value = value; } } } ``` 在这个实现中，我们同样使用了一个哈希表来查询节点是否存在以及快速删除节点，使用一个双向链表来维护缓存中节点的顺序。当有新的节点被访问时，我们将其移到链表头部，并且当缓存空间不足时，我们淘汰链表尾部的节点。同时，我们使用了一个Node内部类来封装节点的key和value，以及前驱和后继节点的指针。

“相关推荐”对你有帮助么？

  • 非常没帮助
  • 没帮助
  • 一般
  • 有帮助
  • 非常有帮助
提交
评论 9
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值