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

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

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

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

HashMap的常规知识点总结 HashMap的Entry在数组中存放的索引位置是如何确定的

 

 

 可以看到如果key为null,那么必定是存放在数组中索引为0的位置上,即数组的第一个槽位。如果key不为null,那么会先计算出key的hash值,然后和数组长度减1做按位与运算,从而得出数组索引下标。很多博客都说是key的hash值和数组长度取模运算,其实是不对的。计算索引位置的函数这么设计,在我看来主要是在计算机中,按位与运算比取模运算更快。

源码中的注释多次提到HashMap的数组容量大小必须是2的倍数是为什么

  我们已经分析过Entry在数组中存放的索引位置是根据key的hash值和数组长度减1做按位与运算得到的,正是因为这种计算Entry在数组中存放的索引位置的函数设计,限制了数组的容量大小必须是2的n次幂。

  2的n次幂用2进制表示就是1后面n个0,比如十进制16表示为2进制就是0001 0000。16减1,表示为2进制是0000 1111,这样和key的hash值做按位与运算,得到的结果必定在0到15之间,刚好是数组索引的范围。

  但是如果数组的容量不是2的n次幂,比如数组的长度为15,表示为2进制就是0000 1111。按照源码中计算索引位置的函数,15需要先减1,然后和key的hash值做按位与运算。15减1后,表示为2进制就是0000 1110,这时和key的hash值做按位与运算,真正的有效位就只有3位,按位与运算后可能的值为0000 0000, 0000 1000, 0000 1100, 0000 1110, 0000 1010, 0000 1000, 0000 0110, 0000 0100, 0000 0010。可以看到2进制的最低位必定是0,而可能的值虽然都在数组索引范围内,但是有一些数组索引根本不可能通过按位与运算得到。

  总结来说,HashMap计算Entry在数组中存放的索引位置的方式决定了数组的容量大小必须是2的n次幂,如果不是2的n次幂,那么会存在某些数组索引不会被使用,从而导致了hash冲突增多,查询效率降低,同时不使用的数组槽位也浪费了内存空间。

如果创建HashMap时传的初始化容量不是2的倍数,会破坏了数组长度是2的n次幂的规则吗

 可以看到,如果我们创建HashMap时,传入了初始化容量,那么会先进行一系列的判断。如果小于0会抛出异常,如果大于最大容量会直接使用最大容量,而最大容量是2的30次幂,也是符合数组长度是2的n次幂的规则的,后续又将初始化容量赋值给threshold变量。

因为HashMap是按照lazy-load原则,在使用的时候才会真正的初始化,所以我们继续看put的源码

  

 进入put方法的时候,table数组为null,就会进入数组的初始化方法inflateTable,传入的参数正是我们自定义的初始化容量threshold。然后调用roundUpToPowerOf2获取到大于或等于自定义初始化容量的最小的2的n次幂,然后将得到的2的n次幂,作为数组的长度创建出数组。

highestOneBit方法获取的是int类型的值转化为2进制后,最高位的表示的十进制的值,而传入highestOneBit的参数是先减1,再右移1位,返回的结果是最高位的表示的十进制的值,那也就等于获取到大于或等于自定义初始化容量的最小的2的n次幂。这里比较难,可以仔细思考一下,或者直接去调用这个方法,获取到输出结果查看,记住这个结论就可以!

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

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

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