hashmap初试数组大小为什么一定要是2 的倍数

 我来答
折柳成萌
高粉答主

2018-07-29 · 繁杂信息太多,你要学会辨别
知道顶级答主
回答量:4.4万
采纳率:96%
帮助的人:6295万
展开全部
1、在hashmap 的底层源码中,首先会计算一个 key 的 hash 码,比如计算一个字符串 "1".hashcode(); 会得到 hashcode 的大小为 49,但是 hashmap 默认数组的大小是 16,所以这样肯定是不能存到数组里面的,会越界
2、需要再次通过一个 hash 函数(这个hash 函数是自己定义的)来得到一个 hash 值,在 hashmap 的底层,这个 hash 函数是用 hashcode 的低 16 位与 高16 位进行的一次异或运算如下:

为什么要进行这一步的运算呢?看下面:
这就是HashMap的高明之处。先看个例子,一个十进制数32768(二进制1000 0000 0000 0000),经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗?或许这样还看不出什么,再举个数字61440(二进制1111 0000 0000 0000),运算结果是65263(二进制1111 1110 1110 1111),现在应该很明显了,它的目的是让“1”变的均匀一点,散列的本意就是要尽量均匀分布。那这样有什么意义呢?看第3步。
3、 得到h之后,把h与HashMap的承载量(HashMap的默认承载量length是16,可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。)进行逻辑与运算,即 h & (length-1),这样得到的结果就是一个比length小的正数,我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index,这是HashTable的改进,HashTable中的算法只是把key的 hashcode与length相除取余,即hash % length,这样有可能会造成index分布不均匀。还有一点需要说明,HashMap的键可以为null,它的值是放在数组的第一个位置。

3、得到 hash 值之后,再与数组的长度-1(length-1)进行一次与运算,因为如果数组的长度是 2 的倍数,那么length-1 的二进制一定是 ...00001111...这种形式,也就是前面一定都是 0,后面全是1,那么再与 hash 值进行与运算的时候,结果一定是在原来数组大小的范围内,比如默认数组大小16-1=15 的二进制为: 00000000 00000000 00000000 00001111,某 key 的hash 值为:11010010 00000001 10010000 00100100,那么与上面做与运算的时候,值会对后面的四位进行运算,肯定会落在0~15 的范围内,假如不是 2 的倍数,那么 length-1 的二进制后面就不可能全是 1,做与运算的时候就会造成空间浪费
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式