1. 概述
比较常用的一种缓存算法是LRU（Least Recently Used），LRU是近期最少使用算法，它的核心思想是当缓存满时，会优先淘汰那些近期最少使用的缓存对象。采用LRU算法的缓存有两种：内存缓存和磁盘缓存，LruCache用于实现内存缓存。
2. 使用
int cacheSize = (int) (Runtime.getRuntime().maxMemory() / 1024 / 8);//计算最大缓存大小（内存的1/8）
LruCache<String, Bitmap> lruCache = new LruCache<String, Bitmap>(cacheSize) {
@Override
protected int sizeOf(String key, Bitmap value) {//自定义每个 entry 大小的计算方法
return value.getByteCount() / 1024;
}
};
注：maxMemory 返回的单位是 字节。
3. 构造方法与成员变量
size 当前占用的内存大小
maxSize 允许的最大容量
这两个值指的是内存的大小，跟Entry的数量没有直接关系。
private final LinkedHashMap<K, V> map;//使用 LinkedHashMap 方便实现移除「最近最少使用的元素」
//每一个缓存实体的大小。不一定是元素的数量。
private int size;
private int maxSize;
private int putCount;//添加的数量
private int createCount;//创建的数量
private int evictionCount;//「赶出」的数量
private int hitCount;//命中次数
private int missCount;//不命中的次数
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
}
4. put 操作
android.support.v4.util.LruCache#put
/**
* 缓存{@code key}的{code}值。该值被移动到队列的头部。
*
* @return 原先 key 对应的值.
*/
public final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {//获取同步锁
putCount++;//put 数量+1
size += safeSizeOf(key, value);//当前占用的内存大小增加相应的单位
previous = map.put(key, value);//存储
if (previous != null) {//
size -= safeSizeOf(key, previous);//本来已经有这样的 Entry，需要减去旧 Entry
}
}
if (previous != null) {//移除旧值
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);//
return previous;
}
LruCache#safeSizeOf
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);//调用 sizeOf 方法，获取对应 Entry 的大小
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
/**
* Returns the size of the entry for {@code key} and {@code value} in
* user-defined units. The default implementation returns 1 so that size
* is the number of entries and max size is the maximum number of entries.
*
以用户定义的单位返回{@code key}和{code code}的 entry 大小。默认实现返回1，以便size是 entry 数量，max size是 entry 的最大数量。
* <p>An entry's size must not change while it is in the cache.
*/
protected int sizeOf(K key, V value) {
return 1;
}
LruCache#trimToSize
移除缓存中最不常使用的元素，直到低于指定的值。
/**
* 删除「最老的」 entries ，直到剩余 entries 的总数达到或小于参数 maxSize 的值。
* @param maxSize返回之前缓存的最大大小。可能是-1
* 驱逐即使是0大小的元素。
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
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);//移除 key 对应的 value
size -= safeSizeOf(key, value);//更新占用内存大小
evictionCount++;//「清除的数量」+ 1
}
entryRemoved(true, key, value, null);//通知元素已经被移除了
}
}
LruCache#maxSize
获取最大的缓存值
public synchronized final int maxSize() {
return maxSize;
}
5. get 操作
/**
* Returns the value for {@code key} if it exists in the cache or can be
* created by {@code #create}. If a value was returned, it is moved to the
* head of the queue. This returns null if a value is not cached and cannot
* be created.
*/
public final V get(K key) {
if (key == null) {//key 不能为空
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {//进入同步块
mapValue = map.get(key);//
if (mapValue != null) {
hitCount++;//命中次数+1
return mapValue;//返回
}
missCount++;//未命中的次数+1
}
/*尝试创建一个值。这可能需要很长时间，并且 create() 方法返回时map 可能已经出现了修改。如果 create（）方法正在工作时将冲突值添加到 map 中，则我们将该值保留在 map 中并释放创建的值。
*/
V createdValue = create(key);//默认实现中 create 返回null
if (createdValue == null) {
return null;
}
synchronized (this) {//进入同步块
createCount++;//创建次数+1
mapValue = map.put(key, createdValue);//将生成的值存储进去
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);//创建值期间，key 有对应的值 put 进来了，那么应该将它置为对应的值
} else {
size += safeSizeOf(key, createdValue);//
}
}
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);//通知 entry 被移除掉了
return mapValue;
} else {
trimToSize(maxSize);//保证内存占用小于最大的内存
return createdValue;
}
}
/**
* entry被移除之后会回调该方法。默认为空实现。
* 对参数 evicted 的说明：
* 如果删除条目以腾出空间，则 evicted 为 true;
* 如果删除是由 put或 remove 引起的，则为false。
*/
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
/**
* 在缓存未命中后调用，用于计算相应key的值。返回计算值，如果不能计算值的话，则返回null。默认实现直接返回null。
*
* 该方法可以在没有同步的情况下被调用：这意味着 其他线程可以在该方法执行时访问缓存。
*/
protected V create(K key) {
return null;
}
6. 清空缓存
/**
* 清空缓存
*/
public final void evictAll() {
trimToSize(-1); // -1 will evict 0-sized elements
}
7. 获取缓存的快照
/**
* 返回缓存中当前内容的副本，按照最近最少访问到最近访问的顺序排列。
*/
public synchronized final Map<K, V> snapshot() {
return new LinkedHashMap<K, V>(map);
}
8.总结
缓存的关键在于存储与淘汰。淘汰有一定的策略，LRUCache 中的淘汰策略是删除最近最少使用的元素。LRUCache 使用 LinkedHashMap 作为存储的容器，初始化 LinkedHashMap 的时候指定排序模式为按照访问顺序排序。每次 put 的完成的时候进行检查，如果缓存占用是否超出了指定的最大值，如果是，会淘汰掉最近最不常使用有的元素。
由于本人水平有限，可能出于误解或者笔误难免出错，如果发现有问题或者对文中内容存在疑问欢迎在下面评论区告诉我。谢谢！
