LrcCache是Android3.1所提供的一个缓存类。LruCache类是泛型类，主要算法原理是把最近使用的对象强引用（即我们平常使用的对象引用方式）存储在LinkedHashMap中。当缓存满时，把最近最少使用的对象从内存中移除，并提供了get和put方法来完成缓存的获取和添加操作。
1、LruCache的使用
lruCache的使用非常简单，以图片缓存为例
private LruCache mMemoryCache = null;
private void lrcCaheceInit() {
int maxMemory = (int) (Runtime.getRuntime().totalMemory() / 1024);
int cacheSize = maxMemory / 8;
mMemoryCache = new LruCache<String, Bitmap>(cacheSize) {
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getRowBytes() * value.getHeight() / 1024;
}
};
}
- 设置LruCache缓存的大小，一般为当前进程可用容量的1/8.
- 重写sizeOf方法，计算出要缓存的每张图片的大小。
注意：缓存的总量和每个缓存对象的大小所用单位要一致。
2、LruCache实现的原理
维护一个缓存对象的列表，其中对象列表的排序方式是按照访问的顺序实现的，即一直没有访问的对象，就放在队尾，即将被淘汰。而最近访问的对象放在队头，最后被淘汰。淘汰过程图：
该队列便是由linkedHashMap来维护。而LinkedHashMap则是由数组+双向链表的数据结构来实现的。其中双向链表的结构可以实现访问顺序和插入顺序，使得LinkedHashMap中的键值对，按照一定的顺序排列起来。
通过下面构造函数来指定LinkedHashMap中的结构是访问顺序还是插入顺序。
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
其中accessOrder设置为true则为访问顺序，false则为插入顺序。
具体例子解释，当设置为true时：
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来实现缓存的添加，获得和删除的。
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的访问顺序。
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) {
//插入的缓存对象加1
putCount++;
//增加已有的缓存大小
size += safeSizeOf(key, value);
//在map中加入缓存对象
previous = map.put(key, value);
//如果已有缓存对象，则缓存大小回复之前的大小
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//空方法，自行实现
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//调整缓存大小的关键方法
trimToSize(maxSize);
return previous;
}
put方法中，主要的就是添加缓存对象后，调用trimSize()方法，来判断是否缓存已满，如果满了就要删除近期最少使用的算法。
private 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!");
}
//如果缓存大小小于最大缓存，跳出缓存
if (size <= maxSize) {
break;
}
//遍历map集合，取队尾的元素，近期访问最少的元素
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);
}
}
trimToSize()方法不停地删除LinkedHashMap中队尾的元素，即近期最少访问的，知道缓存大小小于最大值。
当调用LruCache的get()方法获取缓存中的对象时，就代表了一次该元素，将会更新队列，保持整个队列是按照访问顺序排序。这个更新过程就是在LinkedHashMap中的get()方法中完成的。
get()方法：
public final V get(K key) {
//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) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
//实现排序的方法
afterNodeAccess(e);
return e.value;
}
afterNodeAccess()方法
void afterNodeAccess(Node<K,V> e) { // 将节点挪到队尾
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
由此，LruCache中维护了一个集合LinkedHashMap，该LinkedHashMap是以顺序排序的。当调用put()方法时，就会在集合中添加元素，并调用trimToSize()判断缓存是否已满。如果满了就删除最后的元素。当调用get()方法访问缓存的对象时，就调用LinkedHashMap的get()方法获得对应集合元素。同时更新该元素到队头。
