本篇分为两部分，为LruCache缓存原理和LinkedHashMap部分源码分析两点。这么做的目的是LruCache是基于LinkedHashMap实现的，通过两者的分析，可以更好的掌握其中的奥妙～
文章大纲
- LruCache
1.1 简介
1.2 原理分析- LinkedHashMap
2.1 保证顺序和容量的三个重要方法
2.2 get/put- 总结——为什么要在LruCache处理内存溢出
LruCache
1. 简介
LruCache（Last Recent Use）是Android3.1提供的一个缓存类，使用它可以方便实现内存缓存，通常在图片加载对Bitmap缓存时使用。
主要原理：把最近使用的对象用强引用存储在LinkedHashMap中，当内存满的时候，将最旧的对象移除。
LruCache是线程安全的，LinkedHashMap是线程兼容（非线程安全）。
- 简单使用
// 获取android系统的内存大小，需在四大组件中获取
int memorySize = (int) (Runtime.getRuntime().maxMemory() / 1024);
// 构造参数传入缓存池大小，内存的八分之一
LruCache<String, Bitmap> lruCache = new LruCache<String, Bitmap>(memorySize / 8) {
@Override
protected int sizeOf(@NonNull String key, @NonNull Bitmap value) {
// 返回存储对象的字节大小，单位保持一致
return value.getRowBytes() * value.getHeight() / 1024;
}
};
注意，构造函数传入的缓存池大小和sizeOf()计算的对象大小单位需保持一致，这里使用kb。如没有重写sizeOf()方法，默认返回对象大小为1。即通过计数实现缓存，可在构造函数传入最多存储多少个对象。
存储和访问通过put(K k, V v)和get(K k)即可。
2. 原理分析
LruCache是基于LinkedHashMap实现的。其构造方法如下
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
} else {
this.maxSize = maxSize;
// 第三个参数为true表示开启LinkedHashMap的accessOrder模式，保证old->new的排序，详细请看第二部分
this.map = new LinkedHashMap(0, 0.75F, true);
}
}
2.1 put方法
@Nullable
public final V put(@NonNull K key, @NonNull V value) {
if (key != null && value != null) {
Object previous;
// 同步处理
synchronized(this) {
++this.putCount;
// 计算当前缓存容量大小
this.size += this.safeSizeOf(key, value);
// 加入缓存
previous = this.map.put(key, value);
// 如果已有缓存对象，将容量减去
if (previous != null) {
this.size -= this.safeSizeOf(key, previous);
}
}
if (previous != null) {
// 空实现，需用户自行实现该方法，用于资源缓存删除时用户对该资源的回收处理
this.entryRemoved(false, key, previous, value);
}
// 调整缓存大小，关键方法
this.trimToSize(this.maxSize);
return previous;
} else {
throw new NullPointerException("key == null || value == null");
}
}
2.2 trimToSize调整缓存大小
LruCache的重点方法。
思路：每次put添加元素都会调用该方法，判断容量是否充足；如充足，直接插入，如不充足，剔除最旧的对象（通过LinkedHashMap.accessNodeAccess保证顺序）。
public void trimToSize(int maxSize) {
while(true) {
Object key;
Object value;
synchronized(this) {
if (this.size < 0 || this.map.isEmpty() && this.size != 0) {
throw new IllegalStateException(this.getClass().getName() + ".sizeOf() is reporting inconsistent results!");
}
// 如果缓存容量充足，则不需要调整，直接返回
if (this.size <= maxSize || this.map.isEmpty()) {
return;
}
// 获取最旧的对象
Entry<K, V> toEvict = (Entry)this.map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
// 移除该对象
this.map.remove(key);
this.size -= this.safeSizeOf(key, value);
++this.evictionCount;
}
// 回调移除后的处理
this.entryRemoved(true, key, value, (Object)null);
}
}
2.3 remove
思路：通过Map移除对象，并响应减去该对象占用的size，更新缓存容量。
@Nullable
public final V remove(@NonNull K key) {
if (key == null) {
throw new NullPointerException("key == null");
} else {
Object previous;
synchronized(this) {
previous = this.map.remove(key);
if (previous != null) {
this.size -= this.safeSizeOf(key, previous);
}
}
if (previous != null) {
this.entryRemoved(false, key, previous, (Object)null);
}
return previous;
}
}
需要注意的是，如果需要对LruCache移除的对象进行处理时，如资源回收，需重写其entryRemove()方法，该方法上面多次提到，在entry被移除时调用。
LinkedHashMap
LinkedHashMap是Hash表和链表的实现，继承于HashMap。依靠双链表保证迭代顺序是插入的顺序。
1. 保证顺序和容量的三个重点实现方法
这三个方法在HashMap中提供了空实现，并封装集成到部分操作中（put、get）
- afterNodeAccess
在访问节点后调用。保证最近访问的节点放在最后，目的是实现双向链表的第一个节点为最旧的节点，在保证容量、固定缓存大小得到应用。保证顺序为 旧 -> 新。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 如果定义了accessOrder，那么就保证最近访问节点放到最后
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;
}
}
acessOrder在其构造函数定义，默认为false。如下
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
- afterNodeInsertion
顾名思义，在插入节点后调用。当用户定义了溢出规则，在实现内存缓存可利用该方法。它保证在满足removeEldestEntry(E e)的情况下，每次新增新节点时，能够将最旧的节点移除。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
// afterNodeAccess 保证的顺序体现在这里
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
/*
在这里添加内存满的阀值
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
// 可使用 size() == MEMORY_SIZE
return false;
}
- afterNodeRemoval
该函数在移除节点后调用，目的是将节点从双向节点删除。
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
2. get和put
-
put
put方法在LinkedHashMap中并未重新实现，只是实现了afterNodeAccess，该方法在HashMap的put方法中就已经被调用了，有兴趣可以查源码看，基本就是在元素插入后的时机进行调用。如下：
image.png get
get方法在HashMap的基础上添加了afterNodeAccess，在aceessOrder的情况下保证访问顺序。
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模式下，只要执行get或者put等操作的时候，就会产生·structural modification`。官方文档是这么描述的：
In access-ordered linked hash maps, merely querying the map with get is a structural modification.
总结
LruCache可以认为是在LinkedHashMap的基础上实现了同步+缓存容量计算方法，在对LinkedHashMap的分析中，其也可以利用accessNodeInseraction()保证缓存池数量不会溢出，那么LruCache还要自己实现溢出处理呢？
笔者认为原因有以下两点：
- LinkedHashMap为非线程安全对象，其溢出处理可能会导致线程冲突。
- LinkedHashMap中只是对缓存池数量进行溢出处理，但在现实使用中，缓存池的容量一般使用kb作为单位，如Bitmap，LruCache对于这两种的兼容处理是采取
sizeOf()方法，上面已经介绍过了。
