专栏首页业余草深入浅出LinkedHashMap原理和源码解毒

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

最近,我知道有好几个同学会偶尔的阅读阅读我的博客。我倍感压力,他都是 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 值是否相等。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 可视化实时Web日志分析工具,堪称神器!

    说到web服务器就不得不说Nginx,目前已成为企业建站的首选。但由于种种历史原因,Nginx日志分析工具相较于传统的apache、lighthttp等还是少很...

    猿哥
  • Istio 学习笔记:Istio CNI 插件

    当前实现将用户 pod 流量转发到 proxy 的默认方式是使用 privileged 权限的 istio-init 这个 init container 来做的...

    imroc
  • 聊聊reactor-netty的AccessLog

    reactor-netty-0.8.5.RELEASE-sources.jar!/reactor/netty/ReactorNetty.java

    codecraft
  • 聊聊reactor-netty的AccessLogHandlerH2

    reactor-netty-0.8.5.RELEASE-sources.jar!/reactor/netty/http/server/AccessLogHand...

    codecraft
  • JAVA之Collection(一):关于RandomAccess的讨论

    在阅读Collectios类源码时,发现一些方法常常出现list instanceof RandomAccess的字样,下面以binarySearch为例:

    Charles-LZ
  • node与vue结合的前后端分离跨域问题

    withCredentials默认是false,意思就是不携带cookie信息,那就让它为true,我是全局性配置的,就是main.js中的这句话:

    wfaceboss
  • windows下MmAccessFault->MiDispatchFault处理过程说明

    MmAccessFault函数中查看到faultaddress对应的pte无效之时,查看TempPte.u.Soft.Prototype,

    kkindof
  • 配置Tomcat的虚拟主机 原

    说明: 在配置文件中搜索8080找到如上所示参数,将默认的8080端口改为80端口,更改完成后重启服务。

    阿dai学长
  • 聊聊openjdk的BufferPoolMXBean

    java.management/java/lang/management/PlatformManagedObject.java

    codecraft
  • AJAX跨域请求JSONP 原

    JSONP(JSON with Padding)是一个非官方的协议,它允许在服务器端集成Script tags返回至客户端,通过javascript callb...

    tianyawhl

扫码关注云+社区

领取腾讯云代金券