HashMap采用2的幂次方长度的设计，主要是为了简化索引计算，提高性能，并减少哈希碰撞。
减少哈希冲突
先说结论：2 的幂次方的容量，可以更均匀地分布哈希值，减少哈希冲突。
先看不是2 的幂次方的例子。
例如：长度为9时候，3&(9-1)=0 ，2&(9-1)=0 ，都在0上，碰撞了。
比如：3&(9-1)
3 & 8 = 0000 0011 & 0000 1000 = 0000 0000 = 0
结果是0
比如：2&(9-1)
2 & 8 = 0000 0010 & 0000 1000 = 0000 0000 = 0
结果也是 0。
这两个不同的哈希值，都映射到了相同的索引 0，这增加了哈希冲突的可能性。
2 的幂次方的容量，可以更均匀地分布哈希值，减少哈希冲突。
例如：长度为8时候，3&(8-1)=3 ，2&(8-1)=2 ，不同位置上，不碰撞。
- 数字 3 的二进制表示是
0000 0011 - 数字 8 的二进制表示是
0000 1000 - 数字 8 减去 1 得到 7，7 的二进制表示是
0000 0111
所以，计算 3 & (8 - 1) 实际上就是计算：
0000 0011 & 0000 0111 ----------- 0000 0011
结果为：3
2&(8-1)，计算为：
2 & (8 - 1) = 0000 0010 & 0000 0111 = 0000 0010
结果为：2
没有冲突，这样，哈希表的性能会更加稳定。
高效扩容
HashMap 在容量不足时会进行扩容，新的容量也是 2 的幂次方。
扩容时，每个元素的位置要么保持不变，要么移动到新位置（索引 + 旧容量），这使得重新分布元素的过程更简单高效。
比如扩容前长度是8，扩容后长度是16
第一种情况：
扩容前：
00000000 00000000 00000000 00000101
&00000000 00000000 00000000 00000111 8-1=7
-------------------------------------
101 ===== 5 原来脚标位是5
扩容后：
00000000 00000000 00000000 00000101
&00000000 00000000 00000000 00001111 16-1=15
-------------------------------------
101 ===== 5 扩容后脚标位是5（原脚标位）
第二种情况：
扩容前：
00000000 00000000 00000000 00001101
&00000000 00000000 00000000 00000111 8-1=7
-------------------------------------
101 ===== 5 原来脚标位是5
扩容后：
00000000 00000000 00000000 00001101
&00000000 00000000 00000000 00001111 16-1=15
-------------------------------------
1101 ===== 13 扩容后脚标位是13（原脚标位+扩容长度）
扩容后到底是在原来位置，还是在原脚标位+扩容长度的位置，主要是看新扩容最左边一个1对应的上方数字是0还是1。
如果是0则扩容后在原来位置，如果是1则扩容后在原脚标位+扩容长度的位置。
快速计算索引
使用键的哈希值计算元素在哈希表中的索引时，常用公式是：index=hash&(capacity−1)。
当容量是 2 的幂次方时，capacity−1 的二进制表示会全是 1，这样与操作就相当于取哈希值的后几位，这比取模操作（%）更高效。
// 假设HashMap的长度为2的幂次方，例如16 int capacity = 16; // 假设有一个哈希函数hash() int hash = hashFunction(key); // 使用位运算计算索引位置 int index = hash & (capacity - 1);
在这个例子中：(capacity – 1)等于15，在二进制中为“0111”，通过与哈希值进行位运算，可以快速地得到索引位置。
这种方法比使用取模运算hash % capacity更高效，因为位运算的速度通常比取模运算快得多。
陈睿mikechen
十余年BAT架构经验，资深技术专家，就职于阿里、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》