HashMap数组长度为什么是2的n次方

HashMap是基于哈希表的数据结构实现的集合。底层是由一个Node数组构成的，在jdk1.8之后采用数组+(链表或红黑树)的方式实现。

transient Node<K,V>[] table

node数组的长度在初始化或者扩容(resize)时会被指定，无论怎么变，数组长度始终都是2的n次方。

为什么要是2的n次方？

key在table中的定位是由(length - 1) & hash确定的，length为数组的长度。因为length是2的n次方，所以length-1的二进制肯定是11111....11的形式，此时length-1和hash进行&运算时不会有空间的浪费，且位运算效率很高。假设length不是2的次幂，比如length为15，则 length-1为14，二进制为1110，和hash进行&操作，最后一位都为0，增加了碰撞，使得一些空间被浪费。

总结就是这样做可以减少哈希冲突，均匀分布元素，从代码上来说就是按位“与”的时候，每一位都能&1。

如何保证是2的n次方的？

1）初始化指定容量时，通过tableSizeFor方法返回一个目标容量的2次幂的值(如果目标容量值不是2的n次方，就会返回一个大于该目标值的最小二次幂，如cap为10则返回16)。

2）扩容即resize()得到的新数组长度也是2的n次方。实际数组初始化也是首次put值时通过resize方法完成的。

扩容得到的新数组的长度newCap有三处赋值，可以看到都是2的n次幂。对应图中：1是通过位运算扩容为原长度的2倍；2是hashmap初始化时指定的；3是默认值16。

这里源码中还有个小细节的处理，就是hash()对key的处理并不是只取hashcode。可以说每一个细节都在尽可能的优化，存在必有其原因。