问题描述
HashMap一定2倍扩容,因为存储位置由(length-1)&hash(key)确定,如果用hash(key)%length确定存储,不就不用必须2倍扩容了吗?可以随意扩容,为什么不采用?是因为hash(key)%length性能较(length-1)&hash(key)低?
HashMap一定2倍扩容,因为存储位置由(length-1)&hash(key)确定,如果用hash(key)%length确定存储,不就不用必须2倍扩容了吗?可以随意扩容,为什么不采用?是因为hash(key)%length性能较(length-1)&hash(key)低?
摘自本人的文章 https://segmentfault.com/a/11...
这是一个常见的面试题。这个问题描述的设计,实际上为了服务于从Key映射到数组下标index的Hash算法。
前面提到了,我们为了让HashMap存储高效,应该尽量减少哈希碰撞,也就是说,应该让元素分配得尽可能均匀。
Hash值到数组下标需要一个映射的算法。这个计算方式就是3.2中有出现的(n - 1) & hash
。
我们来进一步演示一下这个算法:
key="book"
book
的hashCode值,结果为十进制的3029737,二进制的101110001110101110 1001。通过这种与运算的方式,能够和取模运算一样的效果hashCode % length
,在上述例子中就是3029737 % 16=9
。
并且通过位运算的方式大大提高了性能。
可能到这里,你还是不知道为什么长度必须是2的幂次方,也是因为这种位运算的方法。
长度16或者其他2的幂,Length-1的值是所有二进制位全为1,这种情况下,index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀,Hash算法的结果就是均匀的。如果HashMap的长度不是2的幂次方,会出现某些index永远不会出现的情况,这个显然不符合均匀分布的原则和期望。所以在源码里面一直都在强调power-of-two expansion
和size must be power of two
。
......
@waterDoge 的回答应该是正确的。
对于HashMap两倍扩容的原因我也一直有这个疑问,如果仅仅是因为 (length - 1) & hash
这种hash算法比 (length - 1) % hash
执行效率高,就必须要求容量是2的n次方,那这样也太得不偿失了。虽然位运算确实执行速度快,但取余运算的速度也不慢,性能相差并不大。网络上大多都说是这个原因,但仔细思考一下,使用取余运算作为hash算法的好处更多,hash到的结果一样,同时还不要求length必须是2的n次方。
@waterDoge 所说的扩容时重新分配操作更简单应该是必须2倍扩容的主要原因,扩容时,所有的元素都要重新分配,就相当于要对所有的元素全部重新 put 一遍,这是一个极其耗资源、耗时的过程,对这个过程的优化非常有必要,我想这也是HashMap设计成table length必须是2的n次方的原因。
3 回答2.3k 阅读✓ 已解决
3 回答3.8k 阅读✓ 已解决
8 回答3.1k 阅读
4 回答2.4k 阅读✓ 已解决
3 回答2.3k 阅读✓ 已解决
1 回答1.9k 阅读✓ 已解决
3 回答1.5k 阅读✓ 已解决
按位和运算比求余运算快是一方面,还有很重要的一点就是这种扩容方式下对元素的重新分配操作更简单,尤其是在碰撞较多的情况下。
原先在
oldTab[i]
位置的元素在resize后要么在newTab[i]
,要么在newTab[i+oldCap]
, 而且只有oldTab[i]
上的元素会被分配到这两个位置对节点链表
oldTab[i]
做rehash时,只需要根据hash&oldCap
是否等于0拆分成low、high两个链表,然后直接赋值newTab[i] = low, newTab[i+oldCap] = high
即可。如果是随意扩容,rehash时就需要对每个元素做如下操作:
*oldCap为扩容前数组大小
*从java 8开始, 碰撞的元素还可能是以树的形式存储,处理方式略有差异