LruCache
LruCache是Android提供的基于最近最少使用算法的缓存策略，该策略根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
LruCache的原理是在内部由LinkedHashMap维护了一个队列，队列按照访问时间排序，head访问时间最早，tail访问时间最晚。当队列长度超过设置的最大长度时，则从head开始挨个删除，直到长度符合要求。
LruCache源码解析
从LruCache常用的几个方法入手分析。
- 构造函数
private final LinkedHashMap<K, V> map;
/** Size of this cache in units. Not necessarily the number of elements. */
private int size;
private int maxSize;
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，在构造函数中初始化，并指定maxSize，maxSize指的是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) {
putCount++;
size += safeSizeOf(key, value); //safeSizeOf用来计算新增的条目的size，默认是1
previous = map.put(key, value);
if (previous != null) { //如果存在旧的数据，减去旧的数据的size
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value); //缓存被移除时调用，默认为空实现
}
trimToSize(maxSize); //将超出maxSize的数据移除
return previous;
}
put方法只是将数据put到LinkedHashMap中，然后计算新的size值，并检查是否超过maxSize，如果超过的话，将队头（最后访问时间最早）的数据依次删除。
- get
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) {
hitCount++;
return mapValue;
}
missCount++;
}
//map找不到的话，尝试创建一个，create默认返回null，所以一般情况下只执行到这里就结束了。
V createdValue = create(key);
if (createdValue == null) {
return null;
}
//如果createdValue不为空的话，就put到LinkedHashMap中，如果map中已经有值，就撤销put操作
synchronized (this) {
createCount++;
mapValue = map.put(key, createdValue);
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;
}
}
get方法先从LinkedHashMap中获取数据，如果存在值则返回。如果不存在值，则调用create方法，如果create方法没有被重写则返回null。如果被重写了，会创建一个createdValue，并put到LinkedHashMap中，如果与原有的值冲突了，就撤销put操作，如果没有冲突，就put到map中，并更新size。
- 排序
看完LruCache的代码，可以知道，缓存数量超出限制之后，从队头挨个删除。看起来平平无奇，那么LruCache在哪里排序以实现LRU的效果呢。这就需要看一下LinkedHashMap了。
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMapEntry<K,V> tail;
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
LinkedHashMap是双向链表，head保存的是最老的数据，而tail保存的是最年轻的数据。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
从上面的代码可以看出来，在put的时候，如果之前不存在当前key，则添加在队尾。如果之前已经存在当前key，替换成新的Value。然后会调用afterNodeAccess。
void afterNodeAccess(Node<K,V> e) { // move node to last
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;
}
}
在afterNodeAccess中一顿链表的操作，最后把p挪到了队尾。因此，可以确定执行完put方法之后，新的value一定在队尾。再回头看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;
}
在get方法中同样通过afterNodeAccess方法将该Node挪到队尾。因此可以实现LinkedHashMap按访问时间进行排序。
