Java基础——HashMap 的长度为什么是 2 的幂次方

HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方

在Java中，表达式 (n - 1) & hash 常用于计算哈希表中键的索引。其中 n 表示哈希表的大小（通常为2的幂），hash 表示键的哈希码。

表达式 (n - 1) & hash 计算了 n - 1 和 hash 的按位与。由于 n 是2的幂，所以 n - 1 的所有低位都被设置为1。当这个值与 hash 进行按位与时，它实际上是将 hash 除以 n 后取余数，这样可以确保结果索引在界内（介于0和n-1之间）。

下面是一个例子：

int n = 16; // 哈希表大小（2的幂）
int hash = 42; // 键的哈希码
int index = (n - 1) & hash; // 哈希表中键的索引

在这个例子中，(n - 1) & hash 计算了 (16 - 1) & 42, 相当于 15 & 42. 在二进制中，相当于：

   1111 (15)
&101010 (42)
-------
   1010 (10)

因此，在这种情况下，在大小为16的哈希表中，具有哈希码为42的键的索引将是10。