前言
LRU及Least Recently Used, 最近最少使用算法, 也就是当内存缓存达到设定的最大值时将内存缓存中近期最少使用的对象移除，有效的避免了OOM的出现.
上篇文章我们看了LinkedHashMap的源码, 通过LinkedHashMap可以很方便的获取最少使用的元素, 而LRUCache也就是通过LinkedHashMap来实现的, 下面来看下LRUCache的代码.
源码
- 注释
/**
* A cache that holds strong references to a limited number of values. Each time
* a value is accessed, it is moved to the head of a queue. When a value is
* added to a full cache, the value at the end of that queue is evicted and may
* become eligible for garbage collection.
*
* <p>If your cached values hold resources that need to be explicitly released,
* override {@link #entryRemoved}.
*
* <p>If a cache miss should be computed on demand for the corresponding keys,
* override {@link #create}. This simplifies the calling code, allowing it to
* assume a value will always be returned, even when there's a cache miss.
*
* <p>By default, the cache size is measured in the number of entries. Override
* {@link #sizeOf} to size the cache in different units. For example, this cache
* is limited to 4MiB of bitmaps:
* <pre> {@code
* 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();
* }
* }}</pre>
*
* <p>This class is thread-safe. Perform multiple cache operations atomically by
* synchronizing on the cache: <pre> {@code
* synchronized (cache) {
* if (cache.get(key) == null) {
* cache.put(key, value);
* }
* }}</pre>
*
* <p>This class does not allow null to be used as a key or value. A return
* value of null from {@link #get}, {@link #put} or {@link #remove} is
* unambiguous: the key was not in the cache.
*
* <p>This class appeared in Android 3.1 (Honeycomb MR1); it's available as part
* of <a href="http://developer.android.com/sdk/compatibility-library.html">Android's
* Support Package</a> for earlier releases.
*/
总结一下注释中提到的几点信息:
- LRUCache是一个持有有限数据的强引用. 每次访问元素, 该元素就会被移到队列头部. 队列满了之后再次添加元素, 就会回收队列尾部的元素.
- 如果缓存的值持有的资源需要被彻底释放, 需要重写entryRemoved进行释放操作.
- 重写create方法, 这样缓存即使丢失也总能被返回.
- 默认的缓存占用大小是缓存对象的个数, 需要重写sizeOf计算不同缓存对象所占的大小.
- LRUCache是线程安全的.
- 不允许使用空的key和value.
- 出现在Android3.1, 也在Android Support包中兼容早期版本.
- 变量及构造方法
public class LruCache<K, V> {
private final LinkedHashMap<K, V> map;
private int size;//内存占用大小
private int maxSize;//缓存最大容量
private int putCount;//put的次数
private int createCount;//create的次数
private int evictionCount;//回收的次数
private int hitCount;//get到的次数
private int missCount;//未get到的次数
//构造函数中传入最大缓存容量
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
//初始化LinkedHashMap, 扩充因子为0.75, accessOrder为true, 按访问顺序排列, 方便获取最老的元素
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
}
- put
public final V put(K key, V value) {
//key和value都不能为空
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
putCount++;
size += safeSizeOf(key, value);//size累加该对象缓存大小
previous = map.put(key, value);//获取key对应的之前的值
//不为空, size要减去之前的值所占的缓存大小
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//key之前对应的有值, 通知旧值被替换
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//重新计算是否超过最大容量
trimToSize(maxSize);
return previous;
}
private int safeSizeOf(K key, V value) {
//获取该对象缓存大小
int result = sizeOf(key, value);
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
//需要重写该方法, 设置每个缓存对象的大小, 默认为1
protected int sizeOf(K key, V value) {
return 1;
}
//当entry对象被回收或删除或替换时, 通过此方法回调出去
//evicted: 是否被回收 oldValue: key对应的旧值 newValue:key对应的新值
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {
}
LRUCache的put操作就是在LinkedHashMap的put操作上增加了缓存大小的计算和是否超出最大容量的计算, 如果超出就删除最旧的缓存对象.
- trimToSize
计算缓存是否超出最大值.
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) {
break;
}
//缓存容量超出最大值之后, 通过LinkedHashMap获取最旧的元素
Map.Entry<K, V> toEvict = map.eldest();
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);// 删除最旧的元素
size -= safeSizeOf(key, value);//重新计算缓存大小
evictionCount++;//增加回收次数
}
//回调通知回收了最旧的元素
entryRemoved(true, key, value, null);
}
}
- get
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//map获取到key对应的值之后直接返回
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
//如果map中没有获取到, 判断用户是否重写create来创建对象
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//如果用户重写了create创建对象
synchronized (this) {
createCount++;
//把key和新创建的对象存入map, 并获取key对应的之前的对象
mapValue = map.put(key, createdValue);
//如果key对应的之前的对象不为空, 再重新把之前的值存入map
//因为create可能需要一段时间, 多线程访问时可能会有key对应旧值不为空的情况, 所以保存旧值, 放弃新值
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {//key对应旧值为空, 累加缓存大小
size += safeSizeOf(key, createdValue);
}
}
//key对应旧值不为空, 缓存大小不不变, 通知删除新值, 返回旧值
if (mapValue != null) {
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {//key没有对应旧值, 重新计算是否超出最大值, 返回新值
trimToSize(maxSize);
return createdValue;
}
}
get就是通过LinkedHashMap获取key对应的value, 有则直接返回, 没有则创建, 如果创建了新value就加入LinkedHashMap, 重新计算缓存大小, 重新计算是否超出最大缓存.
- remove
public final V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
//删除key对应的value
previous = map.remove(key);
//key对应value不为空, 删除之后要重新计算缓存大小
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//key对应value不为空, 删除之后, 通知删除了该value
if (previous != null) {
entryRemoved(false, key, previous, null);
}
return previous;
}
remove操作也很简单, 通过LinkedHashMap删除key对应value之后重新计算缓存大小.
- resize
public void resize(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
synchronized (this) {
this.maxSize = maxSize;
}
trimToSize(maxSize);
}
很简单, 就是重新设置缓存最大值, 重新计算当前缓存是否超出最大值.
基本操作就这些, 是不是很简单, 存取都是通过LinkedHashMap来操作的, 只不过多了缓存大小的计算, 以及是否超出最大缓存的计算, 如果超出最大缓存, 就把最少使用的对象删除.
原理清楚了, 具体使用可以参考大神的照片墙
网友评论