Least Recently Used => LRU:最近最少使用算法
为什么使用LRUcache？
Android2.3开始，GC更倾向于回收弱引用和软引用，变得不可靠。
Android3.0中，图片的数据会存储在本地的内存当中，限制值的数量. 每当值被访问的时候，它会被移动到队列的头部. 当缓存空间已满加入在新的值时，队列中最后的值会出队，可能被回收。
原理：
LruCache 使用一个 LinkedHashMap 简单的实现内存的缓存，没有软引用，都是强引用。如果添加的数据大于设置的最大值，就删除（最近最少使用）最先缓存的数据来调整内存。
maxSize 是通过构造方法初始化的值，最大缓存值。
size 在添加和移除缓存都被更新值，他通过 safeSizeOf 这个方法更新值。safeSizeOf方法内部调用的sizeOf方法默认返回 1，但一般我们会根据 maxSize 重写这个方法，比如认为 maxSize 代表是 KB 的话，那么就以 KB 为单位返回该项所占的内存大小。
除异常外首先会判断 size 是否超过 maxSize，如果超过了就取出最先插入的缓存，如果不为空就删掉，并把 size 减去该项所占的大小。这个操作将一直循环下去，直到 size 比 maxSize 小或者缓存为空。
public class LruCache<K, V> {
private final LinkedHashMap<K, V> map;//LinkedHashMap双链表集合
/** Size of this cache in units. Not necessarily the number of elements. */
private int size;//内存占用大小
private int maxSize;//最大内存占用
private int putCount;//添加的次数
private int createCount;//创建的次数
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是实现Lru算法的关键
//初始容量为0
//达到最大容量的75%时，会增加内存一半
//排序方式：true表示按访问顺序排序，访问的值会被排在最后面，反之最前面是最近最少使用的值，flase表示按添加顺序
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++;//添加次数+1
size += safeSizeOf(key, value);//计算value大小
previous = map.put(key, value);//添加进集合
//如果当前key的值存在，减去这条值得大小
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//entryRemoved是一个空实现，如果我们使用LruCache的时候需要掌握元素移除的信息，可以重写这个方法。
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//整理内存空间，如果储存空间（size）>最大储存空间(maxSize)，循环删除最近最少使用的值
trimToSize(maxSize);
return previous;
}
//计算安全空间
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);//sizeOf需要被重写，返回实际的大小
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
//整理内存空间
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;
}
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);
}
}
看完put，那下面来看看get：
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//根据kay获取value值
mapValue = map.get(key);
//值存在
if (mapValue != null) {
hitCount++;//命中+1
return mapValue;
}
missCount++;//丢失+1
}
/*
* 值不存在，创建，如果值为null，则返回null
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//createdValue不为null
synchronized (this) {
createCount++;//创建+1
//添加新值进map
mapValue = map.put(key, createdValue);
//如果mapValue存在值，有冲突，所以撤消put操作
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
//更新储存空间
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
//返回存在的值
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
//返回创建的值
trimToSize(maxSize);//整理内存空间
return createdValue;
}
}
最后说一下remove方法：
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;
}
