LruCache 原理
Lru 即 Least Recently Used，也就是最近最少使用算法。
LruCache 就是当缓存空间满了的时候，将最近最少使用的数据从缓存空间中删除以增加可用的缓存空间来缓存新内容。LruCache 内部有一个缓存列表。每当访问一个缓存数据的时候，就会把该缓存数据放到列表头部，一段时间后，列表的尾部数据就是最近最不常使用的了，当缓存空间不足时，就会删除列表尾部的缓存数据。
LruCache 源码中首先声明了 LinkedHashMap 类型的全局变量 map，LinkedHashMap 继承于 HashMap，它使用了一个双向链表来保证了 Map 中的 Entry 顺序关系。LinkedHashMap 是 LruCache 中最核心的部分，所以我们需要先来了解一下 LinkedHashMap 的具体实现。
private final LinkedHashMap<K, V> map;
关于 LinkedHashMap
简单来说，LinkedHashMap 是 HashMap 和双向链表的组合。它是一个将所有 Entry 节点通过双向链表结构组织起来的 HashMap。LinkedHashMap 是 HashMap 的子类，所以它拥有 HashMap 的所有特性。
假如 LinkedHashMap 的插入顺序为 Entry1，Entry2，Entry3，Entry4，那么此时的结构可以用下图表示：
LinkedHashMap 结构图.png
1、为了实现双向链表，LinkedHashMap 中定义了如下 LinkedHashMapEntry：
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
可以看到，LinkedHashMapEntry 在 HashMap.Node 的基础上，额外定义了 before 和 after 两个 LinkedHashMapEntry 的引用，分别引用前一个元素和后一个元素。
2、然后 LinkedHashMap 中还定义了 head 和 tail，可以用于从前往后和从后往前的检索：
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> tail;
3、LinkedHashMap 的构造方法如下：
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
其中在 HashMap 构造方法的基础上，增加了 accessOrder 变量的赋值。accessOrder 变量的定义如下：
/**
* 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;
accessOrder 用来标识双向链表中排序规则，ture 为按照访问顺序排序，false 为按照插入顺序排序。所以构造方法中，没有指定 accessOrder 时，默认为 false，按照插入顺序排序。
双向链表的维护主要依靠三个方法，即 afterNodeRemoval，afterNodeInsertion，afterNodeAccess。这三个方法的主要作用是，在删除，插入，获取节点之后，对链表进行维护。
4、下面是 afterNodeRemoval 的源码：
// 在节点删除后，维护链表，传入删除的节点
void afterNodeRemoval(Node<K,V> e) { // unlink
// p 指向待删除元素，b 指向待删除元素的前驱节点，a 指向待删除元素后驱节点
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
// 待删除节点的前驱节点和后驱节点置空
p.before = p.after = null;
if (b == null)
// 如果待删除节点的前驱节点为空，即删除了头节点，此时把 head 头节点指向待删除节点的后驱节点
head = a;
else
// 否则直接把待删除节点的前驱节点的下一节点指向待删除节点的后驱节点
b.after = a;
if (a == null)
// 如果待删除节点的后驱节点为空，即删除了尾节点，此时把 tail 尾节点指向待删除节点的前驱节点
tail = b;
else
// 否则直接把待删除节点的后驱节点的前一节点指向待删除节点的前驱节点
a.before = b;
}
5、下面是 afterNodeInsertion 的源码：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMapEntry<K,V> first;
// removeEldestEntry 方法自身固定返回 false，所以不会进入 if 代码块
// 但是子类可重写，某些情况子类重写后可以实现在插入新节点后删除头节点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
6、下面是 afterNodeAccess 的源码：
// 该方法负责在节点被访问后根据 accessOrder 判断是否需要调整链表顺序
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
// 如果 accessOrder 为 true，即按照访问顺序排序
// 并且尾节点不为被访问的节点
// p 为被访问的节点，b 为被访问节点的前驱节点，a 为被访问节点的后驱节点
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
// 先执行删除被访问节点的后一节点
p.after = null;
if (b == null)
// 被访问节点的前驱节点为空，即如果 p 为头节点
// 那么头节点就被设为被访问节点的后驱节点
head = a;
else
// 否则被访问节点的前驱节点的后驱节点设为被访问节点的后驱节点
b.after = a;
if (a != null)
// 被访问节点的后驱节点不为空，即如果 p 不为尾节点
// 那么被访问节点的后驱节点的前驱节点被设为被访问节点的前驱节点
a.before = b;
else
// 如果 p 为尾节点，删除 p 后，这里只是先把 last 变量设为 b
last = b;
if (last == null)
// 如果 last 为空，只有整个链表为空
// 直接把头节点设为 p
head = p;
else {
// 否则把被访问节点的前驱节点设为 last
p.before = last;
// last 的后驱节点设为被访问节点
last.after = p;
}
// 尾节点设为被访问节点
// 这个过程可以看到最新访问的节点被放到了尾节点的位置
// 所以前面 if 语句中 (last = tail) != e 的判断，正是当被访问的节点为尾节点时，跳过处理
tail = p;
++modCount;
}
}
7、LinkedHashMap 中重写了 HashMap 的 get 方法：
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;
}
相比 HashMap 的 get 方法，增加了判断是否为按照访问顺序排序的处理。
LinkedHashMap 中没有重写 put 方法和 remove 方法。
LruCache 的源码分析
1、LruCache 中全局变量的定义：
private final LinkedHashMap<K, V> map;
/** Size of this cache in units. Not necessarily the number of elements. */
private int size;
private int maxSize;
private int putCount;
private int createCount;
private int evictionCount;
private int hitCount;
private int missCount;
除了 LinkedHashMap 类型的 map 以外，还定义了 size、maxSize 等变量，变量名的定义就已经能很好帮助我们理解它们的意义了。
2、LruCache 的构造方法，只有一个：
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);
}
传入初始的 maxSize 值，赋值全局变量 maxSize，并初始化 LinkedHashMap，初始容量 0，装载因子 0.75，并且需要按访问顺序排序。
3、LruCache 的 get 方法：
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
// 同步获取 map 中 key 值对应的 value 值
mapValue = map.get(key);
if (mapValue != null) {
// 如果获取到的 value 值不为空，则将命中数加 1 后直接返回 value
// 此时由于我们初始化的 map 为 accessOrder = ture，即会按照访问顺序排序
// 所以该 value 值在 map 内的双向链表结构中，会被放到尾部 tail 的位置
hitCount++;
return mapValue;
}
// 如果获取到的 value 值为空，则将未命中数 missCount 加 1
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.
*/
// 根据注释内容，接下调用 createdValue 方法来尝试创建新值
// create 方法默认返回空，可由子类重写
V createdValue = create(key);
// 创建新值失败则直接返回空
if (createdValue == null) {
return null;
}
// 创建新值成功
synchronized (this) {
// 创建新值的计数加 1
createCount++;
// 并且将新创建的值添加到 map 中，此时
mapValue = map.put(key, createdValue);
// 如果 map 的 put 方法返回的 mapValue 不为空，则说明原来的 key 值对应的 value 是存在的
if (mapValue != null) {
// There was a conflict so undo that last put
// 所以重新把原来的值 mapValue 放回去
// 相当于撤销刚才添加新值的操作
map.put(key, mapValue);
} else {
// 加入新创建的 value 之后重新计算 size 大小
size += safeSizeOf(key, createdValue);
}
}
// 上面重新创建新值并且添加到 map 的过程中
if (mapValue != null) {
// 如果原来的 key 值对应的 value 是存在的
// 调用 entryRemoved 方法并传入 key 值，创建的值 createdValue，和原来存在的值 mapValue
// 该方法为空方法，可以预见是让子类重写来自行处理此情况
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
// 创建了新值，并把新值添加到 map 中之后
// 调用此方法来检查是否达到 maxSize 大小，回收旧数据
trimToSize(maxSize);
return createdValue;
}
}
protected V create(K key) {
return null;
}
以线程安全的方式获取 map 中 key 值对应的 value 值。如果获取数据失败，则会触发 create 方法创建，该方法由子类重写，create 默认返回 null。如果创建数据成功则会将数据插入 map 中，插入成功会触发调用 entryRemoved 方法，该方法也是由子类重写。插入新值会触发 trimToSize 方法来检查是否达到 maxSize 大小，回收旧数据。
get 方法的源码还是比较简单的，接下来需要关注的是源码中 trimToSize(maxSize) 方法。
4、下面是 trimToSize 方法的源码：
private 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 小，则说明无需回收旧数据，break 跳出循环
if (size <= maxSize) {
break;
}
// BEGIN LAYOUTLIB CHANGE
// get the last item in the linked list.
// This is not efficient, the goal here is to minimize the changes
// compared to the platform version.
Map.Entry<K, V> toEvict = null;
// 这里获取需要回收的数据
// 可以发现，通过遍历的方式获取链表中最后一个 item 作为需要回收的数据
// 而链表中最后一个 item 为我们新访问过的数据，此时回收掉新访问过的数据不是出问题了吗？
// 关于这个问题也有不少的讨论。比较多的说法是 Framework 实现和 SDK 源码不一致，SDK 源码也就是下面的写法是存在 Bug 的写法。
// 相关文章：https://blog.csdn.net/xhmj12/article/details/107308212
// 这里我们只要知道拿到的 toEvict 是 map 的双向链表中 head 元素，也就是 eldest 的元素即可
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
// END LAYOUTLIB CHANGE
// 需要回收的数据为空，直接返回
if (toEvict == null) {
break;
}
// 从 map 中删除需要回收的数据的 toEvict
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
// 减小 size
size -= safeSizeOf(key, value);
// 回收计数加 1
evictionCount++;
}
// 旧数据被回收，调用此方法，此为空方法，可由子类重写
entryRemoved(true, key, value, null);
}
}
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
protected int sizeOf(K key, V value) {
return 1;
}
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
负责在缓存空间不足时回收旧数据。
5、看完 LruCache 的 get 方法后，下面就可以来看看 LruCache 的 put 方法了：
public final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
// 同步语句中
// putCout 计数加 1
putCount++;
// size 计数增加，根据上文的源码可知，默认加 1
size += safeSizeOf(key, value);
// 调用 map 的 put 方法，返回之前存在的 value 值 previous
previous = map.put(key, value);
// 如果之前 key 值已经存在对应的 value，即 previous
if (previous != null) {
// 那么将 size 的计数减 1
// 因为此时是覆盖新值，size 在 put 之前加 1，所以这里需要减 1
size -= safeSizeOf(key, previous);
}
}
// 如果旧数据被覆盖，也认为被回收，调用 entryRemoved 方法
// 方法的第一个参数 evicted 为 true 表示是由于清理控件被自动回收
// false 表示在 put、remove 方法中被主动覆盖或移除了
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
6、最后来看一下 LruCache 的 remove 方法：
/**
* Removes the entry for {@code key} if it exists.
*
* @return the previous value mapped by {@code key}.
*/
public final V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
// 调用 map 的 remove 方法并传入参数 key
previous = map.remove(key);
if (previous != null) {
// 移除的 value 不为空，则 size 计数减 1
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
// 调用 entryRemoved 方法
entryRemoved(false, key, previous, null);
}
return previous;
}
有了前面的分析后，理解 remove 方法就更简单了。
目前为止，LruCache 的原理和关键方法也就大致如此了。其他的细节在了解了原理和关键方法后，便能很轻松掌握。
