一、写随笔的原因：最近准备去朋友公司面试，他说让我看一下LRU算法，就此整理一下，方便以后的复习。
二、具体的内容：
1.简介：
LRU是Least Recently Used的缩写，即最近最少使用。算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小”。
这里不得不说i一下LFU（Least Frequently Used），其核心思想是“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”
LRU和LFU算法的区别是概括来说，LRU强调的是访问时间，而LFU则强调的是访问次数。
2.使用场景：
一般来说它是用来作为一种缓存淘汰算法。
3.实现方法：
方法一：用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。该方法有个致命的缺点就是需要不停地维护数据项的访问时间戳，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。
方法二：可以使用链表来实现，分三步走：首先当新数据插入的时候，依次按顺序放到链表中； 其次查询数据时，已经存在链表中时（即缓存数据被访问），则将数据移到链表尾部；当链表满的时候，将链表顶部的数据丢弃。
4.Java中的实现代码：
Java中最简单的LRU算法实现，就是利用LinkedHashMap，覆写其中的removeEldestEntry(Map.Entry)方法即可，内部就是使用的方法二实现的。代码如下：
import java.util.LinkedHashMap; import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUTest { static class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> {
//定义缓存的容量
private int capacity;
//带参数的构造器
LRULinkedHashMap(int capacity){
//如果accessOrder为true的话，则会把访问过的元素放在链表后面，放置顺序是访问的顺序(LinkedHashMap里面的get方法，当accessOrder为true，会走afterNodeAccess方法将节点移到最后)
//如果accessOrder为flase的话，则按插入顺序来遍历
super(16,0.75f,true);
//传入指定的缓存最大容量
this.capacity=capacity;
}
//实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
return size()>capacity;
}
}
//test
public static void main(String[] args) {
LRULinkedHashMap<String, Integer> testCache = new LRULinkedHashMap<>(3);
testCache.put("A", 1);
testCache.put("B", 2);
testCache.put("C", 3);
System.out.println(testCache.get("B"));
System.out.println(testCache.get("A"));
testCache.put("D", 4);
System.out.println(testCache.get("D"));
System.out.println(testCache.get("C"));
}
}
输出结果：
为何上述简单的代码LRU算法，具体要看LinkedHashMap里的put和get方法的源代码。
1.首先是put（）方法，这个在LinkedHashMap并没有重写，直接使用的是HashMap中的put()方法，这里解释一下上面的重写的removeEldestEntry（）方法，在上次HashMap原理探究中，put()方法会调用内部的putVal（）方法，putVal（）方法中最后会调用一个afterNodeInsertion(evict);这个方法在LinkedHashMap里面有实现：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first; //头结点
if (evict && (first = head) != null && removeEldestEntry(first)) { //会调用我们重写的removeEldestEntry（）
K key = first.key;
removeNode(hash(key), key, null, false, true); // 满足条件，这移除头结点
}
}
会调用我们重写的removeEldestEntry（）方法，当返回为true时，则会removeNode（）方法移除链表的顶端元素，满足方法二中的第三个步骤。
2.接下来看一下get()方法，这个在LinkedHashMap有重写，代码如下：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
这里会用到我们初始化时设置的accessOrder的值，我们当时设置的是ture，也就意味着会调用afterNodeAccess（）方法，我们继续看afterNodeAccess的源码：
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
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;
}
tail = p;
++modCount;
}
}
源码中有块英文注释// move node to last，很明显是将查到的数据移动到链表的尾部。满足方法二中的第二个步骤。
至于方法二中的第一个步骤，LinkedHashMap本身就是有顺序的插入，顺带分析下为啥它是如何实现有顺序插入的。由于它并没有单独实现put()方法，所以要看HashMap中的put()实现，还是参照上次HashMap原理探究 ，在put()方法会调用内部的putVal（）方法，putVal（）方法中添加新节点会调用newNode（）方法，而LinkedHashMap对newNode进行了重写，代码如下：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p); // 这个方法就是将新节点顺序的插入到为节点的后面
return p;
}
linkNodeLast（）方法：
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
三、总结：
本篇随笔主要就是LRU的介绍和在java中的快速实现，实现的代码相信网上非常的多，主要还是从源码角度分析了为何可以这样简单的实现，让我们能够更加理解LRU的基于链表的实现吧，同时也分析了下LinkedHashMap的部分源码实现，让大家能够更深入的理解吧。