文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

HashMap的扩容机制

2023-09-04 21:34

关注

目录

一、HashMap的底层

二、HashMap的扩容机制原理

1、JDK1.7版本扩容

2、JDK1.8版本扩容

三、HashMap底层JDK1.7到JDK1.8的变化


底层:采用数组+链表(JDK1.7),采用数组+链表+红黑树(JDK1.8)。线程不安全。

容器:HashMap默认容器长度为16,扩容因子为0.75,以2的n次方扩容,最高可扩容30次。如第一次是长度达到16*0.75=12的时候开始扩容,16*2^1=32。

1、JDK1.7版本扩容

①:先生成新数组;

②:遍历老数组中的每个位置上的链表上的每个元素;

③:获取每个元素的key,并基于新数组长度,计算出每个元素在新数组中的下标;

④:将元素添加到新数组中去;

⑤:所有元素转移完之后,将新数组赋值给HashMap对象的table属性。

2、JDK1.8版本扩容

①:先生成新数组;

②:遍历老数组中的每个位置上的链表或红黑树;

③:如果是链表,则直接将链表中的每个元素重新计算下标,并添加到新数组中去;

④:如果是红黑树,则先遍历红黑树,先计算出红黑树中每个元素对应在新数组中的下标位置;

a:统计每个下标位置的元素个数;

b:如果该位置下的元素个数超过了8,则生成一个新的红黑树,并将根节点添加到新数组的对应位置;

c:如果该位置下的元素个数没有超过8,那么则生成一个链表,并将链表的头节点添加到新数组的对应位置;

⑤:所有元素转移完了之后,将新数组赋值给HashMap对象的table属性。

JDK1.8相较与JDK1.7在数组+链表的基础上添加了红黑树,加红黑树的目的时提高HashMap插入和查询的整体效率;

JDK1.7中链表插入采用的是头插法,JDK1.8中插入使用的是尾插法,因为JDK1.8中插入key和value时需要判断链表元素个数,所以需要遍历链表统计链表元素个数,所以正好直接使用尾插法;

JDK1.7哈希算法比较复杂,存在各种右移与异或运算,JDK1.8进行了简化,因为复杂的哈希算法目的就是提高散列性,来提供HashMap的整体效率,而1.8新增了红黑树,所以可以适当的简化哈希算法,节省CPU资源。

来源地址:https://blog.csdn.net/eg1107/article/details/128228687

阅读原文内容投诉

免责声明:

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

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

软考中级精品资料免费领

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

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

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

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

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

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

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