【Java基础】HashMap的底层数据结构是怎样的?
创始人
2024-05-30 19:52:23
0次

        HashMap就是以Key-Value的方式进行数据存储的一种数据结构。

        HashMap在jdk1.7之前和jdk1.8之后的底层数据结构是不一样的。

        在jdk1.7之前是数组+链表的形式,并通过entry节点保存key和value值;当Hash冲突比较严重的时候,在数组上形成的链表就会变的越来越长,由于链表是不支持索引查询的,所以这个时候要想在链表中找一个元素的话就需要遍历一遍链表,最坏的结果是查找的元素在链表的末尾,这样显然会导致查询效率大大降低;

        所以为避免这一问题的发生,在jdk1.8加入了红黑树,红黑树是一个自平衡的二叉查找树,使用红黑结点并使得两端保持相对平衡;所以jdk1.8后HashMap的底层数据结构是数组+链表+红黑树的形式。

        Jdk8开始当链表高度到8、数组长度超过64时,会将链表转为红黑树,元素以内部类使用Node类存储Key和Value。

        通过计算key的hash值,进行二次hash然后对数组长度进行取模,获得对应数组下标; 获得下标后,会先判断下标位置是否存在元素,如果下标位置没有元素,则直接创建Node存入数组;如果存在元素就会产生hash冲突;

        冲突产生后,先对key值进行equals()比较,如果key值相同则取代该元素,不同则通过尾插法插入链表,在插入的同时遍历链表计算高度,如果中途存在key值相同的元素则进行覆盖;如果没有就直接插入到链表尾部。

        插入完成,对链表高度进行判断,如果链表高度达到8,并且数组长度到64则转变为红黑树;反之,如果红黑树结点低于等于6则会退化为链表。

        注意,如果Key为null的话,则存在下标0的位置上。

jdk7中HashMap底层数据结构图:

jdk8中HashMap底层数据结构图:


 ——》以上讲述了HashMap底层数据结构是怎样的,同时这个题也是面试的高频提问题。在回答过程中,还穿插 了为什么在jdk8要加入红黑树这一问题。以上是自己总结的面试题,根据自我理解和查找资料得出,欢迎各位CSDN的友友们前来指教!


相关内容

热门资讯

中央气象台发布大风蓝色预警 多... 预计11月17日08时至18日08时,青海北部、甘肃大部、内蒙古大部、宁夏、陕西北部、山西、河北北部...
景区招保洁参照公务员体检标准 ... 景区招保洁参照公务员体检标准!近日,某景区招聘53名派遣保洁人员的消息引起了关注。招聘信息显示,应聘...
氯化铵市场年内罕见快速上涨 创... 氯化铵市场正经历一轮年内罕见的快速上涨。截至11月16日,氯化铵工业级价格达到730元/吨,创下年内...
19岁留学生在泰被成功解救 警... 泰国警方于11月14日在芭提雅一家酒店内找到一名19岁的中国留学生,所幸他身体没有受到伤害。此前,有...
女子在KTV电梯内遭陌生男子搂... 11月11日晚上11点,海口一名年轻女子走进KTV电梯,准备去三楼找朋友唱歌。她全程没沾过酒,脑子清...
凯特患癌后首次陪同威廉出访 抗... 凯特患癌后首次陪同威廉出访。2024年3月,凯特王妃证实自己得了癌症,正在接受预防性化疗。同年9月,...
“全程只服一次”流感新药纳入医... 中国疾控中心监测显示,秋冬流感流行季已逐渐开启。患上流感后高烧酸痛令人难受,传统抗流感药往往需要连续...
别让“今天就整改”成了一句客套... 别让“今天就整改”成了一句客套话。一句“今天就整改”,一个月过去,那块水泥还压在原地。这不是工作不力...
留学生遭诱骗至泰国被解救 跨境... 一名19岁的中国留学生入境泰国不到一天,就被跨国电信诈骗团伙控制。家属收到勒索视频后,中泰有关部门迅...
平价羽绒服为啥集体断货 中产过... 平价羽绒服为啥集体断货 中产过冬新宠引发抢购热潮。这个冬天,仓储式会员超市的羽绒服成了中产过冬的新宠...
大范围雨雪天气来袭 收下安全出... 今天冷空气继续影响长江以北大部分地区,预计将迎来降温。明后两天(17日至18日),冷空气势力将进一步...
柴油发电机订单排到明年年底 需... 近年来,国内数据中心和智算中心的建设加速,对大功率柴油发电机组的需求显著增加。据行业预测,到2026...
中小学幼儿园将聘任健康副校(园... 中小学校、幼儿园将聘任健康副校(园)长,由医疗卫生机构选派。国家卫生健康委、教育部、国家中医药局、国...
上海地铁开启“老人机模式” 更... 近日,不少网友注意到上海地铁的一些站点进行了升级,变得更加友好,尤其是对老年乘客。中山公园站和江苏路...
男子拆攒了18年的红包拆了3小... 最近,广东一位男子一次性拆开了攒了18年的红包,整整花了3个小时,最终清点出8523元。这一事件在评...
侯明昊品牌活动售票1599元起... 侯明昊品牌活动售票1599元起。11月15日,侯明昊工作室发布声明称,与雪中飞品牌就2026年11月...
哥哥遮挡号牌弟弟代驾被罚直喊冤... 11月10日晚,张家界市公安局交通管理支队直属一大队开展夜间交通违法专项巡查执法,重点查处涉牌涉证违...
96岁父亲经常骑三轮去看70岁... 96岁父亲经常骑三轮去看70岁女儿。近日,96岁父亲骑车看望70岁女儿的画面引发关注。70岁女儿心疼...
一条视频了解APEC 开放创新... 开放、创新、合作,是2026年APEC“中国年”的三大关键词。这三个词回应了当前亚太地区面临的一些重...
警方回应香港迪士尼报案 电子门... 警方回应香港迪士尼报案 电子门票二维码被盗引发关注。近日,香港迪士尼乐园约有1.7万个电子门票二维码...