您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

LRU算法详解及最简单的Java实现

时间:2019-08-03 17:48:41  来源:  作者:

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

LRU算法的表现

  1. 新数据插入到容器头部;
  2. 每当缓存命中(即缓存数据被访问),则将数据移到容器头部;
  3. 当容器满的时候,将容器尾部的数据丢弃。

实现LRU的方法

  1. 用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中所有的数据项的时间戳自增,并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项的时间戳置为0。当数组空间已满时,将时间戳最大的数据项淘汰。
  2. 利用一个链表来实现,每次新插入数据的时候将新数据插到链表的头部;每次缓存命中(即数据被访问),则将数据移到链表头部;那么当链表满的时候,就将链表尾部的数据丢弃。
  3. 利用链表和HashMap。当需要插入新的数据项的时候,如果新数据项在链表中存在(一般称为命中),则把该节点移到链表头部,如果不存在,则新建一个节点,放到链表头部,若缓存满了,则把链表最后一个节点删除即可。在访问数据的时候,如果数据项在链表中存在,则把该节点移到链表头部,否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。HashMap提供快速定位功能,具体可以参见下文。

比较三种方法优劣:

对于第一种方法,需要不停地维护数据项的访问时间戳,另外,在插入数据、删除数据以及访问数据时,时间复杂度都是O(n)。对于第二种方法,链表在定位数据的时候时间复杂度为O(n)。所以在一般使用第三种方式来是实现LRU算法。

LinkedHashMap的实现方案

LinkedHashMap继承于HashMap,来一张LinkedHashMap的结构图

 

LRU算法详解及最简单的Java实现

 

 

LinkedHashMap的结构图

其中next是用于维护HashMap指定table位置上连接的Entry的顺序的,before、after是用于维护Entry插入的先后顺序的

LinkedHashMap底层就是用的HashMap加双链表实现的。实现LRU算法主要有两个注意的地方:

  1. LinkedHashMap本身已经实现了按照访问顺序的存储。LinkedHashMap的构造函数中有一个accessOrder参数,平时使用LinkedHashMap一般该值为false。不过在LRU算法实现中我们要设置该参数为true,当构造函数中为true时,我们每次调用get方法时都会调用该方法,将我们访问的Node移动到最后,使之成为尾部节点,从而改变了数据在LinkedHashMap中的存储顺序。
  2. LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数,方法默认是直接返回false,不会移除元素,所以需要重写该方法。即当缓存满后就移除最不常用的数。

所以使用LinkedHashMap很简单的实现了LRU算法,代码如下。另外如果生产中使用的话,一定要记得线程安全加锁。

class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> {
 // 定义缓存的容量
 private int capacity;
 // 带参数的构造器
 LRULinkedHashMap(int capacity){
 // 第三个参数为accessOrder
 super(16,0.75f,true);
 // 传入指定的缓存最大容量
 this.capacity=capacity;
 }
 // 实现LRU的关键方法,如果map里面的元素个数大于了缓存最大容量,则删除链表的顶端元素
 @Override
 public boolean removeEldestEntry(Map.Entry<K, V> eldest){
 return size()>capacity;
 }
 }

更多内容,欢迎关注微信公众号:全菜工程师小辉~



Tags:LRU算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1 什么是LRULRU(Least recently used)最近最少使用,它的核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。因此 LRU 算法会根据数据的历史访问记录来进行排序,如...【详细内容】
2020-11-09  Tags: LRU算法  点击:(139)  评论:(0)  加入收藏
LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。...【详细内容】
2020-07-07  Tags: LRU算法  点击:(66)  评论:(0)  加入收藏
LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。LRU算法的表现 新数据插...【详细内容】
2019-08-03  Tags: LRU算法  点击:(287)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条