2.9 HashMap 的⻓度为什么是 2 的幂次⽅

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

这个算法为什么这么设计呢？

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