本文主要是介绍深读源码-java集合之LinkedHashMap源码分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
简介
LinkedHashMap内部维护了一个双向链表，能保证元素按插入的顺序访问，也能以访问顺序访问，可以用来实现LRU缓存策略。
LinkedHashMap可以看成是 LinkedList + HashMap。
类继承体系
LinkedHashMap继承HashMap，拥有HashMap的所有特性，并且额外增加了按一定顺序访问的特性。
Entry的继承关系
Entry作为基本的节点，可以看到LinkedHashMap的Entry继承自HashMap的Node，在其基础上加上了before和after两个指针，而TreeNode作为HashMap和LinkedHashMap的树节点，继承自LinkedHahsMap的Entry，并且加上了树节点的相关指针，另外提一点：before和parent的两个概念是不一样的，before是相对于链表来的，parent是相对于树操作来的，所以要分两个。
Iterator的继承关系
LinkedHashMap的迭代器为遍历节点提供了自己的实现——LinkedHashIterator，对于Key、Value、Entry的3个迭代器，都继承自它。而且内部采用的遍历方式就是在前面提到的Entry里加的新的指向下一个节点的指针after，后面我们将具体看它的代码实现。
存储结构
双链表是链表的一种，由节点组成，每个数据结点中都有两个指针，分别指向直接后继和直接前驱
我们知道HashMap使用（数组 + 单链表 + 红黑树）的存储结构，那LinkedHashMap是怎么存储的呢？
通过上面的继承体系，我们知道它继承了HashMap，所以它的内部也有这三种结构，但是它还额外添加了一种“双向链表”的结构存储所有元素的顺序。
添加删除元素的时候需要同时维护在HashMap中的存储，也要维护在LinkedList中的存储，所以性能上来说会比HashMap稍慢。
源码解析
属性
/*** 双向链表头节点 */
transient LinkedHashMap.Entry<K,V> head;/*** 双向链表尾节点 */
transient LinkedHashMap.Entry<K,V> tail;/*** 是否需要按访问顺序排序，用来指定LinkedHashMap的迭代顺序。* true则表示按照基于访问的顺序来排列，意思就是最近使用的entry，放在链表的最末尾* false则表示按照插入顺序排序*/
final boolean accessOrder;
（1）head
双向链表的头节点，旧数据存在头节点。
（2）tail
双向链表的尾节点，新数据存在尾节点。
（3）accessOrder
是否需要按访问顺序排序， true则表示按照基于访问的顺序来排列，意思就是最近使用的entry，放在链表的最末尾 ；false则表示按照插入顺序排序。
注意：accessOrder是final关键字，说明我们要在构造方法里给它初始化。
内部类
// 位于LinkedHashMap中
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;final K key;V value;Node<K, V> next;
}
存储节点，继承自HashMap的Node类，next用于单链表存储于桶中，before和after用于双向链表存储所有元素。
构造方法
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都等于false，说明双向链表是按插入顺序存储元素。
最后一个构造方法accessOrder从构造方法参数传入，如果传入true，则就实现了按访问顺序存储元素，这也是实现LRU缓存策略的关键。
get(Object key)方法
获取元素。
public V get(Object key) {Node<K,V> e;// 调用HashMap的getNode的方法，详见上一篇HashMap源码解析if ((e = getNode(hash(key), key)) == null)return null;// 在取值后对参数accessOrder进行判断，如果为true，执行afterNodeAccessif (accessOrder)afterNodeAccess(e);return e.value;
}
如果查找到了元素，且accessOrder为true，则调用afterNodeAccess()方法把访问的节点移到双向链表的末尾。
afterNodeAccess(Node<K,V> e)方法
在节点访问之后被调用，主要在put()已经存在的元素或get()时被调用，如果accessOrder为true，调用这个方法把访问到的节点移动到双向链表的末尾。
// 此函数执行的效果就是将最近使用的Node，放在链表的最末尾
void afterNodeAccess(Node<K,V> e) {LinkedHashMap.Entry<K,V> last;// 仅当按照LRU原则且e不在最末尾，才执行修改链表，将e移到链表最末尾的操作if (accessOrder && (last = tail) != e) {// 将e赋值临时节点p， b是e的前一个节点， a是e的后一个节点LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;// 设置p的后一个节点为null，因为执行后p在链表末尾，after肯定为nullp.after = null;// p前一个节点不存在，情况一if (b == null) // ①head = a;// p为头部，前一个节点b不存在，那么考虑到p要放到最后面，则设置p的后一个节点a为headelseb.after = a;// P不是头部，前一个节点b存在，重新设置b的后一个节点为aif (a != null) a.before = b;// P不是尾部，设置a的前一个节点为b// p的后一个节点不存在，情况二else // ②last = b;// p为尾部，后一个节点a不存在，那么考虑到统一操作，设置last为b// 情况三if (last == null) // ③head = p;// p为链表里的第一个节点，head=p// 正常情况，将p设置为尾节点的准备工作，p的前一个节点为原先的last，last的after为pelse {p.before = last;last.after = p;}// 将p设置为尾节点tail = p;// 修改计数器+1++modCount;}
}（1）如果accessOrder为true，并且访问的节点不是尾节点；
（2）从双向链表中移除访问的节点；
（3）把访问的节点加到双向链表的末尾；（末尾为最新访问的元素）
标注的情况如下图所示（特别说明一下，这里是显示链表的修改后指针的情况，实际上在桶里面的位置是不变的，只是前后的指针指向的对象变了）：
下面来简单说明一下：
-
正常情况下：查询的p在链表中间，那么将p设置到末尾后，它原先的前节点b和后节点a就变成了前后节点。
-
情况一：p为头部，前一个节点b不存在，那么考虑到p要放到最后面，则设置p的后一个节点a为head
-
情况二：p为尾部，后一个节点a不存在，那么考虑到统一操作，设置last为b
-
情况三：p为链表里的第一个节点，head=p
put()方法
LinkedHashMap的put方法调用的还是HashMap里的put，不同的是重写了里面的部分方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {...tab[i] = newNode(hash, key, value, null);...e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);...if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);...afterNodeAccess(e);...afterNodeInsertion(evict);return null;
}由于在之前《深读源码-java集合之HashMap源码分析》分析过了put方法，这里笔者就省略了部分代码，LinkedHashMap将其中newNode方法以及之前设置下的钩子方法afterNodeAccess和afterNodeInsertion进行了重写，从而实现了加入链表的目的：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {// 秘密就在于 new的是自己的Entry类，然后调用了linkedNodeLastLinkedHashMap.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) {// 将tail给临时变量lastLinkedHashMap.Entry<K,V> last = tail;// 把new的Entry给tailtail = p;// 若没有last，说明p是第一个节点，head=pif (last == null)head = p;// 否则就做准备工作，你懂的 (￣▽￣)"else {p.before = last;last.after = p;}
}// 这里笔者也把TreeNode的重写也加了进来，因为putTreeVal里有调用了这个
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);linkNodeLast(p);return p;
}// 插入后把最老的Entry删除，不过removeEldestEntry总是返回false，所以不会删除，估计又是一个钩子方法给子类用的
void afterNodeInsertion(boolean evict) {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;
}afterNodeInsertion(boolean evict)方法
在节点插入之后做些什么，在HashMap中的putVal()方法中被调用，可以看到HashMap中这个方法的实现为空。
// 插入后把最老的Entry删除，不过removeEldestEntry总是返回false，所以不会删除，估计又是一个钩子方法给子类用的
void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.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，也就是不删除元素。
remove()方法
remove里面设计者也设置了一个钩子方法：
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {...// node即是要删除的节点afterNodeRemoval(node);...
}afterNodeRemoval(Node<K,V> e)方法
在节点被删除之后调用的方法。
void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;// p已删除，前后指针都设置为null，便于GC回收p.before = p.after = null;// 与afterNodeAccess差不多逻辑if (b == null)head = a;elseb.after = a;if (a == null)tail = b;elsea.before = b;
}
经典的把节点从双向链表中删除的方法。
LinkedHashMap的迭代器
abstract class LinkedHashIterator {// 记录下一个EntryLinkedHashMap.Entry<K,V> next;// 记录当前的EntryLinkedHashMap.Entry<K,V> current;// 记录是否发生了迭代过程中的修改int expectedModCount;LinkedHashIterator() {// 初始化的时候把head给nextnext = head;expectedModCount = modCount;current = null;}public final boolean hasNext() {return next != null;}// 这里采用的是链表方式的遍历方式，有兴趣的读者可以去之前的《深读源码-java集合之HashMap源码分析》看看HashMap的遍历方式final LinkedHashMap.Entry<K,V> nextNode() {LinkedHashMap.Entry<K,V> e = next;if (modCount != expectedModCount)throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();//记录当前的Entrycurrent = e;//直接拿after给nextnext = e.after;return e;}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;}
}总结
（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如何实现LRU缓存淘汰策略呢？
首先，我们先来看看LRU是个什么鬼。LRU，Least Recently Used，最近最少使用，也就是优先淘汰最近最少使用的元素。
如果使用LinkedHashMap，我们把accessOrder设置为true是不是就差不多能实现这个策略了呢？答案是肯定的。请看下面的代码：
package cn.com.sdd.study.list;import java.util.LinkedHashMap;
import java.util.Map;/*** @author suidd* @name LRUTest* @description LRU缓存淘汰策略测试* @date 2020/5/9 16:54* Version 1.0**/
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被移到了后面// 如果LRU构造accessOrder设置为false，则输出{3=3, 4=4, 5=5, 6=666, 7=7}System.out.println(lru);}
}class LRU<K, V> extends LinkedHashMap<K, V> {// 保存缓存的容量private int capacity;public LRU(int capacity, float loadFactor) {//accessOrder：true:按访问顺序排序（LRU），false:按插入顺序排序；super(capacity, loadFactor, true);this.capacity = capacity;}/*** 重写removeEldestEntry()方法设置何时移除旧元素** @param eldest* @return*/@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {// 当元素个数大于了缓存的容量, 就移除元素return size() > this.capacity;}
}
参考链接：https://www.cnblogs.com/tong-yuan/p/10639263.html
参考链接：https://www.cnblogs.com/joemsu/p/7787043.html
这篇关于深读源码-java集合之LinkedHashMap源码分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
