IT学习站-137zw.com

more +资源更新Forums

more +随机图赏Gallery

价值5980元高端JAVA架构课程 精英培训计划视频教程 java架构价值5980元高端JAVA架构课程 精英培训计划视频教程 java架构
价值3600元的中文网第八期php cms 视频 完整版视频课程价值3600元的中文网第八期php cms 视频 完整版视频课程
10节课让你成为滚床单高手  强烈推荐 屌丝的福音10节课让你成为滚床单高手 强烈推荐 屌丝的福音
最新流出的传智博学谷黑马python5.0课程最新流出的传智博学谷黑马python5.0课程
价值19000元的小码哥大神班IOS五期不加密版本教程价值19000元的小码哥大神班IOS五期不加密版本教程
从网络基础概念到校园网整体规划组建系列视频教程(共40集)从网络基础概念到校园网整体规划组建系列视频教程(共40集)

刨死你系列——LinkedHashMap剖析(基于jdk1.8)

刨死你系列——LinkedHashMap剖析(基于jdk1.8)

[复制链接]
123456835 | 显示全部楼层 发表于: 2019-11-14 09:45:02
123456835 发表于: 2019-11-14 09:45:02 | 显示全部楼层 |阅读模式
查看: 109|回复: 0

你还没有注册,无法下载本站所有资源,请立即注册!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
一、概述

  1.8版本的LinkedHashMap 继承自 HashMap,在 HashMap(数组链表+红黑树) 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外,LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下,该特性很有用,比如缓存。在实现上,LinkedHashMap 很多方法直接继承自 HashMap,仅为维护双向链表覆写了部分方法。所以,在学习LinkedHashMap前,你要先了解HashMap。其结构可能如下图:
刨死你系列——LinkedHashMap剖析(基于jdk1.8)  技术博客 1408728-20190907194112450-2033381319

二、源码解析

2.1 Entry的继承体系

  LinkedHashMap数据结构相比较于HashMap来说,添加了双向指针,分别指向前一个节点——before和后一个节点——after,从而将所有的节点已链表的形式串联一起来,让我们来看一下它们的继承关系。
刨死你系列——LinkedHashMap剖析(基于jdk1.8)  技术博客 1408728-20190907183303376-25459084

  HashMap 的内部类 TreeNode 不继承它的了一个内部类 Node,却继承自 Node 的子类 LinkedHashMap 内部类 Entry。这里这样做是有一定原因的,这里先不说。先来简单说明一下上面的继承体系。LinkedHashMap 内部类 Entry 继承自 HashMap 内部类 Node,并新增了两个引用,分别是 before 和 after。这两个引用的用途不难理解,也就是用于维护双向链表。同时,TreeNode 继承 LinkedHashMap 的内部类 Entry 后,就具备了和其他 Entry 一起组成链表的能力。
2.2成员变量

具体看下面代码:2.3构造方法

由于LinkedHashMap继承HashMap,构造方法基本类似,唯一的区别就是添加了前面提到的accessOrder,默认赋值为false——按照插入顺序来排列,这里主要说明一下不同的构造方法。LRU(Least Recently Used)最近最久未使用算法。会在后面介绍该算法.
2.4 put()方法

让我们来看一下LinkedHashMap是怎么插入Entry的:LinkedHashMap的put方法调用的还是HashMap里的put,不同的是重写了里面的部分方法,一起来看一下:由于在前面的文章HashMap, 分析过了put方法,这里笔者就省略了部分代码,LinkedHashMap将其中newNode方法以及之前设置下的钩子方法afterNodeAccess和afterNodeInsertion进行了重写,从而实现了加入链表的目的。一起来看一下:2.5 remove()方法

与插入操作一样,LinkedHashMap 删除操作相关的代码也是直接用父类的实现。在删除节点时,父类的删除逻辑并不会修复 LinkedHashMap 所维护的双向链表,这不是它的职责。那么删除及节点后,被删除的节点该如何从双链表中移除呢?当然,办法还算是有的。上一节最后提到 HashMap 中三个回调方法运行 LinkedHashMap 对一些操作做出响应。所以,在删除及节点后,回调方法 afterNodeRemoval 会被调用。LinkedHashMap 覆写该方法,并在该方法中完成了移除被删除节点的操作。相关源码如下:删除的过程并不复杂,上面这么多代码其实就做了三件事:

  • 根据 hash 定位到桶位置
  • 遍历链表或调用红黑树相关的删除方法
  • 从 LinkedHashMap 维护的双链表中移除要删除的节点
