2的负x次幂图像_为什么HashMap的长度是2的整数次幂？

先说答案：

为了

加快哈希计算

以及

减少哈希冲突

我们都知道为了找到 KEY 的位置在哈希表的哪个槽里面，需要计算

hash(KEY) % 数组长度

但是！% 计算比 & 慢很多

所以用 & 代替 %，为了保证 & 的计算结果等于 % 的结果需要把 length 减 1

也就是

hash(KEY) & (length – 1)

这个 hash(KEY) 没什么可说的，调用 Object 里面的 native 方法完成计算，一般返回的是一个整数，至于是偶数还是奇数就不一定了

我做了一个小实验：

假设现在数组的长度：2 ^ 14 = 16384

String key = “zZ1!.” 的 hash 值为 115398910

public static void main(String[] args) {
        String key = "zZ1!.";
        System.out.println(key.hashCode());// 115398910
}

hash & (length – 1) = 115398910 & 16383 = 6398 （你可以使用电脑的计算机验证一下是不是对的）

6398 的二进制是 ‭0001100011111110‬

hash % length = 115398910 % 16384 = 6398

结果确实一样，但是 & 运算更快！

还有一个有意思的事就是：因为扩容为 2 的倍数，根据 hash 桶的计算方法，元素哈希值不变而通过 % 计算的方式会因为 length 的变化导致计算出来的 hash 桶的位置不断变化。数据一致在漂移，影响性能！！

假设现在数组的长度 length 可能是偶数也可能是奇数

length 为偶数时

，length-1 为奇数，奇数的二进制最后一位是 1，这样便保证了 hash &(length-1) 的最后一位可能为 0，也可能为 1（这取决于 h 的值），即 & 运算后的结果可能为偶数，也可能为奇数，

这样便可以保证散列的均匀性

。

例如 length = 4，length - 1 = 3, 3 的 二进制是 11
若此时的 hash 是 2，也就是 10，那么 10 & 11 = 10（偶数位置）
hash = 3，即 11 & 11 = 11 （奇数位置）

而如果 length 为奇数的话，很明显 length-1 为偶数，它的最后一位是 0，这样 hash & (length-1) 的最后一位肯定为 0，即只能为偶数，这样任何 hash 值都

只会被

散列到数组的

偶数下标位置

上，这便

浪费了近一半的空间

length = 3， 3 - 1 = 2，他的二进制是 10
10 无论与什么树进行 & 运算，结果都是偶数

因此，length 取 2 的整数次幂，是为了使不同 hash 值发生碰撞的概率较小，这样就能使元素在哈希表中

均匀地散列

。

Tags: map