提到Android的缓存策略
任何一个Android开发人员都能随口说出LruCache
,利用最新最少使用(Least Recently Used)
的原则进行缓存,可LRU
到底是怎么实现的呢?
LruCache简介
LruCache是个泛型类,主要算法原理是把最近使用的对象用强引用(即我们平常使用的对象引用方式)存储在 LinkedHashMap 中
。当缓存满时,把最近最少使用的对象从内存中移除,并提供了get
和put
方法来完成缓存的获取和添加操作。
实现原理
LruCache内部维护的是一个LinkedHashMap
,最近最少的算法判断逻辑都是由LinkedHashMap来实现,如果对LinkedHashMap原理不了解的童鞋,可以先了解下LinkedHashMap的原理分析这篇文章。
初始化
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; //未命中次数
/**
* @param maxSize for caches that do not override {@link #sizeOf}, this is
* the maximum number of entries in the cache. For all other caches,
* this is the maximum sum of the sizes of the entries in this cache.
*/
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);
}
put
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++;
size += safeSizeOf(key, value); //size加上预put对象的大小
previous = map.put(key, value);
if (previous != null) {
//如果之前存在键为key的对象,则size应该减去原来对象的大小
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//每次新加入对象都需要调用trimToSize方法看是否需要回收
trimToSize(maxSize);
return previous;
}
由上面的代码可以看出来,首先把size
增加,然后判断是否以前已经有元素,如果有,就更新当前的size,并且调用entryRemoved
方法,entryRemoved是一个空实现,如果我们使用LruCache的时候需要掌握元素移除的信息,可以重写这个方法。最后就会调用trimToSize
,来调整集合中的内容。
trimToSize 方法
/**
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
* 此方法根据maxSize来调整内存cache的大小,如果maxSize传入-1,则清空缓存中的所有对象
*/
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!");
}
//如果当前size小于maxSize或者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++; //回收次数+1
}
entryRemoved(true, key, value, null);
}
}
这个方法是一个无限循环,跳出循环的条件是,size < maxSize
或者 map 为空
。主要的功能是判断当前容量时候已经超出最大的容量,如果超出了maxSize的话,就会循环移除map中的第一个元素
,直到达到跳出循环的条件。由上面的分析知道,map中的第一个元素就是最近最少使用的那个元素。
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.
* 通过key获取相应的item,或者创建返回相应的item。相应的item会移动到队列的尾部,
* 如果item的value没有被cache或者不能被创建,则返回null。
*/
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
//mapValue不为空表示命中,hitCount+1并返回mapValue对象
hitCount++;
return mapValue;
}
missCount++; //未命中
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
* 如果未命中,则试图创建一个对象,这里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;
}
}
这个方法就先通过key来获取value,如果能获取到就就直接返回,获取不到的话,就调用create()
方法创建一个,事实上,如果我们不重写这个create方法的话是return null
的,所以整个流程就是获取得到就直接返回,获取不到就返回null
。
不要以为LruCache
是多么复杂的一个算法,看过之后是不是感觉也就那么回事?-