LinkedHashMap概述
LinkedHashMap是一个关联数组、哈希表，它是线程不安全的，允许key为null,value为null。它继承自HashMap，实现了Map<K,V>接口。其内部还维护了一个双向链表，在每次插入数据，或者访问、修改数据时，会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序。
默认情况，遍历时的顺序是按照插入节点的顺序。这也是其与HashMap最大的区别。也可以在构造时传入accessOrder参数，使得其遍历顺序按照访问的顺序输出。
因继承自HashMap, 除了输出无序，其他LinkedHashMap都有，比如扩容的策略，哈希桶长度一定是2的N次方等等。LinkedHashMap在实现时，就是重写override了几个方法。以满足其输出序列有序的需求
数据结构
假设图片中红黄箭头代表元素添加顺序，蓝箭头代表单链表各个元素的存储顺序。head 表示双向链表头部，tail 代表双向链表尾部
如图元素插入顺序:1->2->3->4->5->6 存储顺序:1->2->3->13->14->4(跟HashMap一致)
LinkedHashMap 底层结构还是数组 + 单链表 + 红黑树（JDK1.8之后），存储结构并没有发生变化。
唯一变化的是使用双向链表（图中红黄箭头部分）记录了元素的添加顺序，我们知道 HashMap 中的 Node 节点只有 next 指针，对于双向链表而言只有 next 指针是不够的，所以 LinkedHashMap 对于 Node 节点进行了拓展：
成员变量
/**
* Entry是LinkedHashMap静态内部类，继承了HashMap.Node<K,V>类，在Node类的基础上增加了before、
* after节点用来构成双向循环链表。
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
/**
* 双向链表的的头结点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 双向链表的的尾结点
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* accessOrder用来区分对LinkedHashMap中元素的顺序。accessOrder为false时（默认为false），按照插
* 入顺序，accessOrder为true时，按照访问顺序(不是存储顺序)。
*/
final boolean accessOrder;
- accessOrder若为false，遍历双向链表时，是按照插入顺序排序。
- accessOrder若为true，表示双向链表中的元素按照访问的先后顺序排列，最先遍历到（链表头）的是最近最少使用的元素。
构造函数
public LinkedHashMap() {
super();
accessOrder = false;
}
//指定初始化时的容量，
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//指定初始化时的容量，和扩容的加载因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//指定初始化时的容量，和扩容的加载因子，以及迭代输出节点的顺序
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//利用另一个Map 来构建，
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
构造函数和HashMap相比，就是增加了一个accessOrder参数。用于控制迭代时的节点顺序。
获取元素
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
// 将当前被访问到的节点e，移动至内部的双向链表的尾部
afterNodeAccess(e);
return e.value;
}
get方法重写了HashMap中get方法。不同的时候，在查找出元素后，如果当前是按照元素访问顺序的模式，这里会通过调用afterNodeAccess方法把元素添加至链表的尾部。（因为按照元素访问的模式中，会按照访问效率排序，最少访问的靠前，最新访问的靠后。）
添加元素
LinkedHashMap 并没有覆写任何关于 HashMap put 方法。所以调用 LinkedHashMap 的 put 方法实际上调用了父类 HashMap 的方法.但是其重写了构建新节点的newNode()方法。newNode()会在HashMap的putVal()方法里被调用（HashMap中put方法调用putVal方法）
LinkedHashMap重写了newNode(),在每次构建新节点时，通过linkNodeLast(p);将新节点链接在内部双向链表的尾部。
//在构建新节点时，构建的是`LinkedHashMap.Entry` 不再是`Node`.
// LinkedHashMap newNode方法重写了 HashMap的 newNode方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
//将新增的节点，连接在链表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
//集合之前是空的
if (last == null)
head = p;
else {//将新节点连接在链表的尾部
p.before = last;
last.after = p;
}
}
以及HashMap专门预留给LinkedHashMap的afterNodeAccess() afterNodeInsertion() afterNodeRemoval() 方法。
// HashMap中的预留方法没有逻辑实现
void afterNodeAccess(Node<K,V> p) { } //将当前节点，移动至内部的双向链表的尾部
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
HashMap的putVal方法中会涉及到newNode afterNodeAccess afterNodeInsertion方法。
//回调函数，新节点插入之后回调根据evict和判断是否需要删除最老插入的节点。
// 如果实现LruCache 最近最少使用缓存会用到这个方法。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//LinkedHashMap 默认返回false 则不删除节点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//LinkedHashMap 默认返回false 代表不删除节点。 返回true 代表要删除最早的节点。通常构建一个LruCache的时候 会在达到Cache的上限是返回true
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
void afterNodeInsertion(boolean evict)以及boolean removeEldestEntry(Map.Entry<K,V> eldest)是构建LruCache需要的回调(很重要)，在LinkedHashMap里可以忽略它们。
删除元素
如插入操作一样，LinkedHashMap 没有重写 remove 方法，使用的仍然是 HashMap 中的代码
但它重写了afterNodeRemoval()这个回调方法。该方法会在Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)方法中回调
// HashMap中代码
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
......
afterNodeRemoval(node);
return node;
......
}
LinkedHashMap 通过调用父类的 HashMap 的 remove 方法将 Hash 表的中节点的删除操作完成即：
- 获取对应 key 的哈希值 hash(key)，定位对应的哈希桶的位置
- 遍历对应的哈希桶中的单链表或者红黑树找到对应 key 相同的节点，在最后删除，并返回原来的节点。
对于 afterNodeRemoval（node） HashMap 中是空实现，而该方法，正是 LinkedHashMap 删除对应节点在双向链表中的关系的操作：
//在删除节点e时，同步将e从双向链表上删除
void afterNodeRemoval(Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//待删除节点 p 的前置后置节点都置空
p.before = p.after = null;
//如果前置节点是null，则现在的头结点应该是后置节点a
if (b == null)
head = a;
else//否则将前置节点b的后置节点指向a
b.after = a;
//同理如果后置节点时null ，则尾节点应是b
if (a == null)
tail = b;
else//否则更新后置节点a的前置节点为b
a.before = b;
}
LinkedHashMap put元素的时候如果key不存在，不论accessOrder是否true还是false, 都会把新元素添加到双向链表的尾部，既符合插入的先后顺序，又符合访问的先后顺序；当key存在重复，需要覆盖value值，这个时候只有accessOrder为true的时候会调整双向链表，把当前访问put的Entry移到双向链表的尾部, 保证了访问的先后顺序。
总结
- LinkedHashMap是非线程安全的
- LinkedHashMap 拥有与 HashMap 相同的底层哈希表结构，即数组 + 单链表 + 红黑树，也拥有相同的扩容机制。
- LinkedHashMap 相比 HashMap 的拉链式存储结构，内部额外通过 Entry 维护了一个双向链表。
- HashMap 元素的遍历顺序不一定与元素的插入顺序相同，而 LinkedHashMap 则通过(遍历双向链表)来获取元素，所以遍历顺序在一定条件下等于插入顺序。
- 迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。LinkedHashMap 可以通过构造参数 accessOrder 来指定双向链表是否在元素被增、删、改、查后改变其在双向链表中的位置。
- 维护这个双向链表了，就是在get和put的时候用了钩子技术(多态)调用LinkedHashMap重写的方法来维护这个双向链表，然后迭代的时候直接迭代这个双向链表。