LRU算法详解及实现方法

  • LRU算法详解及实现方法已关闭评论
  • 5,420 views
  • A+
所属分类:IT技术

基本概念

LRU全称Least Recently Used,也就是最近最少使用的意思,是一种内存管理算法,最早应用与Linux操作系统。LRU算法基于一种假设:长期不被使用的数据,在未来被用到的几率也不大,因此,当数据所占内存达到一定阈值时,我们要移除掉最近最少被使用的数据。

算法原理

LRU算法详解及实现方法

  1. 最开始时,内存空间是空的,因此依次进入A、B、C是没有问题的
  2. 当加入D时,就出现了问题,内存空间不够了,因此根据LRU算法,内存空间中A待的时间最为久远,选择A,将其淘汰
  3. 当再次引用B时,内存空间中的B又处于活跃状态,而C则变成了内存空间中,近段时间最久未使用的
  4. 当再次向内存空间加入E时,这时内存空间又不足了,选择在内存空间中待的最久的C将其淘汰出内存,这时的内存空间存放的对象就是E->B->D

应用场景

CPU的高速缓存

LRU算法详解及实现方法

以目前最常见的L1、L2、L3为例:层数越往下,缓存越大,速度也越慢,cpu计算时经常要用到的数据会被从其他地方读到cache里。但cache的大小是有限的。当cpu想要读出一条cache里没有的数据时,势必需要淘汰一些存在cache里的数据来为新的数据腾出位置。这个时候按照什么原则去淘汰呢?一个很自然的想法就是:删掉那些cpu好久没用的数据吧!这就是LRU的策略

Android中显示大量图片

在你应用程序的UI界面加载一张图片是一件很简单的事情,但是当你需要在界面上加载一大堆图片的时候,情况就变得复杂起来。在很多情况下,(比如使用 ListView, GridView 或者 ViewPager 这样的组件),屏幕上显示的图片可以通过滑动屏幕等事件不断地增加,最终导致OOM。为 了保证内存的使用始终维持在一个合理的范围,通常会把被移除屏幕的图片进行回收处理。此时垃圾回收器也会认为你不再持有这些图片的引用,从而对这些图片进 行GC操作。用这种思路来解决问题是非常好的,可是为了能让程序快速运行,在界面上迅速地加载图片,你又必须要考虑到某些图片被回收之后,用户又将它重新滑入屏幕这种情况。这时,你可以使用LRU回收掉长时间不使用的图片,保留最近经常使用的图片,以此来维持图片内存在可控范围内。

技术基础

双向哈希链表与LRU

有一个查询用户信息的场景,用户信息当然是存在数据库里。但是由于我们对用户系统的性能要求比较高,显然不能每一次请求都去查询数据库。所以,我们在内存中创建了一个哈希表作为缓存,每次查找一个用户的时候先在哈希表中查询,以此提高访问性能。

LRU算法详解及实现方法

每次查询到的用户信息存入到哈希表中作为缓存,但这样做会存在一个问题:如果用户量很大,那么这个哈希表中的数据就会剧增,导致计算机内存不够用。采用LRU算法可以解决这样的问题。

我们都知道,哈希表是由若干个Key-Value所组成。在“逻辑”上,这些Key-Value是无所谓排列顺序的,谁先谁后都一样。

LRU算法详解及实现方法

在哈希链表当中,这些Key-Value不再是彼此无关的存在,而是被一个链条串了起来。每一个Key-Value都具有它的前驱Key-Value、后继Key-Value,就像双向链表中的节点一样。

LRU算法详解及实现方法

这样一来,原本无序的哈希表拥有了固定的排列顺序。

1.假设我们使用哈希链表来缓存用户信息,目前缓存了4个用户,这4个用户是按照时间顺序依次从链表右端插入的。

LRU算法详解及实现方法

2.此时,业务方访问用户5,由于哈希链表中没有用户5的数据,我们从数据库中读取出来,插入到缓存当中。这时候,链表中最右端是最新访问到的用户5,最左端是最近最少访问的用户1。

LRU算法详解及实现方法

3.接下来,业务方访问用户2,哈希链表中存在用户2的数据,我们怎么做呢?我们把用户2从它的前驱节点和后继节点之间移除,重新插入到链表最右端。这时候,链表中最右端变成了最新访问到的用户2,最左端仍然是最近最少访问的用户1。

LRU算法详解及实现方法 LRU算法详解及实现方法

4.接下来,业务方请求修改用户4的信息。同样道理,我们把用户4从原来的位置移动到链表最右侧,并把用户信息的值更新。这时候,链表中最右端是最新访问到的用户4,最左端仍然是最近最少访问的用户1。

LRU算法详解及实现方法 LRU算法详解及实现方法

5.后来业务方换口味了,访问用户6,用户6在缓存里没有,需要插入到哈希链表。假设这时候缓存容量已经达到上限,必须先删除最近最少访问的数据,那么位于哈希链表最左端的用户1就会被删除掉,然后再把用户6插入到最右端。

LRU算法详解及实现方法LRU算法详解及实现方法

Java中的LinkedHashMap对哈希双向链表做了很好的实现,我们可以直接利用LinkedHashMap做我们自己业务中的LRU算法。

LinkedHashMap原理及与HashMap的区别

在使用HashMap的时候,可能会遇到需要按照当时put的顺序来进行哈希表的遍历。HashMap中不存在保存顺序的机制。在LinkedHashMap中可以保持两种顺序,分别是插入顺序和访问顺序,这个是可以在LinkedHashMap的初始化方法中进行指定的。相对于访问顺序,按照插入顺序进行编排被使用到的场景更多一些,所以默认是按照插入顺序进行编排。如果将构造函数中的accessOrder参数设置为true,即表示按访问顺序排序(也就是LRU了)。LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。

LRU算法详解及实现方法

运行结果如下图所示,可以看到,输出的顺序与插入的顺序是一致的。

LRU算法详解及实现方法

在LinkedHashMap中,是通过双联表的结构来维护节点的顺序的。上文中的程序,实际上在内存中的情况如下图所示,每个节点都进行了双向的连接,维持插入的顺序(默认)。head指向第一个插入的节点,tail指向最后一个节点。

LRU算法详解及实现方法

LinkedHashMap是HashMap的亲儿子,直接继承HashMap类。LinkedHashMap中的节点元素为Entry<K,V>,直接继承HashMap.Node<K,V>。UML类图关系如下:

LRU算法详解及实现方法

可以看出,LinkedHashMap比HashMap的Entry多出after和before属性,这两属性就是用于标识前后节点的。

实现代码

继承Java的LinkedHashMap,设定一个哈希表存储的最大数量maxSize,如果插入元素超过该最大值,则会执行移除不常用元素的操作;重载removeEldestEntry方法,该方法用于判断移除元素的时机。记住,调用父类的构造方法中,将accessOrder参数设置为true,表示考虑按使用先后顺序排序各个元素。

LRU算法详解及实现方法

阿拉灯aladeng