目录
HashMap的数组最大容量为什么要设计为2的30次方?而不是2的31次方-1?
回到开头,为什么已经选用了int类型,什么不用2^31-1,而是用了2^31?
一、问题
今天看HashMap源码的时候看到了下面这行,数组的最大容量
1 << 30表示1左移30位,也就是表示2的30次方。
不由得很是疑惑,既然已经选用了int类型,int占4个字节,32位,最左边1个符号位,还剩31位用来表达范围,31位全是1的情况下,int类型可以表达的最大值也就是2^31-1=2147483647,相当于是21亿+,而2^30=1073741824,相当于10亿+,那HashMap的容量可以设计为10亿+,为什么不能设计为21亿+呢?
带着问题继续研究源码
要搞清楚为什么设计成2^30次方的关键就在于数组容量为什么一定要设计为2的幂(2的n次方)?
二、数组容量为什么一定要设计为2的幂(2的n次方)?
1、首先要清楚HashMap的底层基本原理
HashMap的基本原理是数组+链表+红黑树。
数组初始容量是16,每次添加元素时,需要先计算key的hash值来决定存放在哪个桶中(即数组中的哪个位置),然后将value值放在对应的桶中。每个桶中存放的是一个链表,链表长度默认为8。
扩容:当数组元素数量>=数组容量*扩容因子(默认是0.75)时,触发扩容,所以默认第一次扩容16*0.75=12,每次扩容为原来数组容量的2倍,当数组容量大于等于64时,链表长度达到8时,链表会转为红黑树(自平衡的二叉搜索树)。
补充:当数组容量<64,且某个链表节点数达到阈值8时,会优先触发扩容,并不是直接转红黑树。
2、再来看下怎么通过hash值决定存放在哪个桶中?
首先看下hash值
1)hashCode()是一个本地方法(基于其他语言实现),会返回一个32位的整数(int类型)。
2)h >>> 16,对这个hash值进行无符号右移16位的运算,左边补0,结果就是上面得到Hash值的高16位(左边的16位)。
3)h ^ (h >>> 16)然后对h和第二步的结果进行按位异或运算,也就是对原Hash值的高16位和低16位进行按位异或运算,最终的到的值就是HashMap中要用的hash值。
这里也是为什么Object对象中要拥有hashCode()方法的原因之一。
为什么要进行异或运算呢?
原始的hashCode()
方法返回的哈希码可能分布不够均匀,尤其是在高位部分。通过 (h >>> 16)
这个无符号右移16位的操作,可以将哈希码的高半部分移到低半部分,然后再与原始哈希码做异或运算,这样可以将高位和低位的信息进行混合,增加了哈希码的随机性,减少由于哈希碰撞引发的链表过长或者树形结构过深的问题,从而提高查询和插入的效率。
再看下怎么确定当前key存放在哪个数组下标下的
当容量为16时,n-1为15,二进制为1111,然后和hash值去做按位与运算,来确定最后存放的桶的下标。(这里在调试时,n是256,有知道的大佬可以解惑吗?) 这里调试时候遇到256的原因是类加载器中也有用到map(这一点可以在调用栈中明显看到),所以第一次进的断点并不是我们想要的断点,这里是个误区,调试时需要注意。
为什么要做按位与而不用模运算符%?
按位与操作是计算机底层硬件直接支持的,执行速度非常快。
而且按位与可以直接获取原来hash值的低位二进制,如下:
1011 1101------199
0000 1111------15
-------------------------
0000 1101-----13
所以最终决定存放在哪个桶的时候是根据hash值取低位的二进制来决定的,并不是很多人说的hash对数组长度取余。结果范围始终在0到n-1之间,正好对应数组的索引。
为什么要n-1呢?
为了保证得到的全是1的二进制。
n是一个什么样的数的时候才能保证n-1的二进制全是1呢?
只有当n是2的幂的时候,n-1的二进制才能保证全1。
3、总结
所以设计者规定了,HashMap中的数组容量必须是2的幂(即2的n次方)。
并且在有参构造器中,可以指定数组容量。
通过这个算法得到的返回值,一定是大于且最接近指定容量的2的幂。
如:指定容量是70,返回值就会是128=2^7
为什么到16就停止了?
右移的次数加起来 1+2+4+8+16=31,最多只有31位啊。
三、HashMap的数组最大容量为什么要设计为2的30次方?而不是2的31次方-1?
现在已经知道数组的容量一定要保证2的幂
回到开头,为什么已经选用了int类型,什么不用2^31-1,而是用了2^31?
在int范围内,2的幂的最大值是2^30,2^31-1是int类型能表示的最大值,但它不是2的幂啊!!!
所以很多人会说最大容量是2^30的原因是,要保证2的幂,这是关键。
标签:hash,HashMap,容量,16,31,数组,次方 From: https://blog.csdn.net/weixin_45967584/article/details/136918330