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

2021年09月15日 阅读数:1
这篇文章主要向大家介绍深刻浅出LinkedHashMap原理和源码解毒,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

第一时间获取技术干货和业界资讯!数组

深刻浅出LinkedHashMap原理和源码解毒
最近,我知道有好几个同窗会偶尔的阅读阅读个人博客。我倍感压力,他都是 CTO 级的人物,我常常向他们取经,膜拜他们。缓存

这不最近,有一个同窗公司里要搞培训,主讲人对 LinkedHashMap 讲的不够深,但愿我有好文章推荐一下。既然这么说了,那我何不解决宣传一下本身的公众号呢?安全

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

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

深刻浅出LinkedHashMap原理和源码解毒
顺着 LinkedHashMap 的源码往下看,你会发现 LinkedHashMap 提供了 5 个构造函数。基本上就是对 HashMap 的构造函数作了扩展,加了一个重要的参数 accessOrder,它表明的是一个访问顺序,后面会具体的讲。函数

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

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

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

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

深刻浅出LinkedHashMap原理和源码解毒
LinkedHashMap 并无重写任何 put 方法。可是其重写了构建新节点的 newNode() 方法。
newNode() 会在 HashMap 的 putVal() 方法里被调用,putVal() 方法会在批量插入数据 putMapEntries(Map m, boolean evict) 或者插入单个数据 public V put(K key, V value) 时被调用。

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

深刻浅出LinkedHashMap原理和源码解毒
其中的 linkNodeLast 方法,会将新增的节点。若是,集合以前是空的,指定 head 节点;不然将新节点链接在链表的尾部。

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

深刻浅出LinkedHashMap原理和源码解毒
LinkedHashMap 还重写了 afterNodeRemoval 这个方法。在删除节点 e 时,同步将 e 从双向链表上删除。

深刻浅出LinkedHashMap原理和源码解毒
另外 get() 和 getOrDefault() 方法也被重写了。由于咱们要根据 accessOrder 规则来调整具体的获取方法。在 accessOrder 为 true 的状况下,要去回调 void afterNodeAccess(Node e) 函数。

深刻浅出LinkedHashMap原理和源码解毒
在 afterNodeAccess() 函数中,会将当前被访问到的节点 e,移动至内部的双向链表的尾部。

深刻浅出LinkedHashMap原理和源码解毒
经过上图的解释,你会发现。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的增、删、改、查时都会更新。

以知足按照插入顺序输出,仍是访问顺序输出。

    1. 它与 HashMap 比,还有一个小小的优化,重写了 containsValue() 方法,直接遍历内部链表去比对 value 值是否相等。