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

问题描述

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

阅读 1.1k
评论
    4 个回答
    摘自本人的文章 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 expansionsize must be power of two

    ......

      相似问题
      推荐文章