文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

源码解析带你了解LinkedHashMap

2024-04-02 19:55

关注

LinkedHashMap维护插入的顺序。

元素存储关系

红黄箭头:元素添加顺序
蓝箭头:单链表各个元素的存储顺序
head:链表头部
tail:链表尾部

继承体系

5088755_1577812744625_DA615EAF7757A05A68BDC4C9093BBBD8

属性

此 LinkedHashMap 的迭代排序方法:

构造方法

构造方法都是先执行父类 HashMap 的构造方法.

无参

有参

下面我们开始研究该类的主要特性是如何通过代码实现的.

按插入顺序访问

LinkedHashMap 默认 accessOrder 为 false,提供按照插入顺序的访问,并没有重写父类 HashMap 的 put 方法.但在 HashMap 中,put 的是 HashMap 的 Node 类型节点,LinkedHashMap 的 Entry 与其结构并不同,又是怎样建立起双向链表的呢?下面一起看下 LinkedHashMap 插入相关代码.

忽略未重写的 put=>putValue代码部分,我们直接观察重写的

newNode

控制新增节点追加到链表的尾部,这样每次新节点都追加到尾部,即可保证插入顺序了.
继续研究 linkNodeLast

linkNodeLast

新增节点,并追加到链表的尾部.


`// link at the end of list`

`private` `void` `linkNodeLast(LinkedHashMap.Entry<K,V> p) {`

`LinkedHashMap.Entry<K,V> last = tail;`

`// 新增于尾节点`

`tail = p;`

`// last 为null,说明链表为空`

`if` `(last == ``null``)`

`head = p;`

`// 链表非空,建立新节点和上一个尾节点的前后关系`

`else` `{`

`// 将新节点 p 直接接在链尾`

`p.before = last;`

`last.after = p;`

`}`

`}`

由此得知,通过在 HashMap 基础上新增的头尾节点,节点的 before 和 after 属性,就能实现在每次新增时,把节点直接追加到尾节点,即可达到维护按照插入顺序的链表结构的目的!

蓝色部分是 HashMap 的方法
橙色部分为 LinkedHashMap 独有方法

注意 LinkedHashMap 虽然也是双向链表,但只提供单向的按插入的顺序从头到尾访问,不及 LinkedList 般可双向无死角访问.

迭代过程中,不断访问 after 节点即可完成遍历.

1 处进行校验
2 处通过节点的 after 属性,找到后继节点

链表节点的删除

与插入操作一样,LinkedHashMap 删除操作相关的代码也是直接用父类的实现. 在删除节点时,父类不会修复 LinkedHashMap 的双向链表。那么删除及节点后,被删除的节点该如何从双链表中安全移除呢?其实在删除节点后,回调方法 afterNodeRemoval 会被调用。LinkedHashMap 重写了该方法.


`// e 为已经删除的节点`

`void` `afterNodeRemoval(Node<K,V> e) { ``// unlink`

`LinkedHashMap.Entry<K,V> p =`

`(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;`

`// 将 p 节点的前驱后后继引用置 null,辅助 GC`

`p.before = p.after = ``null``;`

`// p.before 为 null,表明 p 是头节点`

`if` `(b == ``null``)`

`head = a;`

`else`

`// 否则将 p 的前驱节点连接到 p 的后继节点`

`b.after = a;`

`// a 为 null,表明 p 是尾节点`

`if` `(a == ``null``)`

`tail = b;`

`else`

`// 否则将 a 的前驱节点连接到 b`

`a.before = b;`

`}`

删除元素的主要流程:

5088755_1583897219283_48356470140921DD4FA1E2C40982DE97

转存失败重新上传取消

LRU(Least recently used,最近最少使用)

栗子

经常访问的元素会被追加到队尾,这样不经常访问的数据自然就靠近队头,然后可以通过设置删除策略,比如当 Map 元素个数大于多少时,把头节点删除

元素被移到队尾

get 时,元素会被移动到队尾:


`public` `V get(Object key) {`

`Node<K,V> e;`

`// 调用 HashMap  get 方法`

`if` `((e = getNode(hash(key), key)) == ``null``)`

`return` `null``;`

`// 如果设置了 LRU 策略`

`if` `(accessOrder)`

`// 这个方法把当前 key 移动到队尾`

`afterNodeAccess(e);`

`return` `e.value;`

`}`

从上述源码中,可以看到,通过 afterNodeAccess 方法把当前访问节点移动到了队尾,其实不仅仅是 get 方法,执行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法时,也会这么做,通过不断的把经常访问的节点移动到队尾,那么靠近队头的节点,自然就是很少被访问的元素了。

到此这篇关于源码解析带你了解LinkedHashMap的文章就介绍到这了,更多相关Java LinkedHashMap内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