1.LRU 是一种算法。
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的算法。
用通俗易懂的说法来解释可以参考这篇：
https://juejin.cn/post/7073244330537779207
假设我是一个卖玩具的商人，我在街上租了一个只能放下三个玩具（没办法太穷了）的摊位，所以大部分的玩具都没摆出来而是放在仓库里。
image.png
好家伙，终于有个人来问了，我赶紧把一个玩具摆在了第一个格子...
image.png
生意太好了，又有人要问自行车，因为第一个格子是黄金位置，所以我把最新的都放那...
image.png
太火爆了，马上我的三个格子就不够用了...
image.png
因为格子从上到下依次最受欢迎，所以我会把下面格子的玩具放回到仓库，给新的玩具腾出点地方来
image.png
当然啦，如果客户想看摊位上已经有的玩具，我会把他放到第一个最火热的格子
image.png
2.LruCacha
下面以LruCacha为例，去简单理解下这个算法。
在Android中使用图片时，一般会用LruCacha做图片的内存缓存。
图片缓存简单使用实例：
int maxMemory = (int) (Runtime.getRuntime().totalMemory()/1024);
int cacheSize = maxMemory/8;
mMemoryCache = new LruCache<String,Bitmap>(cacheSize){
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getRowBytes()*value.getHeight()/1024;
}
};
①设置LruCache缓存的大小，一般为当前进程可用容量的1/8。
②重写sizeOf方法，计算出要缓存的每张图片的大小。
注意：缓存的总容量和每个缓存对象的大小所用单位要一致。
LruCacha:用LinkedHashMap实现LRU。
LinkedHashMap继承于HashMap。
在理解LruCacha之前，需掌握的知识点：
HashMap ，双向链表和LinkedHashMap。
2.1 HashMap 和 双向链表
这里简单介绍下集合类。
Java 的集合类很多，主要分为两大类：Collection 和 Map
- 集合主要是两组(单列集合, 双列集合)
- Collection 接口有两个重要的子接口List Set , 他们的实现子类都是单列集合
- Map 接口的实现子类是双列集合，存放的K-V
HashMap 小结
1.Map接口常用实现类： HashMap 、Hashtable 和 Properties。
2.HashMap是Map接口使用频率最高的实现类。
3.HashMap是以key-val 对的方式来存储数据（HashMap$Node类型）
4.key不能重复，但是值可以重复，允许使用null键和null值
5.如果添加相同的key，则会覆盖原来的key-val，等于修改（key不会替换，val会替换）。
6.与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的（hashmap 底层 数组+链表+红黑树）。
7.hashmap没有实现同步，因此线程不安全，方法没有做同步互斥的操作，没有 synchronized。
双向链表
https://baike.baidu.com/item/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/2968731?fr=aladdin
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
双向链表增删操作效率较高。
通过模拟一个双向链表来理解。
//定义一个Node 类，Node 对象表示双向链表的一个结点
class Node {
public Object item; //真正存放数据
public Node next; //指向后一个结点
public Node pre; //指向前一个结点
public Node(Object name) {
this.item = name;
}
public String toString() {
return "Node name=" + item;
}
}
public class LinkedList01 {
public static void main(String[] args) {
//模拟一个简单的双向链表
Node jack = new Node("jack");
Node tom = new Node("tom");
Node hsp = new Node("老韩");
//连接三个结点，形成双向链表
//jack -> tom -> hsp
jack.next = tom;
tom.next = hsp;
//hsp -> tom -> jack
hsp.pre = tom;
tom.pre = jack;
Node first = jack;//让first 引用指向jack,就是双向链表的头结点
//演示，从头到尾进行遍历
System.out.println("===从头到尾进行遍历===");
while (true) {
if(first == null) {
break;
}
//输出first 信息
System.out.println(first);
first = first.next;
}
//演示，从尾到头的遍历
System.out.println("====从尾到头的遍历====");
while (true) {
if(last == null) {
break;
}
//输出last 信息
System.out.println(last);
last = last.pre;
}
//演示链表的添加对象/数据，是多么的方便
//要求，是在tom --------- 老韩直接，插入一个对象smith
//1. 先创建一个Node 结点，name 就是smith
Node smith = new Node("smith");
//下面就把smith 加入到双向链表了
smith.next = hsp;
smith.pre = tom;
hsp.pre = smith;
tom.next = smith;
//让first 再次指向jack
first = jack;//让first 引用指向jack,就是双向链表的头结点
System.out.println("===从头到尾进行遍历===");
while (true) {
if(first == null) {
break;
}
//输出first 信息
System.out.println(first);
first = first.next;
}
last = hsp; //让last 重新指向最后一个结点
//演示，从尾到头的遍历
System.out.println("====从尾到头的遍历====");
while (true) {
if(last == null) {
break;
}
//输出last 信息
System.out.println(last);
last = last.pre;
}
}
}
2.2 LinkedHashMap
LinkedHashMap构造函数，主要就是调用HashMap构造函数初始化了一个Entry[] table，然后调用自身的init初始化了一个只有头结点的双向链表。
也可以参考这张LinkedHashSet图。
LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+ 双向链表。set和map的区别是一个存放的是单列数据，一个是双列K-V。把图中的123,456等数据换成k-v数据就行。
接下来，来看一下 put 和 get 代码。
先看看put。
http://aospxref.com/android-7.1.2_r39/xref/libcore/ojluni/src/main/java/java/util/LinkedHashSet.java
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
...
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
...
}
http://aospxref.com/android-7.1.2_r39/xref/libcore/ojluni/src/main/java/java/util/HashSet.java
//构造函数
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
...
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
新建了LinkedHashMap，LinkedHashMap继承自HashMap。LinkedHashMap中没有重写put,所以map.put调用的HashMap.put。
http://aospxref.com/android-7.1.2_r39/xref/libcore/ojluni/src/main/java/java/util/LinkedHashMap.java
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{}
http://aospxref.com/android-7.1.2_r39/xref/libcore/ojluni/src/main/java/java/util/HashMap.java
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
HashMap.put中调用了addEntry，LinkedHashMap又重写了addEntry，因此最终调用了LinkedHashMap中的addEntry,又由于调用了super.addEntry
,所以还是会调用HashMap.addEntry,但是createEntry有重写，所以调用了LinkedHashMap中的createEntry。
http://aospxref.com/android-7.1.2_r39/xref/libcore/ojluni/src/main/java/java/util/LinkedHashMap.java
void addEntry(int hash, K key, V value, int bucketIndex) {
// Previous Android releases called removeEldestEntry() before actually
// inserting a value but after increasing the size.
// The RI is documented to call it afterwards.
// **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
// Remove eldest entry if instructed
LinkedHashMapEntry<K,V> eldest = header.after;
if (eldest != header) {
boolean removeEldest;
size++;
try {
removeEldest = removeEldestEntry(eldest);
} finally {
size--;
}
if (removeEldest) {
removeEntryForKey(eldest.key);
}
}
super.addEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> old = table[bucketIndex];
LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
...
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
http://aospxref.com/android-7.1.2_r39/xref/libcore/ojluni/src/main/java/java/util/HashMap.java
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
也就是说，put的时候，先求hash值（int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);），再求索引(int i = indexFor(hash, table.length);)，确定元素在table的位置(table[bucketIndex] = e;)，然后将元素添加到双向链表（e.addBefore(header)）。
来看看addBefore。
addBefore(LinkedHashMapEntry<K,V> existingEntry)，注释解释为Inserts this entry before the specified existing entry in the list.
简单翻译就是在列表中指定的 现有条目 之前插入此条目，例如A.addBefore（B），B是已存在的现有条目（LinkedHashMapEntry），A是刚new的，把A插入到B之前。
举个例子，图中的c节点相当于下面代码中的existingEntry，要插入的是x节点。
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry; //相当于上图中的操作 1
before = existingEntry.before; //相当于上图中的操作 3
before.after = this; //相当于上图中的操作 4
after.before = this; //相当于上图中的操作 2
}
e.addBefore(header)传入的参数是header（header是双向链表的头）。
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
也可参考LinkedList。
https://blog.csdn.net/ylyg050518/article/details/78065671
实际上就是HashMap和LinkedList两个集合类的存储结构的结合。在LinkedHashMapMap中，所有put进来的Entry都保存在哈希表中，但它又额外定义了一个以head为头结点的空的双向循环链表，每次put进来Entry，除了将其保存到对哈希表中对应的位置上外，还要将其插入到双向循环链表的尾部。
因为是循环链表，所以header的前一个节点就是链表的最后一个节点。
下面来看看get。
http://aospxref.com/android-7.1.2_r39/xref/libcore/ojluni/src/main/java/java/util/LinkedHashMap.java
public V get(Object key) {
LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
if (e == null)
return null;
//该方法用来记录访问
e.recordAccess(this);
return e.value;
}
...
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
// 调用hashmap.remove移除lastReturned
remove();
// 把e插入到lm.header之前
addBefore(lm.header);
}
}
...
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
...
//libcore/ojluni/src/main/java/java/util/HashMap.java
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.getValue());
}
关于lastReturned，所有的操作都是在lastReturned指向的节点上进行操作，next指向下一个节点。(可参考LinkedList)。
get方法的逻辑是这样的:
调用父类的getEntry方法获取节点数据以后,再判断当前排序模式accessOrder,如果accessOrder是true,那就将当前节点从链表中移除,然后再将当前节点插入到链表头之前，修改entry在链表中的位置（访问过后就放到前面的位置）。
在对LinkedHashMap的数据结构有一定的了解后，接下来看看Android如何使用LinkedHashMap实现LRU缓存。
2.3 LruCache简单分析
https://www.jianshu.com/p/b49a111147ee
LruCache的实现原理
LruCache的核心思想很好理解，就是要维护一个缓存对象列表，其中对象列表的排列方式是按照访问顺序实现的，即一直没访问的对象，将放在队尾，即将被淘汰。而最近访问的对象将放在队头，最后被淘汰。
https://www.jianshu.com/p/b49a111147ee
由于代码版本不同，所以这句话关于头和尾的地方要反一下。
一直没访问的对象，将放在队尾，即将被淘汰。而最近访问的对象将放在队头，最后被淘汰。
本篇中的代码逻辑是：一直没访问的对象，将放在队头，即将被淘汰。而最近访问的对象将放在队尾，最后被淘汰。
图片逻辑也要反一下。
注意，LinkedHashMap代码中的header（private transient LinkedHashMapEntry<K,V> header;）不是这里的队头，这里的队头，实际代码中取的是header.after。
下面来看看具体代码。
LruCache源码简单分析，看看其构造函数，put和get。
http://aospxref.com/android-7.1.2_r39/xref/frameworks/base/core/java/android/util/LruCache.java
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
public final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
putCount++;
size += safeSizeOf(key, value);
previous = map.put(key, value);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
构造函数这里new了一个LinkedHashMap，accessOrder 设为true。
put()方法在添加过缓存对象后，调用 trimToSize，调整大小。这个函数很关键。
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
// size(缓存的元素个数) 小于 maxSize(容量) 那么跳出循环
if (size <= maxSize) {
break;
}
// eldest() 取 LinkedHashMap 里面最年老的元素
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
// 删掉 最近最少使用的
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
map.eldest()是什么？
http://aospxref.com/android-7.1.2_r39/xref/libcore/ojluni/src/main/java/java/util/LinkedHashMap.java#492
public Map.Entry<K, V> eldest() {
//取head的下一个
Entry<K, V> eldest = header.after;
//如果eldest != header则 返回eldest ，只剩下头节点返回null
return eldest != header ? eldest : null;
}
方法很简单，就是取出 header 的 after,取离头最近的一个。那为什么header.after就是最近最少使用的元素呢？这个是因为在 put 和 get 过程中，如果 accessOrder 设置为 true 的话，都会调用addBefore，会把对应 Entry 放到head的前面，链表的最后一个结点，即尾部。
最少使用的header.after,最新使用的是header.before。
就是把上面那张图中的头和尾反过来理解一下，把队头换成队尾。
再来看看get方法
/**
* 根据key查询缓存，如果存在于缓存或者被create方法创建了。
* 如果值返回了，那么它将被移动到双向循环链表的队头。
* 如果如果没有缓存和没有被创建过，则返回null。
*/
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//当accessOrder为true时，LinkedHashMap的get会实现将访问的元素更新到队列头部的功能
mapValue = map.get(key);
if (mapValue != null) {
// 计算 命中次数
hitCount++;
return mapValue;
}
// 计算 丢失次数
missCount++;
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
*/
/*
*
* 尝试创建一个值，这可能需要很长时间，并且Map可能在create()返回的值时有所不同。如果在create()执行的时
* 候，一个冲突的值被添加到Map，我们在Map中删除这个值，释放被创造的值。
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
/***************************
* 不覆写create方法走不到下面 *
***************************/
/*
* 正常情况走不到这里
* 走到这里的话 说明 实现了自定义的 create(K key) 逻辑
* 因为默认的 create(K key) 逻辑为null
*/
synchronized (this) {
// 记录 create 的次数
createCount++;
mapValue = map.put(key, createdValue);
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
return createdValue;
}
}
3.Lru在内存管理中的应用
可参考这篇
Linux学习-内存管理篇（六）-内存回收(lru链表)
参考链接：
Android LruCacha 源码分析
LRU原理和Redis实现——一个今日头条的面试题
用LinkedHashMap实现LRU
LinkedHashMap和LruCacha
LruCache 源码分析
LruCache 原理
Android LruCache源码解析
LruCache源码解析
彻底解析Android缓存机制——LruCache
Java集合框架源码分析(四)——LinkedHashMap
Map接口常用实现类学习
图解LinkedHashMap原理
Java集合------LinkedHashMap底层原理
数据结构 - 双链表的头插法和后插法
《韩顺平_循序渐进学Java》
