前言
LRU是Least Recently Used的缩写，即最近最少使用，当超过容量时，自动删除最近最少使用的项目。
LRU在android开发中最常见的就是图片加载框架中的缓存逻辑。在java中可以利用LinkedListMap很方便的实现LRU，如下
class LRUCache extends LinkedHashMap<Integer, Integer> { //LinkedHashMap实现了按访问排序和移除最近最少，但是默认是不使用的，需要我们改造一下 private int capacity; public LRUCache(int capacity) { //这里的第三个参数true就是使用访问排序，这样每次访问都是更新链表 //注意，这里的第一个参数是map的初始大小，并不是限定容量 super(capacity, 0.75F, true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { //这个函数默认返回false，如果不重写这个方法，永远不会进行清除 //所以这里要重写一下，判断是否进行清除。 return size() > capacity; } } 复制代码
那么这其中的原理是什么呢？
原理
首先就是LinkedHashMap，它与HashMap的区别就是在Map的结构外还有一个链表结构，Map的每个key-value都会以Node的形式同时存储在Map和链表中。
当put一个key和value时，加入Map的同时，也加入链表尾部，这样实现了有序（HashMap本来是无序的）。
这里就不展开说了，简单知道有这个链表就可以了，正是这个链表完成了LRU的实现。
简单来说就是get（使用了）的时候将该Node从链表中移除，并添加到链表尾部。
put的时候，检查Map的容量，如果超出了，就从移除链表头部Node（时间最久的，即最近最少使用），同时从map中移除。
那么代码中是如何实现的？
先看get函数，这个函数LinkedHashMap进行了重写：
public V get(Object var1) { Node var2; if ((var2 = this.getNode(hash(var1), var1)) == null) { return null; } else { if (this.accessOrder) { this.afterNodeAccess(var2); } return var2.value; } } public V getOrDefault(Object var1, V var2) { Node var3; if ((var3 = this.getNode(hash(var1), var1)) == null) { return var2; } else { if (this.accessOrder) { this.afterNodeAccess(var3); } return var3.value; } } 复制代码
可以看到有这么一段代码：
if (this.accessOrder) { this.afterNodeAccess(var3); } 复制代码
这里的accessOrder就是LinkedHashMap的三参数构造函数super(capacity, 0.75F, true)中的第三个参数，是否使用访问排序。
默认是false，如果为ture就使用访问排序，这时候get函数就会调用afterNodeAccess，这个函数是HashMap的，但是在HashMap中是个空函数，没有任何实现：
void afterNodeAccess(HashMap.Node<K, V> var1) { } 复制代码
所以如果使用HashMap，这个访问排序就没有什么意义。但是在LinkedHashMap中对这个函数进行了重写：
void afterNodeAccess(Node<K, V> var1) { LinkedHashMap.Entry var2; if (this.accessOrder && (var2 = this.tail) != var1) { LinkedHashMap.Entry var3 = (LinkedHashMap.Entry)var1; LinkedHashMap.Entry var4 = var3.before; LinkedHashMap.Entry var5 = var3.after; var3.after = null; if (var4 == null) { this.head = var5; } else { var4.after = var5; } if (var5 != null) { var5.before = var4; } else { var2 = var4; } if (var2 == null) { this.head = var3; } else { var3.before = var2; var2.after = var3; } this.tail = var3; ++this.modCount; } } 复制代码
简单来说就是将get函数访问的这个Node从链表中移除，添加到结尾。 所以可以看到，如果想实现LRU，accessOrder就必须为true，否则无效。
自动清理
这样实现了访问排序，那么如何实现的自动清理呢？
我们来看看put函数，put函数LinkedHashMap没有重写，所以在它的父类HashMap中：
public V put(K var1, V var2) { return this.putVal(hash(var1), var1, var2, false, true); } final V putVal(int var1, K var2, V var3, boolean var4, boolean var5) { HashMap.Node[] var6; int var8; if ((var6 = this.table) == null || (var8 = var6.length) == 0) { var8 = (var6 = this.resize()).length; } Object var7; int var9; if ((var7 = var6[var9 = var8 - 1 & var1]) == null) { var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null); } else { ... if (var10 != null) { Object var13 = ((HashMap.Node)var10).value; if (!var4 || var13 == null) { ((HashMap.Node)var10).value = var3; } this.afterNodeAccess((HashMap.Node)var10); return var13; } } ++this.modCount; if (++this.size > this.threshold) { this.resize(); } this.afterNodeInsertion(var5); return null; } 复制代码
这里重点关注链表的逻辑，可以看到如果Map中不存在这个key，就新建一个
if ((var7 = var6[var9 = var8 - 1 & var1]) == null) { var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null); } else { 复制代码
但是如果存在，除了重新赋值之外，还执行了afterNodeAccess，将它移到了链表尾部。
if (var10 != null) { ... this.afterNodeAccess((HashMap.Node)var10); return var13; } 复制代码
因为重新赋值就是访问了该元素，所以需要重新排序。
那么这里受不受accessOrder的控制，因为accessOrder是LinkedHashMap的一个变量，而put是HashMap实现的，所以在put的代码中并没有判断accessOrder。但是在上面afterNodeAccess函数的源码中可以看到一开始就判断了accessOrder，所以这里也是受accessOrder的控制的。这也是为什么在get函数中判断了accessOrder，在afterNodeAccess又一次判断的原因。
最后还执行了afterNodeInsertion，这个函数与afterNodeAccess一样，在HashMap中是空函数，没有任何代码。在LinkedHashMap实现了，如下：
void afterNodeInsertion(boolean var1) { LinkedHashMap.Entry var2; if (var1 && (var2 = this.head) != null && this.removeEldestEntry(var2)) { Object var3 = var2.key; this.removeNode(hash(var3), var3, (Object)null, false, true); } } 复制代码
可以看到这个函数实现了移除Map中的元素，这样就实现了清理。但是并不是每次都清理，所以需要removeEldestEntry判断。
这个函数是LinkedHashMap的函数，但是在LinkedHashMap中这个函数也是一个空函数，默认返回false
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> var1) { return false; } 复制代码
所以永远不会清理，这也是我们为什么一定要重写这个函数的原因。通过我们上面的重写，当Map容量大于我们规定的上限时就返回true，这样就执行了清理。
@Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { //这个函数默认返回false，如果不重写这个方法，永远不会进行清除 //所以这里要重写一下，判断是否进行清除。 return size() > capacity; } 复制代码
总结
所以要用LinkedHashMap实现LRU，有两个非常重要的点：
- 1、accessOrder必须为true。否则链表不会重排。
注意：如果为false，还是可以清理的（下面会说到），这时候如果清理实际上就是清理存入最久的，也就相当于一个普通的队列。
- 2、必须重写removeEldestEntry。否则永远不会清理。
那么上面提到的一个问题，清理是否受accessOrder影响？是不是accessOrder为false就不清理了？
答案是不影响，重排和清理是互不影响的，在afterNodeInsertion的整个流程中没有accessOrder的出现。
所以上面提到了，如果accessOrder为false也可以清理，只不过清理的是存入最久的（忽略访问），并不是LRU算法。
