LruCache
一. LRU算法简介
LRU算法，全称Least Rencetly Used，就是最近最少使用算法，用来淘汰长时间未使用的对象。他的核心思想是每一次新增或者使用一个对象时，把这个对象放在优先级最高的位置上，每次需要淘汰的时候，淘汰掉优先级最低的对象。
二. 使用
LruCache使用较为简单，我们只说明回调方法，其他不做赘述。
val lruCache = object :LruCache<String,String>(1 * 1024 *1024){
//重新设置最大空间
override fun resize(maxSize: Int) {
super.resize(maxSize)
}
//设置初始值
override fun create(key: String?): String {
return super.create(key)
}
//数据更新/销毁的回调
override fun entryRemoved(evicted: Boolean, key: String?, oldValue: String?, newValue: String?) {
super.entryRemoved(evicted, key, oldValue, newValue)
}
//自定义容量计算
override fun sizeOf(key: String?, value: String?): Int {
return super.sizeOf(key, value)
}
//确定清理缓存时调用
override fun trimToSize(maxSize: Int) {
super.trimToSize(maxSize)
}
}
lruCache.put(key,value)
lruCache.get(key)
lruCache.remove(key)
三. 源码分析
1. 基本结构
1.1 构造函数
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);//LruCache的主体，也是Lru算法得以实现的关键。
}
在创建LruCache对象的时候，我们需要指定最大的缓存大小，每当缓存的空间大于这个值的时候，就会执行回收操作。LruCache的内部维护了一个LinkHashMap对象，这个对象是LruCache的核心部分，是Lru算法得以实现的关键，下面，我们来简单说说LinkedHashMap是何神圣。
1.2 LinkedHashMap简介
LinkedHashMap继承自HashMap，就是说他拥有HashMap的一切特性，同时，他还是一个双向循环链表。链表结构使内部存储的数据有了先后的顺序（类似优先级），在这里我们需要注意他的一个构造函数：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
构造函数的前两个参数分别是初始大小和负载因子，与HashMap相同，在这儿我们不做赘述，需要注意的是第三个Boolean类型的参数，当accessOrder = true的情况下，map基于访问顺序排列，即每当我们调用put/get方法时，都会将我们操作的节点移动到链表的尾部，而链表头部则是我们最少使用的节点；当accessOrder = false的情况下，map基于插入顺序排列，即节点顺序只与插入顺序有关。
2. put()/get()方法
2.1 put()方法：
/**
* 数据更新/存储采用键-值对的方式
*/
public final V put(K key, V value) {
//键值不可为空
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
//key对应的前一个数据
V previous;
//线程锁
synchronized (this) {
//放置数量加一
putCount++;
//计算更新/存储数据后总共所占的空间大小
size += safeSizeOf(key, value);
//获取更新前的数据（没有则为null）
previous = map.put(key, value);
if (previous != null) {
//若更新前存在更新前数据，需减去更新前数据所占的空间大小
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
//若存在更新前的数据，回调销毁节点方法
entryRemoved(false, key, previous, value);
}
//清理缓存空间
trimToSize(maxSize);
//返回更新前一个数据
return previous;
}
从源码里我们可以知道，put方法分为以下几步：
判断key/value不可为空；
获取需要缓存的数据大小，并添加进现在缓存大小（size）中；
-
放置数据，并获取更新前的数据，此时：
- 若存在更新前数据，则从现在缓存大小（size）中减去更新前数据大小，并回调
entryRemoved()方法；
- 若存在更新前数据，则从现在缓存大小（size）中减去更新前数据大小，并回调
调用
trimToSize()清理缓存空间。
那么，trimToSize()又是怎么清理缓存空间的呢？我们接着往下看：
private void trimToSize(int maxSize) {
//循环执行Lru算法，直到当前容量小于设置的最大容量
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) {
break;
}
//下面则是Lru算法的相关操作
//需要销毁的节点
Map.Entry<K, V> toEvict = null;
//获得队尾的节点
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
// END LAYOUTLIB CHANGE
if (toEvict == null) {
break;
}
//销毁节点
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
//减去销毁节点所占的空间
size -= safeSizeOf(key, value);
evictionCount++;
}
//回调方法
entryRemoved(true, key, value, null);
}
}
2.2 get()方法：
public final V get(K key) {
//key不能为空
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//获取key所对应的value
mapValue = map.get(key);
//若获取到的value不为空，则返回，至此get()方法完成
if (mapValue != null) {
hitCount++;
return mapValue;
}
//此方法下都是value不存在的处理
missCount++;
}
//调用create方法初始化一个value（需要用户覆写）
V createdValue = create(key);
//若为空，则返回null
if (createdValue == null) {
return null;
}
//若不为空执行（说明用户已指定初始值）
synchronized (this) {
createCount++;
//将初始值放入map并获取更新前的一个值
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;
}
}
从源码中我们可以知道，get()方法分一下几步：
- 调用map的
get()方法，若有值则直接返回； - 调用
create()方法，获取初始值，若初始值不存在则直接返回null； - 将得到的初始值放入map中，并获得更新前的数据，此时：
- 若更新前已存在数据，则撤销初始值，将更新前的数据重新放入，并回调
entryRemoved()方法，返回更新前的数据； - 若更新前不存在数据，则计算初始数据的大小，添加进当前所占空间中，并执行清理缓存的操作，返回初始值。
- 若更新前已存在数据，则撤销初始值，将更新前的数据重新放入，并回调
2.3 总结
自此回顾我们可以发现，LruCache的put()/get()方法都具有以下特征：
- key、value不可为空；
- 有线程锁，所以不用在多线程操作时额外进行添加线程锁的操作；
