1.缓存策略
缓存策略主要包含缓存的添加、获取和删除三类操作。删除缓存是因为不管是内存缓存还是硬盘缓存，它们的缓存大小都是有限的。当缓存满了之后，再想添加缓存就需要删除一些旧的缓存来添加新的缓存。
LRU(Least Recently Used)缓存算法是近期最少使用的算法，它的核心思想是当缓存满时，会优先淘汰那些近期最少使用的缓存对象。关于Android的三级缓存，其中主要的就是内存缓存和硬盘缓存。这两种缓存机制的实现都应用到了LruCache算法。
2.LruCache
LruCache是Android 3.1提供的一个缓存类，在Android中可以直接使用LruCache实现内存缓存。而硬盘缓存DisLruCache目前还不是Android SDK的一部分，但Android官方文档推荐使用该算法来实现硬盘缓存。
LruCache是个泛型类，主要算法原理是把最近使用的对象用强引用存储在LinkedHashMap中。当缓存满时，把最近最少使用的对象从内存中移除，并提供了get和put方法来完成缓存的获取和添加操作。
LruCache的使用非常简单，以图片缓存为例：
int maxMemory=(int)(Runtime.getRuntime().ma xMemory()/1024);//获取系统分配给每个应用程序的最大内存
int cacheSize=maxMemory/8;
private LruCache<String, Bitmap> mMemoryCache;
//给LruCache分配1/8 最大内存
mMemoryCache = new LruCache<String, Bitmap>(mCacheSize){
//重写该方法，来测量Bitmap的大小
@Override
protected int sizeOf(String key, Bitmap value){
return value.getRowBytes() * value.getHeight()/1024;
}
};
①设置LruCache缓存的大小，一般为当前进程可用容量的1/8。
②重写sizeOf方法，计算出要缓存的每张图片的大小。
注意：缓存的总容量和每个缓存对象的大小所用单位要一致。
3.LruCache实现原理
LruCache的核心思想就是维护一个缓存对象列表，其中对象列表的排列方式按照访问顺序实现，即一直没访问的对象，将放在队尾，即将被淘汰，而最近访问的对象将放在队头，最后被淘汰。
如下图所示：
这个队列就是由LinkedHashMap维护的。LinkedHashMap由数组+双向链表的数据结构实现。其中双向链表的结构可以实现访问顺序和插入顺序，使得LinkedHashMap中的<key,value>对按照一定顺序排列起来。
通过下面构造函数来指定LinkedHashMap中双向链表的结构是访问顺序还是插入顺序。
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
其中accessOrder设置为true是访问顺序，为false是插入顺序。
以具体例子解释：
①当设置为true时
public static final void main(String[] args) {
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(0, 0.75f, true);
map.put(0, 0);
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);
map.put(6, 6);
map.get(1);
map.get(2);
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}
}
输出结果：
0:0
3:3
4:4
5:5
6:6
1:1
2:2
即最近访问的最后输出，这正好满足LRU缓存算法的思想。可见LruCache巧妙实现，就是利用了LinkedHashMap的这种数据结构。
下面在LruCache源码中具体看看，怎么应用LinkedHashMap来实现缓存的添加、获得和删除。
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);
}
从LruCache的构造函数中可以看到正是用了LinkedHashMap的访问顺序。
(1)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);
//向map中加入缓存对象
previous = map.put(key, value);
//如果已有缓存对象，则缓存大小恢复到之前
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//entryRemoved()是个空方法，可以自行实现
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//调整缓存大小(关键方法)
trimToSize(maxSize);
return previous;
}
put()方法最重要的就是在添加缓存对象后，调用trimToSize()方法来判断缓存是否已满，如果满了就要删除近期最少使用的算法。
trimToSize()方法：
public void trimToSize(int maxSize) {
while (true) { //死循环
K key;
V value;
synchronized (this) {
//如果map为空并且缓存size不等于0或者缓存size小于0，抛出异常
if (size < 0 || (map.isEmpty() && size != 0)){
throw new IllegalStateException( getClass().getName() + ".sizeOf() is reporting inconsistent results!");
}
//如果缓存大小size小于最大缓存，或者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++;
}
entryRemoved(true, key, value, null);
}
}
trimToSize()方法不断地删除LinkedHashMap中队尾的元素，即近期最少访问的，直到缓存大小小于最大值。
当调用LruCache的get()方法获取集合中的缓存对象时，就代表访问了一次该元素，将会更新队列，保持整个队列是按照访问顺序排序。这个更新过程就是在LinkedHashMap中的get()方法中完成的。
(2)get()方法
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//获取对应的缓存对象。get()方法会实现将访问的元素更新到队列头部的功能
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
}
其中LinkedHashMap的get()方法如下：
public V get(Object key) {
LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
if (e == null)
return null;
//实现排序的关键方法
e.recordAccess(this);
return e.value;
}
调用recordAccess()方法如下：
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//判断是否是访问排序
if (lm.accessOrder) {
lm.modCount++;
remove(); //删除此元素
//将此元素移动到队列的头部
addBefore(lm.header);
}
}
可见LruCache中维护了一个集合LinkedHashMap ，该LinkedHashMap是以访问顺序排序的。当调用put()方法时，就会在集合中添加元素，并调用trimToSize()判断缓存是否已满，如果满了就用LinkedHashMap的迭代器删除队尾元素，即近期最少访问的元素。当调用get()方法访问缓存对象时，就会调用LinkedHashMap的get()方法获得对应集合元素，同时会更新该元素到队头。