2.6 get()方法

默认情况下,LinkedHashMap 是按插入顺序维护链表。不过我们可以在初始化 LinkedHashMap,指定 accessOrder 参数为 true,即可让它按访问顺序维护链表。访问顺序的原理上并不复杂,当我们调用get/getOrDefault/replace等方法时,只需要将这些方法访问的节点移动到链表的尾部即可。相应的源码如下:从上面的代码可以看到,LinkedHashMap的get方法,调用HashMap的getNode方法后,对accessOrder的值进行了判断,我们之前提到:由此可见,afterNodeAccess(e)就是基于访问的顺序排列的关键,让我们来看一下它的代码:

标注的情况如下图所示(特别说明一下,这里是显示链表的修改后指针的情况,实际上在桶里面的位置是不变的,只是前后的指针指向的对象变了):
刨死你系列——LinkedHashMap剖析(基于jdk1.8)  技术博客 1408728-20190907192616113-169970110

下面来简单说明一下:

  • 正常情况下:查询的p在链表中间,那么将p设置到末尾后,它原先的前节点b和后节点a就变成了前后节点。
  • 情况一:p为头部,前一个节点b不存在,那么考虑到p要放到最后面,则设置p的后一个节点a为head
  • 情况二:p为尾部,后一个节点a不存在,那么考虑到统一操作,设置last为b
  • 情况三:p为链表里的第一个节点,head=p
2.7 基于 LinkedHashMap 实现缓存

在上节中,说到LRU算法,我I们通过继承LinkedHashMap实现了一个简单的 LRU 策略的缓存。在实践前我们要补充部分知识:上面的源码的核心逻辑在一般情况下都不会被执行,所以之前并没有进行分析。上面的代码做的事情比较简单,就是通过一些条件,判断是否移除最近最少被访问的节点。看到这里,大家应该知道上面两个方法的用途了。当我们基于 LinkedHashMap 实现缓存时,通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。比如我们可以根据节点数量判断是否移除最近最少被访问的节点,或者根据节点的存活时间判断是否移除该节点等。本节所实现的缓存是基于判断节点数量是否超限的策略。在构造缓存对象时,传入最大节点数。当插入的节点数超过最大节点数时,移除最近最少被访问的节点。实现代码如下:测试代码如下:测试结果:
刨死你系列——LinkedHashMap剖析(基于jdk1.8)  技术博客 1408728-20190907193515307-1322558808

不过笔者自己也通过继承LinkedHashMap实现了LRU算法,感兴趣的小伙伴可以看看!
2.8 小结

本文对 LinkedHashMap 的源码put,get,remove进行了分析,并在文章的结尾基于 LinkedHashMap 实现了一个简单的 Cache。在日常开发中,LinkedHashMap 的使用频率虽不及 HashMap,但它也个重要的实现。在 Java 集合框架中,HashMap、LinkedHashMap 和 TreeMap 三个映射类基于不同的数据结构,并实现了不同的功能。HashMap 底层基于拉链式的散列结构,并在 JDK 1.8 中引入红黑树优化过长链表的问题。基于这样结构,HashMap 可提供高效的增删改查操作。LinkedHashMap 在其之上,通过维护一条双向链表,实现了散列数据结构的有序遍历。TreeMap 底层基于红黑树实现,利用红黑树的性质,实现了键值对排序功能。

由于个人能力问题,先学习这些,数据结构这个大山,我一定要刨平它。
参考博客:https://segmentfault.com/a/1190000012964859
    https://blog.csdn.net/ShelleyLittlehero/article/details/82957336

来源:http://www.137zw.com
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
137zw.com IT学习站致力于免费提供精品的java技术教程和python技术教程,CCNA书籍/资料/CCNP书籍/资料教程/CCIE书籍/资料/H3C学习/认证/一级建造师考试/微软学习/认证/包括基础教程和高级实战教程,同时也提供分享网站源码下载和互联网相关一系列的技术教程,我们想做的就是让知识分享更有价值!(IT学习站官方唯一域名地址:www.137zw.com 请谨防假冒网站!)本站所有资源全部收集于互联网或网友自行分享,分享目的仅供大家学习与参考,如无意中侵犯您的合法权益,请联系本站管理员进行删除处理!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

浙ICP备19022368号-1|Archiver|手机版|IT学习站-137zw.com

GMT+8, 2020-7-12 01:35 , Processed in 0.189001 second(s), 32 queries .

快速回复 返回顶部 返回列表