当前位置:首页 » 《资源分享》 » 正文

JAVA进阶篇——HashMap底层实现解析_肝铁侠的博客

24 人参与  2021年10月15日 15:23  分类 : 《资源分享》  评论

点击全文阅读


倘若有一天你去面试的时候,面试官问起了你HashMap的底层实现原理,你怎么办?是一脸懵逼支支吾吾吗?再让你自己通过代码实现你自己的HashMap的时候,难道完全破防?读完这篇文章,让我们对这个情况say no!

在这里插入图片描述

首先我们来通过下面的图看看JDK1.7时代的HashMap是如何通过数组+链表的形式进行值储存的。

在这里插入图片描述

由图中的描述可以清楚地看出来,当数组第一次被定义并且第一次被赋值的时候,这个时候的操作很简单,就是将这个值赋值到我们的table数组上面去。这个操作完成以后,然后我们进行二次put:

在这里插入图片描述
如图左下角描述所示的情况,当数组table下标出现了相等的情况的时候,此时此刻还是将肝铁侠2的值赋值给tablle[i]的,这里讲述的是JDK1.7版本下HashMap中插入的头插法,而JDK1.8版本中是用的尾插法。插入以后,我们要让数组指向链表的头部,那么链表的头部也就是头节点是不是就是table[i]的位置呀。

在这里插入图片描述

如上,最终插入完成以后的模型就是这样的:

在这里插入图片描述

那我们此时此刻是不是就可以大胆地猜测,在HashMap中,使用map.get(“name”)获取到它的value的时候,是不是就是通过int hash = “name”.hashcode,然后获取到对应table下的数组下标int i = hash % table.length获取到table[i]的具体位置的链表,然后再通过hash去对应table[i]上的链表中找到对应的值呢?

有了这个思维,我们再去看HashMap的源码就会轻松许多许多。下一期为大家带来HashMap的手动实现。

再顺带两个基本的关于HashMap的问题:

HashMap底层是怎么实现的呢?
在JDK1.7中是通过数组+链表实现的。JDK1.8中是通过数组+链表+树(红黑树)组成的。

为什么要用链表呢?
①HashMap数组元素为链表的时候,插入直接使用头插,插入复杂度O(1),即操作的数量为常数,与输入的数据的规模无关,效率是非常快的;当链表较短时候,查找数据时对性能并没有什么影响,但是如果链表一长,查找起来就很影响性能了。
②在Java8中,如果链表长度到达了8个,就会转化为红黑树,提高了查找的性能,但每次插入新的数据,都得维护红黑树的结构,复杂度为O(log n)。其实算是对查找和插入元素时性能的一个权衡,毕竟存入的效果就是用来查询的。
这个问题的答案不唯一,可以自行了解一下。


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/29910.html

数组  链表  插入  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 妻子辱我爸受贿自杀,我掏出一等军功章节选推荐_[陈素云辰朋友]小说精彩章节分享
  • 全书浏览苔藓爬满旧日诺言新上(顾砚廷慕晚夏)_苔藓爬满旧日诺言新上(顾砚廷慕晚夏)全书结局
  • 顾尘傅雅宁(神女老婆,却在背地承欢作乐+后续+结局)结局_(顾尘傅雅宁神女老婆,却在背地承欢作乐+后续+结局全书结局)结局列表_笔趣阁(顾尘傅雅宁)
  • 「老婆怀上助理的孩子后,助理要求我净身出户」章节限时抢先看‌_「黄秋雅秋雅姐刘嘉铭」后续完结版
  • 此去经年人未还,沈青禾霍沉洲_此去经年人未还,沈青禾霍沉洲
  • 我爸娶了九十九个媳妇都死了,这次准备娶我的女同学小说精彩章节免费试读_[小梅娶媳妇孤儿]全文免费在线阅读
  • 此去经年人未还结局+番外文章简述(沈青禾霍沉洲)列表_此去经年人未还结局+番外文章简述
  • 完结文寻你寻不到归期结局+完结列表_完结文寻你寻不到归期结局+完结(姜昭意盛西)
  • 江以蓁的潮起时问归期高分佳作江以蓁秦司礼全书在线
  • 「亲手逼死儿子后,男人悔不当初」后续全文免费阅读_[傅司衍轩轩佳佳]最新章节免费阅读
  • (番外)+(全书)寻你寻不到归期+后续+结局(姜昭意盛西辞)全书在线_寻你寻不到归期+后续+结局免费列表_笔趣阁(姜昭意盛西辞)
  • 全文他亲手埋葬的爱结局+番外(谢怀商温南枝)列表_全文他亲手埋葬的爱结局+番外宝藏文(谢怀商温南枝)全文他亲手埋葬的爱结局+番外在线

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1