title: LruCache解析
date: 2016-03-29
tags: LruChche
LruCache
LruCache,最近最少使用缓存算法，乍一听好复杂的算法，还得记录和比较使用次数啥的，看来源码才知道，原来只是名字挺唬人。
LruCache是一种保持一定数量values（被缓存的值）的强引用的缓存。每次缓存value的时候，它会移到队列的头部。当一个value添加到一个已经满的缓存的时候，那个队列最后的value会被抛弃并且这时候最后的value可以被垃圾回收。如果缓存的values持有的资源需要明确的释放，重写entryRemoved方法来释放持有的资源。
如果一个cache miss(缓存未命中)的时候需要得到key值相对应的value，重写create()方法.即使有一个cache miss，也允许一直返回一个它假定的值,这是为了简化调用代码，
默认情况下，缓存大小通过entries的数量来计算。重写sizeOf方法按不同的单位来计算缓存。比如：
int cacheSize = 4 * 1024 * 1024; // 4MiB
LruCache<String, Bitmap> bitmapCache = new LruCache<String, Bitmap>(cacheSize) {
protected int sizeOf(String key, Bitmap value) {
return value.getByteCount();
}
}}
这个类是线程安全的。执行多个缓存操作会原子的按以下同步缓存。
synchronized (cache) {
if (cache.get(key) == null) {
cache.put(key, value);
}
}}
这个类不允许key或value为null。从get,put,remove返回的null表示key不存在
从android3.1开始出现
LruCache<K,V>构造方法传入缓存的最大值，内部使用LinkedHashMap<K,V>来保存缓存的值
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);
}
/**
* @hide
*/
public void resize(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
synchronized (this) {
this.maxSize = maxSize;
}
trimToSize(maxSize);
}
```
get方法，如果在缓存中存在或者可以通过create方法创建的，返回key对应的value值。如果value返回了，它会移到队列的头部。如果这个value没有被缓存或不能被创建，返回null.
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);//从hashmap中获取key对应的缓存值。
if (mapValue != null) {
hitCount++;//不为空，缓存命中加1
return mapValue;
}
missCount++;//若为空缓存未命中加1
}
/*
缓存未击中之后会将该值加入到map中。接下来会尝试通过用户重写的create方法创建一个value。这个创建过程可能会花好久，当create（）返回的时候map可能会变的有所不一样。
当create()执行的时候，如果map中添加了一个冲突的value,那么不管map中的value，将刚创建的value释放掉。
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);//hashmap put方法，返回key之前对应的值
if (mapValue != null) {
// 这有一个冲突，所以撤销最后一次put，也就是将之前的值再put回去。
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {//释放刚刚创建的value持有的资源。
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
trimToSize(maxSize);
return createdValue;
}
}
put方法，被添加的value会移动到队列的头部，返回key之前映射的value
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计数器
size += safeSizeOf(key, value);
previous = map.put(key, value);
if (previous != null) {//key之前有对应的值
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {//释放之前value持有的资源。
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
trimToSize方法。移除最老的entries直到所有剩余的entries在要求的大小之内。maxSize 在返回之前最大缓存值。
private 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) {
break;
}
// 获取到linked列表的最后一项
// 不同版本，这得实现可能不同
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
remve方法，返回key对应的value
public final V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
previous = map.remove(key);
if (previous != null) {//成功移除，修改缓存当前大小
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {//释放资源
entryRemoved(false, key, previous, null);
}
return previous;
}
entryRemoved方法。已经被驱逐或被移除的entries会调用这个方法。当一个value被驱逐来释放空间，调用remove来移除或者调用put方法替换的时候会调用这个方法。默认实现什么都不做。方法调用的时候没有同步：在这个方法执行的时候其他线程可以访问缓存。evicted参数：如果entry被移除来释放空间返回true,如果移除是因为put方法或remove方法返回false。newValue参数表示key对应的新的value(如果存在的话).这个值如果不为空，是因为put引起的。否则的话是驱逐或remove引起的
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}
create方法。在缓存未中之后调用来计算key映射的value.方法调用的时候没有同步：在这个方法执行的时候其他线程可以访问缓存。当这个方法返回的时候，如果key对应的value在cache中存在，创建的value会通过entryRemove()释放并丢弃。当多个线程在同一时间请求相同的key的时候（引起多个values被创建），或者当一个线程调用put方法另一个正在为这个key创建一个value可能会发生这种情况
protected V create(K key) {
return null;
}
safeSizeOf方法，检测用户重写的sizeOf方法的返回值是否合法。
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
sizeOf方法按用户定义的单位返回entry的大小。默认实现是返回1，这时候size表示entris的数量，max size表示entries的最大数量。entry的大小在缓存期间不能改变
protected int sizeOf(K key, V value) {
return 1;
}
/**
* 清空缓存
*/
public final void evictAll() {
trimToSize(-1);
}
size方法，final类型，不能被子类重写。如果缓存没有重写sizeOf()方法，这个方法返回缓存中entries的数量。对于其他的缓存，这个返回缓存中entries大小的和。
public synchronized final int size() {
return size;
}
snapshot方法返回当前缓存内容的拷贝，按照最近最少使用到最近最多使用的顺序。
public synchronized final Map<K, V> snapshot() {
return new LinkedHashMap<K, V>(map);
}
总之，LruCache内部使用LinkedHashMap来保存缓存的值。初始化的时候传入缓存的最大值或者缓存的最大个数（如果sizeOf方法返回1的话）。如果重写来create方法，在使用get方法的时候，如果缓存不存在，就将新创建的value加入到缓存中，这样就不用再次使用put来加入缓存了（因为create不是线程安全的，所以，创建成功之后是否应该加入缓存还需要再判断一下）。