LinkedHashMap内部维护了一个双向链表，能保证元素按插入的顺序访问，也能以访问顺序访问。
LinkedHashMap可以看成是 LinkedList + HashMap。
LinkedHashMap继承HashMap，拥有HashMap(参考链接：JDK集合源码之HashMap解析)的所有特性，并且额外增加了按一定顺序访问的特性，LinkedHashMap 默认存储顺序为插入顺序，也可按照访问顺序存储元素。
案例
@Test public void test01(){ HashMap hashMap = new HashMap(); hashMap.put("name","csp"); hashMap.put("name","csp1999"); hashMap.put("age","22"); hashMap.put("sex","man"); hashMap.put("school","haust"); hashMap.put("class","1801"); System.out.println(hashMap);// key不允许重复，无序集合{school=haust, sex=man, name=csp1999, class=1801, age=22} LinkedHashMap linkedHashMap = new LinkedHashMap(); linkedHashMap.put("name","csp"); linkedHashMap.put("name","csp1999"); linkedHashMap.put("age","22"); linkedHashMap.put("sex","man"); linkedHashMap.put("school","haust"); linkedHashMap.put("class","1801"); System.out.println(linkedHashMap);// key不允许重复，有序集合{name=csp1999, age=22, sex=man, school=haust, class=1801} // LinkedHashMap 默认存储顺序为插入顺序，也可按照访问顺序存储元素 }
LinkedHashMap继承体系
HashMap使用的是（数组 + 单链表 + 红黑树）的存储结构，通过上面的继承体系，我们知道LinkedHashMap继承了HashMap，所以它的内部也有这三种结构，但是它还额外添加了一种“双向链表”的结构存储所有元素的顺序。
添加删除元素的时候需要同时维护在HashMap中的存储，也要维护在LinkedList中的存储，所以性能上来说会比HashMap稍慢。
LinkedHashMap源码分析
1. 属性
/** * 序列化版本号 */ private static final long serialVersionUID = 3801124242820219131L; /** * 双向链表的头节点. * 被transient关键字修饰的对象不能被序列化 */ transient LinkedHashMap.Entry<K,V> head; /** * 双向链表的尾节点. */ transient LinkedHashMap.Entry<K,V> tail; /** * 是否按访问顺序排序 * true : 按照访问顺序排序 * false: 按照插入顺序排序 * @serial */ final boolean accessOrder;
- head：双向链表的头节点，旧数据存在头节点。
- tail：双向链表的尾节点，新数据存在尾节点。
- accessOrder：是否需要按访问顺序排序，如果为false则按插入顺序存储元素，如果是true则按访问顺序存储元素。
2. 内部类
/** * 位于LinkedHashMap中 HashMap的子类. */ 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中. */ static class Node<K,V> implements Map.Entry<K,V> { final int hash;// hash用来存储key计算得来的hash值 final K key;// 键 V value;// 值 Node<K,V> next;// 下一个node节点 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } ... }
存储节点，继承自HashMap的Node类，next用于单链表存储于桶中，before和after用于双向链表存储所有元素。
3. 构造方法
//默认是false，则迭代时输出的顺序是插入节点的顺序。若为true，则输出的顺序是按照访问节点的顺序。 //为true时，可以在这基础之上构建一个LruCach final boolean accessOrder; 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; //该方法上文分析过，批量插入一个map中的所有数据到 本集合中。 putMapEntries(m, false); }
前四个构造方法accessOrder都等于false，说明双向链表是按插入顺序存储元素。
最后一个构造方法accessOrder从构造方法参数传入，如果传入true，则就实现了按访问顺序存储元素，这也是实现LRU缓存策略的关键。
4. 成员方法
4.1 增
LinkedHashMap并没有重写任何put方法。但是其重写了构建新节点的newNode()方法.
newNode()会在HashMap的putVal()方法里被调用，putVal()方法会在批量插入数据putMapEntries(Map<? extends K, ? extends V> m, boolean evict)或者插入单个数据public V put(K key, V value)时被调用。
LinkedHashMap重写了newNode(),在每次构建新节点时，通过linkNodeLast(p);将新节点链接在内部双向链表的尾部。
//在构建新节点时，构建的是`LinkedHashMap.Entry` 不再是`Node`. 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() 方法。
// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { }
//回调函数，新节点插入之后回调 ， 根据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里可以忽略它们。
4.2 删
LinkedHashMap也没有重写remove()方法，因为它的删除逻辑和HashMap并无区别。
但它重写了afterNodeRemoval()这个回调方法。该方法会在Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)方法中回调，removeNode()会在所有涉及到删除节点的方法中被调用，是删除节点操作的真正执行者。
//在删除节点e时，同步将e从双向链表上删除 void afterNodeRemoval(Node<K,V> e) { // unlink 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; }
4.3 查
LinkedHashMap重写了get()和getOrDefault()方法：
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; } public V getOrDefault(Object key, V defaultValue) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return defaultValue; if (accessOrder) afterNodeAccess(e); return e.value; }
对比HashMap中的实现,LinkedHashMap只是增加了在成员变量(构造函数时赋值)accessOrder为true的情况下，要去回调void afterNodeAccess(Node<K,V> e)函数。
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
在afterNodeAccess()函数中，会将当前被访问到的节点e，移动至内部的双向链表的尾部。
void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last;//原尾节点 //如果accessOrder 是true ，且原尾节点不等于e if (accessOrder && (last = tail) != e) { //节点e强转成双向链表节点p LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //p现在是尾节点， 后置节点一定是null p.after = null; //如果p的前置节点是null，则p以前是头结点，所以更新现在的头结点是p的后置节点a if (b == null) head = a; else//否则更新p的前直接点b的后置节点为 a b.after = a; //如果p的后置节点不是null，则更新后置节点a的前置节点为b if (a != null) a.before = b; else//如果原本p的后置节点是null，则p就是尾节点。 此时 更新last的引用为 p的前置节点b last = b; if (last == null) //原本尾节点是null 则，链表中就一个节点 head = p; else {//否则 更新 当前节点p的前置节点为 原尾节点last， last的后置节点是p p.before = last; last.after = p; } //尾节点的引用赋值成p tail = p; //修改modCount。 ++modCount; } }
值得注意的是，afterNodeAccess()函数中，会修改modCount,因此当你正在accessOrder=true的模式下,迭代LinkedHashMap时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。
4.4 遍历
重写了entrySet()如下：
public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; //返回LinkedEntrySet return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es; } final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> { public final Iterator<Map.Entry<K,V>> iterator() { return new LinkedEntryIterator(); } }
最终的EntryIterator:
final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } } abstract class LinkedHashIterator { //下一个节点 LinkedHashMap.Entry<K,V> next; //当前节点 LinkedHashMap.Entry<K,V> current; int expectedModCount; LinkedHashIterator() { //初始化时，next 为 LinkedHashMap内部维护的双向链表的扁头 next = head; //记录当前modCount，以满足fail-fast expectedModCount = modCount; //当前节点为null current = null; } //判断是否还有next public final boolean hasNext() { //就是判断next是否为null，默认next是head 表头 return next != null; } //nextNode() 就是迭代器里的next()方法 。 //该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。 final LinkedHashMap.Entry<K,V> nextNode() { //记录要返回的e。 LinkedHashMap.Entry<K,V> e = next; //判断fail-fast if (modCount != expectedModCount) throw new ConcurrentModificationException(); //如果要返回的节点是null，异常 if (e == null) throw new NoSuchElementException(); //更新当前节点为e current = e; //更新下一个节点是e的后置节点 next = e.after; //返回e return e; } //删除方法 最终还是调用了HashMap的removeNode方法 public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } }
值得注意的就是：nextNode() 就是迭代器里的next()方法 。
该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。
而双链表节点的顺序在LinkedHashMap的增、删、改、查时都会更新。以满足按照插入顺序输出，还是访问顺序输出。
4.5 afterNodeInsertion(boolean evict)方法
在节点插入之后做些什么，在HashMap中的putVal()方法中被调用，可以看到HashMap中这个方法的实现为空。
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }
evict，驱逐的意思。
（1）如果evict为true，且头节点不为空，且确定移除最老的元素，那么就调用HashMap.removeNode()把头节点移除（这里的头节点是双向链表的头节点，而不是某个桶中的第一个元素）；
（2）HashMap.removeNode()从HashMap中把这个节点移除之后，会调用afterNodeRemoval()方法；
（3）afterNodeRemoval()方法在LinkedHashMap中也有实现，用来在移除元素后修改双向链表，见下文；
（4）默认removeEldestEntry()方法返回false，也就是不删除元素。
4.6 afterNodeAccess(Node e)方法
在节点访问之后被调用，主要在put()已经存在的元素或get()时被调用，如果accessOrder为true，调用这个方法把访问到的节点移动到双向链表的末尾。
void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; // 如果accessOrder为true，并且访问的节点不是尾节点 if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // 把p节点从双向链表中移除 p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; // 把p节点放到双向链表的末尾 if (last == null) head = p; else { p.before = last; last.after = p; } // 尾节点等于p tail = p; ++modCount; } }
- 如果accessOrder为true，并且访问的节点不是尾节点；
- 从双向链表中移除访问的节点；
- 把访问的节点加到双向链表的末尾；（末尾为最新访问的元素）
4.7 afterNodeRemoval(Node e)方法
在节点被删除之后调用的方法。
void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<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; }
经典的把节点从双向链表中删除的方法。
4.8 get(Object key)方法
获取元素。
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()方法把访问的节点移到双向链表的末尾。
总结
（1）LinkedHashMap继承自HashMap，具有HashMap的所有特性；
（2）LinkedHashMap内部维护了一个双向链表存储所有的元素；
（3）如果accessOrder为false，则可以按插入元素的顺序遍历元素；
（4）如果accessOrder为true，则可以按访问元素的顺序遍历元素；
（5）LinkedHashMap的实现非常精妙，很多方法都是在HashMap中留的钩子（Hook），直接实现这些Hook就可以实现对应的功能了，并不需要再重写put()等方法；
（6）默认的LinkedHashMap并不会移除旧元素，如果需要移除旧元素，则需要重写removeEldestEntry()方法设定移除策略；
（7）LinkedHashMap可以用来实现LRU缓存淘汰策略；
LinkedHashMap相对于HashMap的源码比，是很简单的。因为大树底下好乘凉。它继承了HashMap，仅重写了几个方法，以改变它迭代遍历时的顺序。这也是其与HashMap相比最大的不同。
在每次插入数据，或者访问、修改数据时，会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序。
accessOrder ,默认是false，则迭代时输出的顺序是插入节点的顺序。若为true，则输出的顺序是按照访问节点的顺序。为true时，可以在这基础之上构建一个LruCache.
LinkedHashMap并没有重写任何put方法。但是其重写了构建新节点的newNode()方法.在每次构建新节点时，将新节点链接在内部双向链表的尾部
accessOrder=true的模式下,在afterNodeAccess()函数中，会将当前被访问到的节点e，移动至内部的双向链表的尾部。值得注意的是，afterNodeAccess()函数中，会修改modCount,因此当你正在accessOrder=true的模式下,迭代LinkedHashMap时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。
nextNode() 就是迭代器里的next()方法 。
该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。
而双链表节点的顺序在LinkedHashMap的增、删、改、查时都会更新。以满足按照插入顺序输出，还是访问顺序输出。
它与HashMap比，还有一个小小的优化，重写了containsValue()方法，直接遍历内部链表去比对value值是否相等。
扩展
LinkedHashMap如何实现LRU缓存淘汰策略呢？
首先，我们先来看看LRU是个什么鬼。LRU，Least Recently Used，最近最少使用，也就是优先淘汰最近最少使用的元素。
如果使用LinkedHashMap，我们把accessOrder设置为true是不是就差不多能实现这个策略了呢？答案是肯定的。请看下面的代码：
/** * @author: csp1999 * @date: 2020/11/10 */ public class LRUTest { public static void main(String[] args) { // 创建一个只有5个元素的缓存 LRU<Integer, Integer> lru = new LRU<>(5, 0.75f); lru.put(1, 1); lru.put(2, 2); lru.put(3, 3); lru.put(4, 4); lru.put(5, 5); lru.put(6, 6); lru.put(7, 7); System.out.println(lru.get(4)); lru.put(6, 666); // 输出: {3=3, 5=5, 7=7, 4=4, 6=666} // 可以看到最旧的元素被删除了 // 且最近访问的4被移到了后面 System.out.println(lru); } } class LRU<K, V> extends LinkedHashMap<K, V> { // 保存缓存的容量 private int capacity; public LRU(int capacity, float loadFactor) { super(capacity, loadFactor, true); this.capacity = capacity; } /** * 重写removeEldestEntry()方法设置何时移除旧元素 * @param eldest * @return */ @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { // 当元素个数大于了缓存的容量, 就移除元素 return size() > this.capacity; } }
