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

HashMap源码解析JDK1.7版本(一)

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

HashMap源码解析JDK1.7版本(一)

 HashMap的常规知识点总结

HashMap的数据结构是什么,代码中是怎么实现这种数据结构的

HashMap的数据结构是数组+链表。代码中采用静态内部类Entry来存储数据的,Entry的数据结构如下:

可以看到Entry中存储了4个成员变量,存储的key和value,key的hash值和类型为Entry的next变量。正是这个类型为Entry的next变量,让HashMap有了链表的数据结构。当多个Entry存储在数组中的相同位置时,后续的Entry会先获取到已存在的Entry对象,然后将已存在的Entry对象赋值给next变量,这样Entry节点之间就存在了引用,链表的数据结构也就形成了!

相关源码如下:

 

 这种Hash冲突时,将原先的Entry对象赋值给新的Entry的next成员变量的插入方式,保证了最新的Entry总是在链表的头部,因此也被称为“头插法”。

HashMap的默认初始化大小是16,默认的负载因子是0.75,默认的负载因子0.75是如何选择的

当我们创建HashMap时没有传入初始化参数,默认调用的就是无参构造器。在HashMap的无参构造器中,会调用HashMap的有参构造器,传入默认的初始化容量16和默认的负载因子0.75。

 

 

 那么默认的负载因子0.75是如何选择的呢,这个可以看HashMap类上的注释。

 可以看到负载因子选择为0.75是在时间和空间上做了比较好的权衡,如果负载因子过大,虽然会降低空间开销,但是会增加查找的成本。增加查找成本的原因主要是因为负载因子过大会增大hash冲突的概率,如果hash冲突变多,就会形成更多的链表,而数组查找的时间复杂度是O(1),链表查找的时间复杂度是O(n),可想而知,查询速度肯定会变慢。

HashMap的hash算法是怎么设计的,为什么不直接取key的hashCode的值

 可以看到在JDK1.7中,HashMap的hash函数的设计还是比较复杂的。先是对key的hashCode进行了异或运算,然后又进行了无符号右移,之后又异或运算。那么为什么不直接取key的hashCode的值呢?

这个又得先了解下,插入的value存放在数组的哪个位置是怎么计算的。

 可以看到,h表示的是key经过hash函数后返回的值,length表示hashMap数组的长度,key经过hash函数后返回的值和hashMap数组长度减1进行按位与运算,以此来得到value存放在数组的下标。

正是因为计算插入数组位置的这种方式,如果直接取的key的hashCode,在默认的初始化容量下,那么真正参与运算的有效位数就只有key的hashCode的最后4位,这样整个hashMap的hash冲突就会变高,查询的效率就会变慢,所以要进行无符号右移,然后异或运算,主要就是让key的hashCode的高位也能够参与运算,这样就会减少hash冲突。在JDK1.8中,hash函数的设计和JDK1.7的不太一样,但是主要的目的还是为了尽可能的实现散列分布,减少hash冲突。

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

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

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