前言
在Android 2.2以上的sdk中提供了缓存类LruCache。LruCache用于内存缓存，常用的应用场景有很多，比如我们的图片加载库的内存缓存就可以利用LruCache来实现，今天我们一起来学习一下LruCache的源码。
LruCache简介
LruCache里实现的是LinkedHashMap类，并且是LinkHashMap里所有的Entry按照访问的顺序排列，根据设置的缓存大小，如果缓存已满，移除最近最少访问的Entry。
源码分析
LruCache源码
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对象，下面看下LinkedHashMap的源码：
public class LinkedHashMap<K,V>{ extends HashMap<K,V> implements Map<K,V> /** * 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; /** * The iteration ordering method for this linked hash map: <tt>true</tt> * for access-order, <tt>false</tt> for insertion-order. * * @serial */ final boolean accessOrder; /** * Constructs an empty <tt>LinkedHashMap</tt> instance with the * specified initial capacity, load factor and ordering mode. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @param accessOrder the ordering mode - <tt>true</tt> for * access-order, <tt>false</tt> for insertion-order * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } }LinkedHashMap基本结构是HashMap+LinkedList,也就是说,它使用HashMap操作数据结构,也用LinkedList维护插入元素的先后顺序
LinkedHashMap集成了HashMap，实现了Map的接口
LinkedHashMap
LinkedHashMap的构造函数中，传入的accessOrder是什么意思
false, 所有的Entry按照插入的顺序排列 true, 所有的Entry按照访问的顺序排列LruCache传入的是true，所以是按照访问顺序排列
LinkedHashMap和HashMap的区别在于他们的基本数据机构上,我们来看一下LinkedHashMap的基本数据结构Entry:
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); } }HashMap的基本数据结构
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next;LinkedHashMap比HashMap多了两个属性LinkedHashMapEntry<K,V> before, after;
next是用于维护HashMap指定table位置上连接的Entry顺序;before、after是用于维护Entry插入的先后顺序.
因为head、before、after，使LinkedHashMap形成了环形双向链表
而head是LinkedHashMap的节点，是环形链表的入口，不保存数据
LinKedHashMap是如何保存数据呢？
LinKedHashMap没有直接实现put方法，是在HashMap里实现
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ 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 //如果key在map中存在，替换新的value，并将替换后的Entry放入队列尾部 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的时候初始化head，并将链表的刚加入的放到tail中
HashMap中put数据的时候调用newTreeNode final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { ..... TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { Node<K,V> xpn = xp.next; TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); if (dir <= 0) xp.left = x; else xp.right = x; xp.next = x; x.parent = x.prev = xp; if (xpn != null) ((TreeNode<K,V>)xpn).prev = x; moveRootToFront(tab, balanceInsertion(root, x)); return null; } } } LinkedHashMap中对newTressNode是实现 TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); linkNodeLast(p); return p; } //将新加入的数据放到链表的tail(链尾) private void linkNodeLast(LinkedHashMapEntry<K,V> p) { LinkedHashMapEntry<K,V> last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } }前面都是从获取key对应的链表中的Entry，看下这三个方法是干嘛的
// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { }HashMap(应该是Java1.8版本以上)中声明了三个空实现的方法，备注是Callbacks toallow LinkedHashMap post-actions
应该是在LinkedHashMap分别实现了这三个方法
LinkedHashMap中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; } }LinkedHashMap中afterNodeInsertion实现如下代码
首先 声明一个first的对象，将head赋值给first，获取first的key，调用removeNode方法
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMapEntry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } }再看看removeNode放在HashMap中实现如下：
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }该方法实现了Map.remove及相关的方法，其中调用了这个afterNodeRemoval，该方法在LinkedHashMap中实现如下：
void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; }相当于是将LinkedHashMap的链表进行循环连起来，传进来的相当于是一个head，将p的前面entry放在tail(链尾)，将p的后面entry放在head(链头)
添加缓存数据总结：首先根据Key获取Hashmap中的是否存在，如果存在获取对应的链表节点，如果不存在新建一个节点，将该节点放入到链表尾部，并判断该链表是否已超出缓存，如果超出缓存，删除链表头的节点
获取缓存：
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方法，是将key对应的链表节点移到链表尾部，这样链表尾部就是最新访问的数据
