栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

HashMap 整理

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

HashMap 整理

HashMap 1.7 和 HashMap1.8 有比较大的区别,可以说1.8有很大的改进。而其中的默认初始化容量16,负载因子0.75,扩容2倍,基本没变。

  • 扩容

1)1.7版本的时候,HashMap的数据结构是:数组 + 链表(Entry)

        扩容条件: 同时满足,所有Entry加起来大于等于阈值(负载因子乘以初始化容量)和hash碰撞,二者缺一不可。

        Hash 碰撞:通过 key 部分进行hash计算,得出的数组下标的值,如果原来这个数组下标位置原来已经有元素了(默认Entry是null),就会产生Hash碰撞。

        过程:我们使用put()方法的时候,会调用addEntry()方法,然后进行判断是否需要扩容,如果需要就调用resize()方法创建一个2倍大的数组,并调用transfer()方法将原来这里面的Entry搬运过来。而搬过来时会对Entry进行rehash(重新计算hash值),得到新的数组下标。这时,相邻两个Entry有可能还是会进到同一个链表上,而插入的方法是头插法,如果原来的链表全都还在同个链表上,就会顺序变反了。

如果只满足:所有Entry加起来大于等于阈值,那么最大容量是16(一直没有发生hash碰撞),第17个才会扩容  

 如果是一开始前11个都只满足hash碰撞,后15个一直没有hash碰撞,那么最多容量是26

 2)1.8版本时,HashMap的数据结构是:数组 + 链表(Node)/ 红黑树

        扩容条件:① 所有Node加起来大于等于阈值

                          ② 单个链表上Node数大于8且数组容量小于64

        二者满足其中一个就扩容,注意还是会有hash碰撞,只不过不作为扩容条件。

        过程:我们使用put()方法的时候,会判断是否需要扩容,如果需要就调用resize()方法,这个方法会创建一个新的2倍大的数组,然后将Node节点rehash之后得到新的下标,搬到对应的下标去。而这里采用的是尾插法,就跟原来的顺序还是一样的。某个链表已经是红黑树了,那么就创建一颗红黑树,再将节点搬过去。

        注意:当单个链表上的Node数大于8且数组容量大于64时,会将该链表转换成一颗红黑树,其他链表如果没有达到该条件,就还是一条链表。如果某颗红黑树后面节点变成小于等于6,就又转换成链表,之所以不是7、8,是为了避免频繁转换的情况,因为转换也是会影响消耗性能的。

  •  头插法与尾插法的区别

        1.7版本由于采用了头插法,在多线程的情况下,可能会造成死循环的情况,即产生了环形链表。因为该方法会造成链表的顺序变反了,而在多线程的情况下,如果一个线程先进行了扩容,等到第二个线程扩容的时候,原来的链表已经反了。

        这时候,采用头插法还会再次把原来的链表反过来,而我们前面在扩容中提到,相邻的两个节点可能会rehash到同一个链表上。这时,会出现上一个Node的next,在第一个线程中已经指向了下一个Node;而第二个线程,会将下一个Node的next 指向 上一个Node,这样就形成一个环形链表。

        而1.8采用尾插法,即使在多线程的情况下,也不会产生环形链表。因为扩容在尾插之后,链表的顺序还是一样的,所以就算有第二个线程再次扩容,也不会有死循环。

        HashMap无论是1.7还是1.8,都不是线程安全的,都没有加锁。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/978821.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号