LRU算法，即least recently used ，最近最少使用，LRU算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
LRU算法通常用于缓存的淘汰策略实现，由于缓存的内存非常宝贵，所以需要根据某种规则来剔除数据保证内存不被撑满。
我们下面来介绍一种最简单的实现LRU的方法。
代码实现
最简单的实现方式就是使用LinkedHashMap
public class LRUCache<K,V> extends LinkedHashMap<K,V> {
private final int CACHE_SIZE;
public LRUCache(int cacheSize) {
//true 表示让 LinkedHashMap 按照访问顺序来进行排序，最近访问的放在头部，最老访问的放在尾部
super((int) (Math.ceil(cacheSize/0.75)+1),0.75f,true);
CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
// 当 map 中的数据量大于指定的缓存个数的时候，就自动删除最老的数据。
return size() > CACHE_SIZE;
}
}
全部代码如上所示，非常的简洁，不超过10行。
其中有几个点
- 初始化时，LinkedHashMap的accessOrder参数需要设置成true,表示map元素按照访问顺序进行排序，false表示按照插入顺序进行排序。
2.需要重写removeEldestEntry()方法。
演示效果
我们来演示一下上面的LRU实现，看看能不能达到我们实现LRU的目的。
首先来看一下缓存超出容量最大值的情况
public class LRUCache<K,V> extends LinkedHashMap<K,V> {
private final int CACHE_SIZE;
public LRUCache(int cacheSize) {
//true 表示让 LinkedHashMap 按照访问顺序来进行排序，最近访问的放在头部，最老访问的放在尾部
super((int) (Math.ceil(cacheSize/0.75)+1),0.75f,true);
CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > CACHE_SIZE;
}
public static void main(String[] args) {
//设置最多缓存3条数据
LRUCache<String, Integer> lruCache = new LRUCache<>(3);
lruCache.put("1",1);
lruCache.put("2",2);
lruCache.put("3",3);
for (Map.Entry<String,Integer> e :lruCache.entrySet()) {
System.out.println(e.getKey()+" : "+e.getValue()+"\t");
}
System.out.println(" ");
//缓存满，插入底条数据
lruCache.put("4",4);
for (Map.Entry<String,Integer> e :lruCache.entrySet()) {
System.out.println(e.getKey()+" : "+e.getValue()+"\t");
}
}
}
//输出结果，缓存未超过最大容量时，输出顺序如下所示，缓存超过最大容量，删除一条数据
1 : 1
2 : 2
3 : 3
2 : 2
3 : 3
4 : 4
从上面的代码看实现了我们在缓存容量超出阈值时删除数据的情况。
下面我们再来看一下访问元素之后，map中元素的排序情况。
public static void main(String[] args) {
LRUCache<String, Integer> lruCache = new LRUCache<>(3);
lruCache.put("1",1);
lruCache.put("2",2);
lruCache.put("3",3);
for (Map.Entry<String,Integer> e :lruCache.entrySet()) {
System.out.println(e.getKey()+" : "+e.getValue()+"\t");
}
System.out.println(" ");
//lruCache.put("4",4);
lruCache.get("1");
for (Map.Entry<String,Integer> e :lruCache.entrySet()) {
System.out.println(e.getKey()+" : "+e.getValue()+"\t");
}
}
//输出
1 : 1
2 : 2
3 : 3
2 : 2
3 : 3
1 : 1
我们访问了key 1，然后map里的元素顺序就调整了。
原理分析
上面我们利用LinkedHashMap简单实现了一下LRU，其中有2个注意点.
一个是LinkedHashMap构造函数中有一个accessOrder要设置成true，表示按照访问顺序排序。看一下LinkedHashMap中这个成员变量的定义。
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;
另一个是要重写removeEldestEntry()方法，自定义缓存超出容量的删除策略，我们在上面的实现中判断map.size()是否大于CACHE_SIZE，即map中元素的个数是否超过我们定义的缓存个数最大值，如果比较结果为true,则删除元素，如果为false，则不删除元素。
我们自己实现LRU的时候只需要实现2个条件即可。
源码解析
LinkedHashMap内部维护了一个双向链表，通过accessOrder控制。
元素访问
我们从get方法往里看源码是如何实现的，下面的代码基于jdk1.8。
public V get(Object key) {
Node<K,V> e;
//根据key取hash定位node，如果查不到就返回null
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果accessOrder为true
if (accessOrder)
//执行此方法
afterNodeAccess(e);
return e.value;
}
LinkedHashMap的get方法也不难，key经过hash查找node，查不到直接返回null,如果查的到，判断是否为accessOrder，然后执行afterNodeAccess方法。
看这个方法之前，我们先来看2个成员变量,根据注释，我们可以看到head存放的是最老的数据，tail存放的是最新的数据
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
我们来看一下afterNodeAccess这个方法，第一行的注释即表明要将传入的node放到最后
void afterNodeAccess(Node<K,V> e) { // move node to last
//先定义一个临时变量last
LinkedHashMap.Entry<K,V> last;
//如果accessOrder=true &&访问的node e不是尾节点
if (accessOrder && (last = tail) != e) {
//将e赋值给变量p,b是p的前驱节点，a是p的后继节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
//将p赋值给tail
tail = p;
++modCount;
}
}
我们插入的时候，head=("1",1),tail=("3",3),现在get方法访问key=1的node,if条件为true，进入到if语句里面
image.png
往下走一步，p=("1",1)，a=("2",2),b=null
image.png
这样继续往下走，head =a，即head=("2",2)
a!=null，a.before=null
image.png
下面就到了我们最后一个判断了，p=("1",1)，last=("3",3),则last跑到了p的前面
last.after=p，就建立了双向联系
image.png
最后一步，将p赋值给tail，则("1",1)就移动到了尾端，("2",2)变成了head，通过一系列赋值操作，将我们访问的node ("1",1)移动到了队尾，以前队头的after节点即("2",2)变成了新的队头。
以后删除的时候就先删除head元素即可。
元素插入
我们来看一下堆栈
image.png
- lruCache.put方法入口
- 直接向hashmap里插入元素
- 调用LinkedHashMap的回调函数，在插入node之后判断是否需要删除元素
- 最终会调用到我们重写的removeEldestEntry方法，判断是否要进行元素删除。
总结
LinkedHashMap和HashMap相结合，封装了大量的细节，最终开发者只需要注意2个细节就可以轻松的实现自己的LRU算法了。如果感兴趣的也可以自己手撸一遍LRU算法，加深自己的理解。
参考文章
LinkedHashMap实现LRU
动手实现一个LRU cache
欢迎扫描下方的二维码关注我的个人公众号：站在海边看远方
image.png
网友评论