1 LruCache介绍
1.1 常见的缓存算法
- FIFO(First In First Out)：先进先出
- LRU(Least Recently Used)：最近最少使用
- LFU(Least Frequently Used)：最不经常使用
举个例子，比如我们的缓存对象顺序为：(队尾)EDDCBABAEA(队头)。如果这时候来了个A，这时候要淘汰一个对象，如果是FIFO，这时候就会淘汰的E；如果是LRU的话，这时候就会淘汰的D，因为D被使用过之后接下来再也没有被使用过了；如果是LFU的话，那么淘汰的就是C了，因为C就被使用过一次。
1.2 LruCache是什么？
LRU (Least Recently Used) 的意思就是近期最少使用算法，它的核心思想就是会优先淘汰那些近期最少使用的缓存对象。当访问一个数据时，这个数据就会被移动到数据队列的头部(经常用到的数据)，当数据添加到缓存满时，队列尾部的数据(也就是不常用到的数据)会被删除并被回收。
在Android中采用LRU算法的常用缓存有两种：LruCache和DisLruCache，分别用于实现内存缓存和硬盘缓存，其核心思想都是LRU缓存算法。
1.3 LruCache使用
Android 提供的 LruCache 基于 LinkedHashMap 实现，利用 LinkedHashMap 会在每次访问元素之后，将元素移动到序列末尾的特点，保证了最近最多使用的元素位于尾部，最近最少使用的元素位于头部，当缓存占用达到设置的上限时，LruCache 就会移出 LinkedHashMap 中的头节点。
LruCache虽然使用了LinkedHashMap，但是实现的思路并不一样。Java需要重写removeEldestEntry来判断是否删除节点；而Android需要重写LruCache的sizeOf，返回当前节点的大小，Android会根据这个大小判断是否超出了限制，进行调用trimToSize方法清除多余的节点。
我们就以图片缓存为例：
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方法，计算出要缓存的每张图片的大小。
注意：缓存的总容量和每个缓存对象的大小所用单位要一致。
1.4 DiskLruCache使用
参考链接[2]
2 LruCache源码
2.1 LruCache 的构造
LruCache正是用了LinkedHashMap的accessOrder=true构造参数实现LRU访问顺序。
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; //当前cache的大小
private int maxSize; //cache最大大小
private int putCount; //put的次数
private int createCount; //create的次数
private int evictionCount; //驱逐剔除的次数
private int hitCount; //命中的次数
private int missCount; //未命中次数
//...省略...
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
//将LinkedHashMap的accessOrder设置为true来实现LRU顺序
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
}
2.2 LruCache 插入元素
public final V put(K key, V value) {
V previous;
synchronized (this) {
putCount++;
// 内存占用记录增加
size += safeSizeOf(key, value);
// 存入新的值, 并获取 key 对应的旧值
previous = map.put(key, value);
if (previous != null) {
//如果已有缓存对象，则缓存大小的值需要剔除这个旧的大小
size -= safeSizeOf(key, previous);
}
}
//entryRemoved()是个空方法，可以自行实现
if (previous != null) {
entryRemoved(false, key, previous, value);
}
// 如果 size > maxSize, 就执行丢弃元素, 裁剪内存操作
trimToSize(maxSize);
return previous;
}
trimToSize()方法不断地删除LinkedHashMap中队头的元素，即近期最少访问的，直到缓存小于最大值。
public void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
//如果map为空并且缓存size不等于0或者缓存size小于0，抛出异常
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
//如果缓存大小size小于最大缓存，或者map为空，则不需要再删除缓存对象，跳出循环
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);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
2.3 LurCache 获取缓存
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//获取对应的缓存对象
//LinkedHashMap的get()方法会实现将访问的元素更新到队列尾部的功能
mapValue = map.get(key);
//mapValue不为空表示命中，hitCount+1并返回mapValue对象
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++; //未命中
}
/*
* 如果未命中，则试图创建一个对象，这里create方法默认返回null,并没有实现创建对象的方法。
* 如果需要事项创建对象的方法可以重写create方法。因为图片缓存时内存缓存没有命中会去
* 文件缓存中去取或者从网络下载，所以并不需要创建，下面的就不用看了。
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//假如创建了新的对象，则继续往下执行
synchronized (this) {
createCount++;
//将createdValue加入到map中，并且将原来键为key的对象保存到mapValue
mapValue = map.put(key, createdValue);
if (mapValue != null) {
// There was a conflict so undo that last put
//如果mapValue不为空，则撤销上一步的put操作。
map.put(key, mapValue);
} else {
//加入新创建的对象之后需要重新计算size大小
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
//每次新加入对象都需要调用trimToSize方法看是否需要回收
trimToSize(maxSize);
return createdValue;
}
}
参考资料：
[1] Android LruCache 缓存机制实现原理
[2] Android DiskLruCache完全解析，硬盘缓存的最佳方案 ★
[3] 源码分析 - LRUCache缓存实现原理 ★
