LruCache实现原理

序、慢慢来才是最快的方法。

回顾

LRU （Least Recently Used）最近最少策略是最常用的缓存淘汰策略。LRU 策略会记录各个数据块的访问 “时间戳” ，最近最久未使用的数据最先被淘汰。与其他几种策略相比，LRU 策略利用了 “局部性原理”，平均缓存命中率更高。

FIFO 与 LRU 策略

经过总结，我们可以定义一个缓存系统的基本操作：

操作 1 - 添加数据： 先查询数据是否存在，不存在则添加数据，存在则更新数据，并尝试淘汰数据；
操作 2 - 删除数据： 先查询数据是否存在，存在则删除数据；
操作 3 - 查询数据： 如果数据不存在则返回 null；
操作 4 - 淘汰数据： 添加数据时如果容量已满，则根据缓存淘汰策略一个数据。

在 Java 标准库中，已经提供了一个通用的哈希链表 —— LinkedHashMap。使用 LinkedHashMap 时，主要关注 2 个 API：

accessOrder 标记位： LinkedHashMap 同时实现了 FIFO 和 LRU 两种淘汰策略，默认为 FIFO 排序，可以使用 accessOrder 标记位修改排序模式。
removeEldestEntry() 接口： 每次添加数据时，LinkedHashMap 会回调 removeEldestEntry() 接口。开发者可以重写 removeEldestEntry() 接口决定是否移除最早的节点（在 FIFO 策略中是最早添加的节点，在 LRU 策略中是最久未访问的节点）。

1.LruCache源码分析

1.1LruCache 的 API

LruCache 是 Android 标准库提供的 LRU 内存缓存框架，基于 Java LinkedHashMap 实现，当缓存容量超过最大缓存容量限制时，会根据 LRU 策略淘汰最久未访问的缓存数据。

用一个表格整理 LruCache 的 API：

1.2 LruCache 的属性

LruCache 的属性比较简单，除了多个用于数据统计的属性外，核心属性只有 3 个：

1、size： 当前缓存占用；
2、maxSize： 最大缓存容量；
3、map： 复用 LinkedHashMap 的 LRU 控制能力。

LruCache.java

public class LruCache<K, V> {// LRU 控制private final LinkedHashMap<K, V> map;// 当前缓存占用private int size;// 最大缓存容量private int maxSize;// 以下属性用于数据统计// 设置数据次数private int putCount;// 创建数据次数private int createCount;// 淘汰数据次数private int evictionCount;// 缓存命中次数private int hitCount;// 缓存未命中数private int missCount;
}

1.3 LruCache 的构造方法

LruCache 只有 1 个构造方法。

由于缓存空间不可能设置无限大，所以开发者需要在构造方法中设置缓存的最大内存容量 maxSize。

LinkedHashMap 对象也会在 LruCache 的构造方法中创建，并且会设置 accessOrder 标记位为 true，表示使用 LRU 排序模式。

LruCache.java #构造方法

  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);}

使用示例

 private static final int CACNHE_SIZE = 4 * 1024 * 1024;LruCache<String, Bitmap> lruCache = new LruCache<String, Bitmap>(CACNHE_SIZE);

1.4测量数据单元的内存占用

开发者需要重写 LruCache#sizeOf() 测量缓存单元的内存占用量，否则缓存单元的大小默认视为 1，相当于 maxSize 表示的是最大缓存数量。

// LruCache 内部使用
private int safeSizeOf(K key, V value) {// 如果开发者重写的 sizeOf 返回负数，则抛出异常int result = sizeOf(key, value);if (result < 0) {throw new IllegalStateException("Negative size: " + key + "=" + value);}return result;
}// 测量缓存单元的内存占用
protected int sizeOf(K key, V value) {// 默认为 1return 1;
}LruCache<String, Bitmap> lruCache = new LruCache<String, Bitmap>(CACNHE_SIZE){@Overrideprotected int sizeOf(String key, Bitmap value) {return value.getByteCount();}};

1.5 添加数据与淘汰数据

LruCache 添加数据的过程基本是复用 LinkedHashMap 的添加过程，我将过程概括为 6 步：

1、统计添加计数（putCount）；
2、size 增加新 Value 内存占用；
3、设置数据（LinkedHashMap#put）；
4、size 减去旧 Value 内存占用；
5、数据移除回调（LruCache#entryRemoved）;
6、自动淘汰数据：在每次添加数据后，如果当前缓存空间超过了最大缓存容量限制，则会自动触发 trimToSize() 淘汰一部分数据，直到满足限制。

淘汰数据的过程则是完全自定义，我将过程概括为 5 步：

1、取最找的数据（LinkedHashMap#eldest）；
2、移除数据（LinkedHashMap#remove）；
3、size 减去旧 Value 内存占用；
4、统计淘汰计数（evictionCount）；
5、数据移除回调（LruCache#entryRemoved）;
重复以上 5 步，满足要求或者缓存为空，才会退出。

疑问 1：为什么 LruCache 不支持 null 作为 Key 或 Value？

其实并没有一定不能为 null 的理由，我的理解是 Google 希望降低 LruCache 的理解成本。如果允许 Value 为 null，那么当 LruCache 需要计算 Value 的 size 时，Value 为 null 默认应该当作 0 还是当作 1呢？

再者，如果业务开发确实有 Key 或 Value 的需求，也可以选择重写 LruCache 的相关方法，或者直接自实现一个 LruCache，这都是可以接受的方案。例如，在 Android Glide 图片框架中的 LruCache 就是自实现的。

总结

1、LruCache 是 Android 标准库提供的 LRU 内存缓存框架，基于 Java LinkedHashMap 实现，当缓存容量超过最大缓存容量限制时，会根据 LRU 策略淘汰最久未访问的缓存数据；
2、LruCache 需要重写 sizeOf() 测量缓存单元的内存占用量，否则缓存单元的大小默认视为 1，相当于 maxSize 表示的是最大缓存数量；
3、LruCache 放弃了 LinkedHashMap#removeEldestEntry() 接口，而是自己实现了 trimToSize() 淘汰方法；