最近,我知道有好几个同学会偶尔的阅读阅读我的博客。我倍感压力,他都是 CTO 级的人物,我经常向他们取经,膜拜他们。
这不最近,有一个同学公司里要搞培训,主讲人对 LinkedHashMap 讲的不够深,希望我有好文章推荐一下。既然这么说了,那我何不解决宣传一下自己的公众号呢?
LinkedHashMap 顾名思义,就是一个基于 HashMap 的双向链表的集合。其中 HashMap 为数组加单向链表的结构,LinkedList 为双向链表实现的。而 LinkedHashMap 正是二者的结合体。
首先,从源码上来看,LinkedHashMap 继承自 HashMap,所以 HashMap 有的大部分特性,LinkedHashMap 都有。比如:线程安全问题等。关于 HashMap 推荐阅读《搞不懂 HashMap?只因你缺一个 HashMap 的原理机制流程图!》。
顺着 LinkedHashMap 的源码往下看,你会发现 LinkedHashMap 提供了 5 个构造函数。基本上就是对 HashMap 的构造函数做了扩展,加了一个重要的参数 accessOrder,它代表的是一个访问顺序,后面会具体的讲。
注意上图,LinkedHashMap 还有一个改变就是多了两个属性:header 和 accessOrder。header 就是双向链表的表头元素。当 accessOrder 为 true 时,代表按访问顺序迭代,false 时表示按照插入顺序。这个配图来自网上,是基于 JDK1.6 的,现在 JDK8 的变化已经很大了。
LinkedHashMap 继承了 HashMap 中大部分的方法,只是多了双向链表。
LinkedHashMap 的 Entry 增加了用于维护顺序的 before 和 after 变量,就是用来确定链表的前后节点。本来无序的数组 + 链表结构,通过 before 和 after 把它们关联起来,变的有序。在 put 和 get 的时候维护好了这个双向链表,遍历的时候就有序了。
LinkedHashMap 的节点 Entry 继承自 HashMap.Node,然后将单向链表改成了一个双向链表。
LinkedHashMap 并没有重写任何 put 方法。但是其重写了构建新节点的 newNode() 方法。
newNode() 会在 HashMap 的 putVal() 方法里被调用,putVal() 方法会在批量插入数据 putMapEntries(Map m, boolean evict) 或者插入单个数据 public V put(K key, V value) 时被调用。
LinkedHashMap 重写了 newNode(),在每次构建新节点时,通过 linkNodeLast(p); 将新节点链接在内部双向链表的尾部。
其中的 linkNodeLast 方法,会将新增的节点。如果,集合之前是空的,指定 head 节点;否则将新节点连接在链表的尾部。
另外 LinkedHashMap 的 afterNodeInsertion 方法也非常的重要,它会在新节点插入之后回调,根据 evict 和 first 判断是否需要删除最老插入的节点。
LinkedHashMap 还重写了 afterNodeRemoval 这个方法。在删除节点 e 时,同步将 e 从双向链表上删除。
另外 get() 和 getOrDefault() 方法也被重写了。因为我们要根据 accessOrder 规则来调整具体的获取方法。在 accessOrder 为 true 的情况下,要去回调 void afterNodeAccess(Node e) 函数。
在 afterNodeAccess() 函数中,会将当前被访问到的节点 e,移动至内部的双向链表的尾部。
通过上图的解释,你会发现。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 值是否相等。
: » 深入浅出LinkedHashMap原理和源码解读
原创文章,作者:bd101bd101,如若转载,请注明出处:https://blog.ytso.com/252081.html