HashMap初始容量为什么是16(必须是2的幂次方)?
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
关键词
hash碰撞位与运算(&)原因
在HashMap中会存在如下代码(详情参考HashMap源代码)
... (n - 1) & hash ...
在执行上述代码的时候，会进行位与运算，n为容量大小，n=16，对应的二进制是 01111 。
1. 当n是2的幂次方时(16)：
01111 & 00101 = 0010101111 & 01010 = 0101001111 & 01101 = 0110101111 & 00111 = 00111... 2. 当n不是2的幂次方时(11)：
01011 & 00101 = 0000101011 & 01010 = 0101001011 & 01101 = 0100101011 & 01001 = 01001...从上边可以看出：n不是2的幂次方时，会出现不同值得到相同的结果，这种现象叫做hash碰撞。在实际代码中，出现这种情况会导致结果跟预想的不一致，为了防止碰撞发生，Java要求map的容量必须是2的幂指数。
结果
1. 使用位与运算计算效率高
2. 设置容量为2的幂指数，避免了hash碰撞产生链表，使得结果可以均匀分布
3. 提高了查询效率