深入浅出LinkedHashMap原理和源码解毒

640

最近，我知道有好几个同学会偶尔的阅读阅读我的博客。我倍感压力，他都是 CTO 级的人物，我经常向他们取经，膜拜他们。

这不最近，有一个同学公司里要搞培训，主讲人对 LinkedHashMap 讲的不够深，希望我有好文章推荐一下。既然这么说了，那我何不解决宣传一下自己的公众号呢？

LinkedHashMap 顾名思义，就是一个基于 HashMap 的双向链表的集合。其中 HashMap 为数组加单向链表的结构，LinkedList 为双向链表实现的。而 LinkedHashMap 正是二者的结合体。

640

首先，从源码上来看，LinkedHashMap 继承自 HashMap，所以 HashMap 有的大部分特性，LinkedHashMap 都有。比如：线程安全问题等。关于 HashMap 推荐阅读《搞不懂 HashMap？只因你缺一个 HashMap 的原理机制流程图！》。

640

顺着 LinkedHashMap 的源码往下看，你会发现 LinkedHashMap 提供了 5 个构造函数。基本上就是对 HashMap 的构造函数做了扩展，加了一个重要的参数 accessOrder，它代表的是一个访问顺序，后面会具体的讲。

640

注意上图，LinkedHashMap 还有一个改变就是多了两个属性：header 和 accessOrder。header 就是双向链表的表头元素。当 accessOrder 为 true 时，代表按访问顺序迭代，false 时表示按照插入顺序。这个配图来自网上，是基于 JDK1.6 的，现在 JDK8 的变化已经很大了。

LinkedHashMap 继承了 HashMap 中大部分的方法，只是多了双向链表。

640

LinkedHashMap 的 Entry 增加了用于维护顺序的 before 和 after 变量，就是用来确定链表的前后节点。本来无序的数组 + 链表结构，通过 before 和 after 把它们关联起来，变的有序。在 put 和 get 的时候维护好了这个双向链表，遍历的时候就有序了。

LinkedHashMap 的节点 Entry 继承自 HashMap.Node，然后将单向链表改成了一个双向链表。

640

LinkedHashMap 并没有重写任何 put 方法。但是其重写了构建新节点的 newNode() 方法。 newNode() 会在 HashMap 的 putVal() 方法里被调用，putVal() 方法会在批量插入数据 putMapEntries(Map m, boolean evict) 或者插入单个数据 public V put(K key, V value) 时被调用。

LinkedHashMap 重写了 newNode(),在每次构建新节点时，通过 linkNodeLast(p); 将新节点链接在内部双向链表的尾部。

640

其中的 linkNodeLast 方法，会将新增的节点。如果，集合之前是空的，指定 head 节点；否则将新节点连接在链表的尾部。

另外 LinkedHashMap 的 afterNodeInsertion 方法也非常的重要，它会在新节点插入之后回调，根据 evict 和 first 判断是否需要删除最老插入的节点。

640

LinkedHashMap 还重写了 afterNodeRemoval 这个方法。在删除节点 e 时，同步将 e 从双向链表上删除。

640

另外 get() 和 getOrDefault() 方法也被重写了。因为我们要根据 accessOrder 规则来调整具体的获取方法。在 accessOrder 为 true 的情况下，要去回调 void afterNodeAccess(Node e) 函数。

640

在 afterNodeAccess() 函数中，会将当前被访问到的节点 e，移动至内部的双向链表的尾部。

640

通过上图的解释，你会发现。afterNodeAccess 方法埋下了隐患，会修改 modCount，因此当你正在 accessOrder=true 的模式下，迭代 LinkedHashMap 时，如果同时查询访问数据，也会导致 fail-fast，因为迭代的顺序已经改变。

最后，总结一下。LinkedHashMap 相对于 HashMap 的源码比，是很简单的。因为大树底下好乘凉。它继承了 HashMap，仅重写了几个方法，以改变它迭代遍历时的顺序。这也是其与 HashMap 相比最大的不同。在每次插入数据，或者访问、修改数据时，会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序。

• accessOrder，默认是 false，则迭代时输出的顺序是插入节点的顺序。 若为 true，则输出的顺序是按照访问节点的顺序。 为 true 时，可以在这基础之上构建一个 LruCache。 参考《手把手教你用LinkedHashMap打造FIFO和LRU缓存系统》
• LinkedHashMap 并没有重写任何 put 方法。 但是其重写了构建新节点的 newNode() 方法.在每次构建新节点时，将新节点链接在内部双向链表的尾部
• accessOrder=true 的模式下，在 afterNodeAccess() 函数中，会将当前被访问到的节点 e，移动至内部的双向链表的尾部。 值得注意的是，afterNodeAccess() 函数中，会修改 modCount，因此当你正在 accessOrder=true 的模式下，迭代 LinkedHashMap 时，如果同时查询访问数据，也会导致 fail-fast，因为迭代的顺序已经改变。
• nextNode() 就是迭代器里的next()方法。 该方法的实现可以看出，迭代 LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。 而双链表节点的顺序在LinkedHashMap的增、删、改、查时都会更新。 以满足按照插入顺序输出，还是访问顺序输出。
• 它与 HashMap 比，还有一个小小的优化，重写了 containsValue() 方法，直接遍历内部链表去比对 value 值是否相等。