LruCache:
包名：android.support.v4.util
主要成员变量：
private final LinkedHashMap<K, V> map;
private int size;//当前缓存区的大小（根据该大小判断是否执行LRU算法）
private int maxSize;//缓存区总大小
private int putCount;//执行put()操作的次数
private int createCount;//执行create的次数
private int evictionCount;//
private int hitCount;//get()操作时，通过key直接取到value的次数(key进行哈希映射)
private int missCount;//get()操作时，通过key没有直接取到value的次数
构造方法：
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);
}
maxSize表示缓存中所能够存储的最大条目数。
对于LinkerHashMap的构造参数详解：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder)
InitialCapacity：初始缓存大小
loadFactory:加载因子
accessOrder:false->按照插入顺序排序 true->按照访问顺序排序(get一个元素后，就将该元素取出来保存到链表的最后，实现最近最少调度算法)
既然内部采用了LinkedHashMap这种数据结构，就表示对数据的处理采用到了链表的get()、put()、remove()等方法：
put():
/**
* Caches {@code value} for {@code key}. The value is moved to the head of
* the queue.
* value被移动到队列的头部
* @return the previous value mapped by {@code key}.
* 返回key映射的值
*/
public final V put(K key, V value) {
//key或value为null都导致空指针
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
//put计数自增
putCount++;
size += safeSizeOf(key, value);
//返回上一次的value对应的大小，此时previous已经被value替换掉
previous = map.put(key, value);
//由于previous被移除了，故而size也要做对应的删减
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
//需要重写，默认为空
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
trimToSize(maxSize);默认maxSize为初始化时赋值，一般取值为Runtime.getRuntime().maxMemory/8
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 || map.isEmpty()) {
break;
}
//缓存区域不够，LRU算法移除头部的value
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
size -= safeSizeOf(key, value);
//eviction次数加1
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
以上是put()操作的过程：首先，根据key到缓存中找相应的value，找到，进行替换，并把size的只进行相应的改变。将新的value替换oldValue之后，size的值发生了改变，故而，要对缓存区域的大小是否能够容纳新的size做出判断，不能的话将map中的元素根据LRU算法进行移除。
get(K key):
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
//字节取到value
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
*/
//create(key)如果不重写的话，直接返回null
V createdValue = create(key);
if (createdValue == null) {
return null;
}
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;
}
}
remove(K key)
/**
* Removes the entry for {@code key} if it exists.
*
* @return the previous value mapped by {@code key}.
*/
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;
}
remove()方法和put()方法大致是一样的。见put()方法分析。
LruCache采用LinkedHashMap数据结构，双链表的pre和next指针分别指向上一个和下一个node的地址，hash算法保证了存取操作的效率。LinkedHashMap的成员变量accessOrder保证了插入的规则，true是基于访问顺序，这保证了最近操作的元素存放在了链表的末尾，删除的元素都是最久时间未使用的。这种思想值的学习。
另外看一看accessOrder在LinkedHashMap中的作用：
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
//将链表的tail赋值给last
if (accessOrder && (last = tail) != e) {
//强转e，并给其设置before指针和after指针，分别为b和a
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
p.after = null;
//若节点e的before不存在，则e的next为链表的头部，因为我们的目标是把节点e断开，然后放到链表的尾部
if (b == null)
head = a;
else
b.after = a;
//e已经断开，需要把e的before和after再次连接起来，形成一条链
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
