一、LruCache概念
在设计缓存时，当空间达到一个临界值，需要淘汰一批数据，常用数据淘汰算法，比如。
先进先出算法FIFO，按照在缓存中的时间决定淘汰者，淘汰时间最长者。
最近使用最少算法LRU，最少是使用的数据先淘汰。
最近使用频率算法LFU，在一定时间，使用次数最少的数据淘汰。
在Android图片加载框架，Bitmap图片的缓存LruCache，使用的算法LRU，内部的存储结构是LinkedHashMap，LinkedHashMap继承HashMap，数组+双向链表。
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);
}
构造方法，创建一个LinkedHashMap对象，初始化容量是0，加载因子0.75，当容量大于75%总量时，扩充，继承HashMap的特性。
public final V get(K key) {
//key不允许空。
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
...
}
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);
//previous是之前的值
previous = map.put(key, value);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
trimToSize(maxSize);
return previous;
}
通过内部LinkedHashMap实现缓存，HashMap不是线程安全的结构，访问时加上synchronized同步。put方法，最后有个trimToSize方法，如果LinkedHashMap的size已经达到maxSize最大值，从LinkedHashMap中找到最少使用的元素，删除，腾地方，在LinkedHashMap结构中，最少使用的元素放在链表尾部，eldest就是LinkedHashMap双向链表头部节点。
public Entry<K, V> eldest() {
LinkedEntry<K, V> eldest = header.nxt;
return eldest != header ? eldest : null;
}
说明这个双向链表是有序的，按照数据的使用频率，从尾到头排序，最不常用在头部，最常用插入尾部。
二、LinkedHashMap原理
基类HashMap。
public LinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
init();
this.accessOrder = accessOrder;
}
accessOrder标志表示按照访问顺序排序，最先访问的排在前面LRU算法，如果没有该标志，表示按照插入顺序排序FIFO算法。
@Override
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null)
return null;
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
}
return null;
}
根据键值key计算哈希值，查找HashMapEntry数组索引，遍历索引处HashMapEntry链表，找到和key值完全相等的节点，返回它的value值。查找流程和HashMap相同，如果有accessOrder标志，执行一次makeTail方法。将访问的HashMapEntry节点移到双向链表尾部，即header前面。具体意思就是，若get访问到这一项，就将该项放到尾部，如果构造方法未传入accessOrder字段，不需要操作，插入后位置不变。这种操作将经常访问的节点放在尾部，不常使用的节点放在头部，方便删除不常用节点。
LinkedHashMap内部节点是LinkedEntry，继承HashMapEntry，增加nxt和prv引用，节点变成双向，存入数据时采用父类HashMap的put方法，重写addNewEntry方法。
@Override
void addNewEntry(K key, V value, int hash, int index) {
LinkedEntry<K, V> header = this.header;
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
key, value, hash, table[index], header, oldTail);
table[index] = oldTail.nxt = header.prv = newTail;
}
将新节点放到数组索引链表头部位置，LinkedEntry节点是双向链表结构，在整个双向链表中插入位置在尾部。LinkedHashMap数据存储结构。
- 索引0增加对象的情况，当前索引index=0处空，不存在对象，新增一个对象插到header前面(黄色节点)，即尾部，建立前后指针连接关系，并将该对象放入index=0位置，红线引用。
- 索引8增加对象的情况：当前索引index=8处已经有一个对象(红色节点)，新增一个对象插到header前面(黄色节点)，即尾部，建立前后指针连接关系，并将新对象放入index=8位置，红线引用1，并指向之前索引8处的节点，红线引用2，虚线为index=8的原引用。
三、总结
LruCache内部采用LinkedHashMap数组+双向链表存储结构，保留HashMap数组元素的链表形式，同时，所有节点加上pre和next指针，改装成一个双向链表，使节点集合全部链接。
LruCache的双向链表按照访问顺序(get)排序，经常访问的和新插入的节点放置在链表尾部，不经常访问的节点慢慢会移到头部，当到达最大值时，从头部开始删除。
任重而道远
