HashMap2倍扩容,为什么不用hash(key)%length存储,这样就不用必须2倍扩容了啊

Question

问题描述

HashMap一定2倍扩容,因为存储位置由(length-1)&hash(key)确定,如果用hash(key)%length确定存储,不就不用必须2倍扩容了吗?可以随意扩容,为什么不采用?是因为hash(key)%length性能较(length-1)&hash(key)低?

Answer 1

按位和运算比求余运算快是一方面，还有很重要的一点就是这种扩容方式下对元素的重新分配操作更简单，尤其是在碰撞较多的情况下。

原先在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时就需要对每个元素做如下操作：

1. 算出在新数组中的位置j
2. 检查newTab[j]是否为空，如果为空则赋值到newTab[j]，否则用一个循环结构找到newTab[j]链表的末尾，将元素添加到链表末尾。

*oldCap为扩容前数组大小
*从java 8开始, 碰撞的元素还可能是以树的形式存储，处理方式略有差异

Answer 2

摘自本人的文章 https://segmentfault.com/a/11...

3.3 HashMap 的长度为什么默认初始长度是16，并且每次resize()的时候，长度必须是2的幂次方？

这是一个常见的面试题。这个问题描述的设计，实际上为了服务于从Key映射到数组下标index的Hash算法。

前面提到了，我们为了让HashMap存储高效，应该尽量减少哈希碰撞，也就是说，应该让元素分配得尽可能均匀。

Hash值到数组下标需要一个映射的算法。这个计算方式就是3.2中有出现的(n - 1) & hash。

我们来进一步演示一下这个算法：

1. 假设有一个key="book"
2. 计算book的hashCode值，结果为十进制的3029737，二进制的101110001110101110 1001。
3. 假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。
4. 把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。

通过这种与运算的方式，能够和取模运算一样的效果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。

......

Answer 3

你说对了，确实是因为性能，hashMap的容量始终是2的倍数，于是用 (lenth - 1) & hash 就能拿到数组下标，这个运算比求余快

Answer 4

@waterDoge 的回答应该是正确的。

对于HashMap两倍扩容的原因我也一直有这个疑问，如果仅仅是因为 (length - 1) & hash 这种hash算法比 (length - 1) % hash 执行效率高，就必须要求容量是2的n次方，那这样也太得不偿失了。虽然位运算确实执行速度快，但取余运算的速度也不慢，性能相差并不大。网络上大多都说是这个原因，但仔细思考一下，使用取余运算作为hash算法的好处更多，hash到的结果一样，同时还不要求length必须是2的n次方。

@waterDoge 所说的扩容时重新分配操作更简单应该是必须2倍扩容的主要原因，扩容时，所有的元素都要重新分配，就相当于要对所有的元素全部重新 put 一遍，这是一个极其耗资源、耗时的过程，对这个过程的优化非常有必要，我想这也是HashMap设计成table length必须是2的n次方的原因。