在上一次LruCache的学习中，了解到LruCache的实现主要依赖于LinkedHashMap，所以这次重点学习LinkedHashMap。
先看一个例子LinkedHashMap20171024，初步了解下HashMap，没设置accessOrder的LinkedHashMap和设置了accessOrder的LinkedHashMap的区别
Paste_Image.png
可看到HashMap是无续输出，没设置accessOrder的LinkedHashMap会根据第一次输入的key值的顺序输出，如果再输入相同key值的value，会覆盖之前的value，设置accessOrder的LinkedHashMap，会按照输入的先后顺序排列，最先输入的在前，如果再输入相同key值的value，会把他移到队尾。
再来看看LinkedHashMap的源码，LinkedHashMap，Android里有一套实现方法，Java里也有一套，实现上有些不同但思路是相同的，这里主要分析Android里的LinkedHashMap。
LinkedHashMap继承HashMap，基本操作与HashMap相似，只是通过重写父类相关的方法，来实现链表的特性
public class LinkedHashMap<K, V> extends HashMap<K, V> {
…
}
LinkedHashMap的构造函数
public LinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
//initialCapacity初始化空间大小
//loadFactor是加载因子，当他的size大于initialCapacity*loadFactor的时候就会扩容
super(initialCapacity, loadFactor);
init();
this.accessOrder = accessOrder;
}
/**
* A dummy entry in the circular linked list of entries in the map.
* The first real entry is header.nxt, and the last is header.prv.
* If the map is empty, header.nxt == header && header.prv == header.
*/
transient LinkedEntry<K, V> header;
@Override
void init() {
header = new LinkedEntry<K, V>();
}
/** Create the header entry */
LinkedEntry() {
super(null, null, 0, null);
nxt = prv = this;
}
初始化了一个header，他是双向环形链表的头，不存放任何数据，上面的注释说明第一个真正的entry是header的下一个，最后一个entry是header的前一个，如果为null，则他的前一个和后一个都等于header，因为他是个环形链表，所以header的下一个也是最先加入的，header的前一个是最后一个加入的。
Paste_Image.png
再来看一些方法：
- 获取最老的元素：
public Entry<K, V> eldest() {
LinkedEntry<K, V> eldest = header.nxt;
return eldest != header ? eldest : null;
}
由上图可以看到最先存放的元素是header的下一个，所以这里使用header.nxt就可以获得最老的元素
- 添加元素：
@Override void
addNewEntry(K key, V value, int hash, int index) {
LinkedEntry<K, V> header = this.header;//先找的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;
// new了一个新的LinkedEntry，然后在加入到table中
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
key, value, hash, table[index], header, oldTail);
// header的前一个元素就是新元素，也是最后一个加入的
table[index] = oldTail.nxt = header.prv = newTail;
}
