【1】LinkedHashMap定义
LinkedHashMap是HashMap的子类，其实现与HashMap 的不同之处在于，LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap 相似，它通过重写父类相关的方法，来实现自己的链接列表特性。
注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。
虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。特别地，该迭代顺序可以是插入顺序，也可以是访问顺序。
因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap 和 保持访问顺序的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的。
顺序遍历和快速定位LinkedHashMap适合有加入顺序和快速定位的场景。
下图来源于网络，大概描述了LinkedHashMap中哈希桶与双向链表的结构，其中黑色箭头表示的是next指针。
【2】核心属性和构造
如下代码如未显示说明，则是基于JDK1.8。
① 核心数据结构
LinkedHashMap底层核心数据结构Entry继承自HashMap的Node，在Node基础上增加了before、after指针来维持双向链表。
LinkedHashMap 采用的hash 算法和HashMap 相同，但是它重新定义了数组中保存的元素Entry，该Entry 除了保存当前对象的引用外，还保存了其上一个元素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); } }
HashMap的Node数据结构如下，维护了hash、key、value、以及next(用于位置单向链表)
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; ... }
不可避免的，这里也用到了树节点TreeNode。如下所示，其在LinkedHashMap.Entry<K,V>基础上增加了parent、left、right、prev以及red(红黑树)。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } //... }
② 核心属性
//双向链表的表头(eldest)元素。 transient LinkedHashMap.Entry<K,V> head; //双向链表的表尾(youngest)元素。 transient LinkedHashMap.Entry<K,V> tail; /** * The iteration ordering method for this linked hash map: <tt>true</tt> * for access-order, <tt>false</tt> for insertion-order. */ // 迭代顺序，true-访问顺序；false-插入顺序 final boolean accessOrder;
③ 构造函数
accessOrder = false;表示默认实现是维持插入顺序。
//指定初始化容量和负载因子 public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } //指定初始化容量 public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } //默认的无参构造 public LinkedHashMap() { super(); accessOrder = false; } //使用给定集合构造 public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); } //完整的属性指定构造 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
④ 排序模式accessOrder和LRU
LinkedHashMap 定义了排序模式accessOrder，该属性为boolean 型变量，对于访问顺序，为true；对于插入顺序，则为false。
一般情况下，不必指定排序模式，其迭代顺序即默认为插入顺序。看LinkedHashMap的构造方法，这些构造方法都会默认指定排序模式为插入顺序。除了其中一个有accessOrder参数外，其他均默认为false。
如果你想构造一个LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造LinkedHashMap：
// accessOrder=true public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
该hashmap的迭代顺序就是最后访问其条目的顺序，这种map很适合构建LRU 缓存。
LinkedHashMap 提供了removeEldestEntry(Map.Entry<K,V> eldest)方法，在将新条目插入到map后，put 和 putAll 将调用此方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false(这样，此map的行为将类似于正常map，即永远不能移除最旧的元素)。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }
此方法通常不以任何方式修改map，相反允许map在其返回值的指引下进行自我修改。如果用此map构建LRU 缓存，则非常方便，它允许map通过删除旧条目来减少内存损耗。
例如：重写此方法，维持此map只保存100 个条目的稳定状态，在每次添加新条目时删除最旧的条目。
private static final int MAX_ENTRIES = 100; protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES; }
【3】读取数据
① jdk1.8下get(Object key)
如下所示，getNode(hash(key), key))本质是直接调用了父类HashMap的方法。
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; }
这里我们需要注意的是当accessOrder为true时(也就是维持访问顺序)，会触发afterNodeAccess(e)。
而下面这三个方法在父类HashMap中均是空方法，留给子类实现。
这里我们需要注意的是当accessOrder为true时(也就是维持访问顺序)，会触发afterNodeAccess(e)。 而下面这三个方法在父类HashMap中均是空方法，留给子类实现。 void
② jdk1.7下get方法
dk1.7下LinkedHashMap 重写了父类HashMap 的get 方法。实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder 为true 时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。
由于链表的增加、删除操作是常量级的，故并不会带来性能的损失。
public V get(Object key) { // 调用父类HashMap 的getEntry()方法，取得要查找的元素。 Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; // 记录访问顺序。 e.recordAccess(this); return e.value; } void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; // 如果定义了LinkedHashMap 的迭代顺序为访问顺序， // 则删除以前位置上的元素，并将最新访问的元素添加到链表表头。 if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } }
关于存放数据如下图所示，LinkedHashMap完全继承自父类HashMap的方法。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
同样移除元素也是依赖于父类HashMap，其自己实现的removeEldestEntry上文已经说过。
【4】LinkedHashMap实现的三个回调函数
在LinkedHashMap调用父类的put和removeNode相关方法中，实现了三个回调函数来进行链表的维护。
① afterNodeAccess
如果定义了accessOrder 为true，则每次访问之后都会将该元素放到链表中youngest位置处。
void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; //如果保持访问顺序且最后结点不是e if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //尾结点的after为null p.after = null; if (b == null)//p没有before结点其本身就是头结点，那么head -> p.after head = a; else b.after = a;//这两步是把p摘出来，也就是p.before.after-->p.after //判断p有没有后继结点 if (a != null) a.before = b; else last = b;//把p.before-->last if (last == null) head = p; else { //双向绑定 p.before = last; last.after = p; } //把p放到尾结点 tail = p; // 结构调整计数器+1 ++modCount; } }
本质就是把当前结点放到尾结点。
② afterNodeInsertion(boolean evict)
如果需要移除eldest结点，如LRU实现中，就根据evict和removeEldestEntry将head移除(也就是移除最老的元素/最少访问的元素)：
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; //调用父类HashMap的移除方法 removeNode(hash(key), key, null, false, true); } }
③ afterNodeRemoval(Node<K,V> e)
如果该结点被移除，就从链表中断开。
void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //before after均置为null p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; }
假设移除Node2，那么图示如下：
