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

JAVA herman 224浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xmtxtt,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序

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

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

996icu的程序员

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

LinkedHashMap 源码

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

LinkedHashMap 类图

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

LinkedHashMap 源码中重要的方法列表

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

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

LinkedHashMap 数组 + 链表结构

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

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

LinkedHashMap 的节点 Entry

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

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

LinkedHashMap 源码 newNode

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

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

LinkedHashMap 的 afterNodeInsertion 方法

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

LinkedHashMap 重写了 afterNodeRemoval

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

afterNodeAccess() 函数

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

afterNodeAccess 方法埋下了隐患

通过上图的解释,你会发现。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 值是否相等。

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847(已满),QQ3群:187424846(已满)。QQ群进群密码:xttblog,想加微信群的朋友,之前的微信号好友已满,请加博主新的微信号:xttblog,备注:“xttblog”,添加博主微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » 深入浅出LinkedHashMap原理和源码解读