HashMap中扩容为什么是2的n次幂

为啥容量都是 2 的幂？ 容量是 2 的幂时，key 的 hash 值然后 & (容量-1) 确定位置时碰撞概率会比较低，因为容量为 2 的幂时，减 1 之后的二进制数为全 1，这样与运算的结果就等于 hasｈ值后面与 1 进行与运算的几位。

下面是个例子。

hash HEX(97)  = 0110 0001‬
n-1  HEX(15)  = 0000 1111
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1
hash HEX(99)  = 0110 0011‬
n-1  HEX(15)  = 0000 1111
--------------------------
         结果  = 0000 0011
# 计算得到位置是 3
hash HEX(101)  = 0110 0101‬
n-1  HEX(15)   = 0000 1111
--------------------------
         结果   = 0000 0101
# 计算得到位置是 5

如果是其他的容量值，假设是 9，进行与运算结果碰撞的概率就比较大。

hash HEX(97)  = 0110 0001‬
n-1  HEX(09)  = 0000 1001
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1
hash HEX(99)  = 0110 0011‬
n-1  HEX(09)  = 0000 1001
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1
hash HEX(101)  = 0110 0101‬
n-1  HEX(09)   = 0000 1001
--------------------------
         结果   = 0000 0001
# 计算得到位置是 1

另外，每次都是 2 的幂也可以让 HashMap 扩容时可以方便的重新计算位置。

hash HEX(97)  = 0110 0001‬
n-1  HEX(15)  = 0000 1111
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1
    
hash HEX(97)  = 0110 0001‬
n-1  HEX(31)  = 0001 1111
--------------------------
         结果  = 0000 0001
# 计算得到位置是 1

参考：HashMap 源码分析解读

嗨嗨

学习下

学习

666

学习学习

学习学习

这样计算哈希碰撞概率低

学习

学习学习

学习

学习

学习了

1

6666

1

1

1

1

1