准备工作
由于LinkedHashMap也是继承HashMap，在HashMap类的基础上进行的功能扩展，所以先了解下HashMap ：https://www.jianshu.com/p/374546518bb6
LinkedHashMap中链地址的双向循环链表结构
// 双向循环链表维护冲突值
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// 双向循环链表的前驱节点和后继结点
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
// 通过前驱后继关系将节点删除
private void remove() {
// 当前节点的前驱节点的后继为当前节点的后继结点
before.after = after;
// 当前节点的后继结点的前驱为当前节点的前驱节点
after.before = before;
}
说明：使用前驱节点和后继节点删除当前节点
/**
* 将existingEntry指定节点前面插入当前节点。
* existingEntry :现有项
*/
private void addBefore(Entry<K,V> existingEntry) {
//this.after =existingEntry;
after = existingEntry;
//this.before =existingEntry.before;
before = existingEntry.before;
before.after = this;
after.before = this;
}
说明（重要设计）：existingEntry指定节点作为当前节点的后继节点，existingEntry指定节点的前驱节点作为当前节点的前驱节点，对于before和after本身就是当前节点的前驱节点和后继节点，再修改下，让前驱节点的后继指针指向当前节点，让后继节点的前驱指针指向当前节点即可。完成了将existingEntry指定节点前面插入当前节点。
/**
* 如果LinkedHashMap的排序顺序为访问顺序，那么就将当前节点插入到头结点前面
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//如果排序顺序为访问顺序
if (lm.accessOrder) {
// LinkedHashMap修改次数加1
lm.modCount++;
// 删除当前节点
remove();
// 在头节点前面插入当前节点
addBefore(lm.header);
}
}
说明：如果排序顺序为访问顺序，那么将在头结点前面插入当前节点。
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
属性
// 双向链表的头结点
private transient Entry<K,V> header;
说明：双向链表的头节点。
// 排序模式：对于访问顺序，为 true；对于插入顺序，则为 false。
private final boolean accessOrder;
说明：节点的排序方式：对于访问顺序，为 true；对于插入顺序，则为 false。
构造方法
构造方法1：传入初始化容量，加载因子，默认采用插入顺序排序的HashMap构造
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
构造方法2：传入初始化容量，默认加载因子为0.75,默认采用插入顺序排序的HashMap构造
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
构造方法3：采用默认初始化容量16，默认加载因子为0.75,默认插入顺序排序的HashMap构造
public LinkedHashMap() {
super();
accessOrder = false;
}
构造方法4：构造一个映射关系与指定 Map 相同的 HashMap； 所创建的 HashMap 具有默认的加载因子 (0.75) 和足以容纳指定 Map 中映射关系的初始容量； 采用默认插入顺序排序
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
构造方法5：构造一个拥有初始化容量、加载因子、排序顺序的LinkedHashMap
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
方法
init方法，初始化双向循环链表
@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
createEntry方法：创建节点，将头结点插入到当前节点的前面。
void createEntry(int hash, K key, V value, int bucketIndex) {
// 通过下标获取键表中对应的节点Entry
HashMap.Entry<K,V> old = table[bucketIndex];
// 创建一个节点，后继节点指向old
Entry<K,V> e = new Entry<>(hash, key, value, old);
// 插入节点e
table[bucketIndex] = e;
// e节点设置为头结点的后继节点
e.addBefore(header);
size++;
}
说明：
- 虽然HashMap查找元素的方式是，通过键找到hash值，通过hash值找到下标，通过下标找到节点链。
- LinkedHashMap在原来的HashMap基础上，将单向节点链中的每个节点又额外构造了一条双向链表，插入值的顺序，就是在头结点的后面插入新节点（类似于不停的插队的节奏）。
transfer方法：将所有元素都放到新的数组中，重写父类的HashMap
的transfer方法。
/**
* 将所有的元素放置到新的数组中
* 重写父类HashMap的transfer方法
*/
@Override
void transfer(HashMap.Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 使用双向链表的头结点进行循环遍历
for (Entry<K,V> e = header.after; e != header; e = e.after) {
if (rehash)
e.hash = (e.key == null) ? 0 : hash(e.key);
// 通过hash值获取对应的下标索引
int index = indexFor(e.hash, newCapacity);
// 插入到链表表头
e.next = newTable[index];
// 新数组的索引对应的值为header
newTable[index] = e;
}
}
说明：遍历双向链表，从头结点的后继节点开始遍历，然后将遍历到的节点设置到新的键表中。
get方法：返回此映射中映射到指定键的值。
public V get(Object key) {
// 调用父类的getEntry方法，通过键key来获取对应的Entry
Entry<K,V> e = (Entry<K,V>)getEntry(key);
// 如果e为null，那么根本不存在对应的Entry就更没有对应的值了，所以返回null
if (e == null)
return null;
// 将当前节点插入到头结点前面
e.recordAccess(this);
return e.value;
}
说明：通过键获取节点，通过节点获取值。
迭代：
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
总结：
- LinkedHashMap存储冲突值使用双向循环链表。
- LinkedHashMap中键和值都允许存入null值。
- LinkedHashMap中值允许重复，如果发现键相同，就更新原来的值。
- LinkedHashMap是线程不安全的。
- LinkedHashMap中accessOrder属性，true意味着排序模式为访问顺序遍历出来，false意味着排序模式为插入顺序遍历出来。
- LinkedHashMap单独维护了一条双向链表，保证了按照插入的顺序设计的，所以取得时候就会保证有序。
