在开发中我们会经常碰到一些资源需要做缓存优化，例如Bitmap，Json等，那么今天我们来瞧瞧默默无闻的LruCache的实现原理
Ps：本文基于API25
简介
当我们做数据缓存处理的时候缓存大小到达临界值时我们会面临2个选择，一个是扩容，一个是清理缓存，而LruCache就是一种属于选择清理缓存的方式，清理最长时间未使用的数据。
分析
按照惯例，我们从入口开始，直接看v4包下的好了，和普通的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);
}
在构造方法中需要传入一个阈值，也就是缓存大小的上限，内部有一个LinkedHashMap作为强引用来保存，我们来看看LinkedHashMap构造器里面发生了什么
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{//省略其他代码
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
}
LinkedHashMap继承于HashMap，对HashMap还不了解的同学要赶紧补补了。
在开发中我们遍历HashMap的Entry会发现它不是按插入顺序排序的，而LinkedHashMap的机制会将每一个数据节点前后链起来，是一个双向循环链表的数据结构。
在使用LinkedHashMap我们用无参构造的时候，是按顺序排列的，取个例子
LinkedHashMap<String,String> map=new LinkedHashMap<>();
map.put("1","1");
map.put("2","2");
map.put("3","3");
map.put("1","4");
Iterator<Map.Entry<String, String>> i = map.entrySet().iterator();
while (i.hasNext()) {
Map.Entry<String, String> e = i.next();
Log.e("Entry", e.getKey() + " " + e.getValue());
}
这种时候日志会输出
Entry: 1 4
Entry: 2 2
Entry: 3 3
因为map.put("1","4")把原来的值覆盖了，不影响链表排序，
那么我们来看这个accessOrder开关，默认是false，翻译出来是存取顺序，开启了会发生什么
Entry: 2 2
Entry: 3 3
Entry: 1 4
顺序发生了改变！我们来看看这个accessOrder影响了什么逻辑
private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
//省略
private void remove() {
//原来前后的数据节点链在一起
before.after = after;
after.before = before;
}
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
//移出当前的Entry结构
remove();
//移动到队列尾部
addBefore(lm.header);
}
}
//省略
}
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;
}
LinkedHashMap额外采用了链表的设计，这么一看，完全符合LruCache近期最少使用的策略，我们来完整的看一下LruCache的成员变量：
public class LruCache<K, V> {
//强引用保存
private final LinkedHashMap<K, V> map;
/** Size of this cache in units. Not necessarily the number of elements. */
private int size;
//缓存上限
private int maxSize;
//put的次数
private int putCount;
//create的次数
private int createCount;
//移除的次数
private int evictionCount;
//命中缓存的次数
private int hitCount;
//未命中缓存的次数
private int missCount;
}
可以发现LruCache的成员变量异常简单，出去一些计数的变量外，就一个LinkedHashMap来保存我们的缓存数据，
我们先来看看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) {
//计数+1
putCount++;
//计算放入的大小
size += safeSizeOf(key, value);
previous = map.put(key, value);
if (previous != null) {
//此次put是覆盖数据，减去计算的大小
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
//空方法，用于通知
entryRemoved(false, key, previous, value);
}
//修改尺寸
trimToSize(maxSize);
return previous;
}
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;
}
在put方法内部对放入的value进行了大小计算，也就是说我们在使用LruCache需要重写sizeOf方法，要不然LruCache无法对缓存空间进行计算。
接着当我们put时如果覆盖了新数据时，会回调entryRemoved方法，然后LruCache会调用trimToSize对当前的map空间进行计算，代码如下：
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!");
}
if (size <= maxSize || map.isEmpty()) {
//不到上限时跳出死循环
break;
}
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
//移除最开始放入的
map.remove(key);
size -= safeSizeOf(key, value);
//移除数+1
evictionCount++;
}
//空方法，回调
entryRemoved(true, key, value, null);
}
}
在trimToSize方法中是一个死循环，只要当前map的空间大于上限，就将其移除队列，并且回调entryRemoved，那么我们来看看
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
参数分别代表
- 是否因为大小被驱逐，555~~
- key
- 老数据
- 新数据，可能为null
这里trimToSize方法是public，也就是说比如在内存紧张的时候可以手动清理一部分缓存。接下来我们来看看get方法：
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//获取数据
mapValue = map.get(key);
if (mapValue != null) {
//命中+1，并返回
hitCount++;
return mapValue;
}
missCount++;
}
//空方法，默认返回null
V createdValue = create(key);
if (createdValue == null) {
return null;
}
synchronized (this) {
createCount++;
//将创建出来的数据放入
mapValue = map.put(key, createdValue);
if (mapValue != null) {
//对应的key原来有value的情况下，那就再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;
}
}
其中有一个空方法create，有需求可以重写，就是在根据key去寻找value时，如果找不到，可以选择创建一个value并放入到缓存队列中。
总结
LruCache源码异常的精简，核心原理是通过LinkedHashMap双向循环链表，每次访问过的数据会被移动到队列末尾，在使用过程中我们需要重写sizeOf方法来帮助LruCache计算缓存大小，每当缓存数据发生覆盖或者清理时会回调entryRemoved方法，并且LruCache是线程安全的，核心操作都上了同步锁。
Ps:我们可以手动调用trimToSize清理一批数据，也可以调用resize方法，重新赋值缓存大小的上限并计算当前空间是否需要清理，snapshot来获取缓存map的切片，注意是浅拷贝。
文章如有错误，敬请指正！
本文的姊妹篇：DiskLruCache源码分析
“ 神爱世人，甚至将他的独生子赐给他们，叫一切信他的，不至灭亡，反得永生。 (约翰福音 3:16 和合本)
