分为两个问题，一个是为什么创建HashMap时的容量都是2的幂次方，第二个是为什么扩容时是扩大两倍。

容量为2的幂次方

目的是为了更快的取模，假设容量为N，哈希值是hash，如果N是2的幂次方，则hash % N = hash & (N - 1)

2的幂次方的二进制表示，只有最高位是1，其他位都是0，2的幂次方减一的二进制表示则全部是1。 hash & (N -1)本质上是只保留hahs的末尾几位，得到的结果一定小于N, 在0到N-1之间。

扩容扩大两倍

扩大两倍可以保证原有的元素要么保持在原来的索引上，要么移动到原索引加N的位置，可以保证数据在扩张后的分布不会变得更差。

首先map的容量都是2的幂次方，那么扩大两倍，本质上就是在取模的时候多保留一位，那么原来的哈希值如果上一位是0，则扩容后取模的结果不会变，如果上一位是1，那么扩容后取模的结果就是二进制数最前面加上1

在二进制最高位+1，相当于十进制里+N，比如从16扩大到32，那么相当于本来取4位，变成取5位，取5位相当于在原来的索引上+16

举个例子:

hash值是110010，此时map的大小是16，那么取后4位，0010做索引，也就是2

扩大两倍后（总大小是32），取后5位，也就是10010做索引，结果是18

扩大两倍后会不会有在扩容前没有hash冲突的两个hash值，扩容后hash冲突了

按照上文的结论，扩容后，原来hash值要么还在原来的索引上，要么在原来的索引+N的位置上（N是扩容前的大小）

两个索引（在扩容前不冲突）在扩容后只可能有3种情况：

  1. 两个索引位置都不变，那么扩容后也不会有冲突
  2. 两个索引的位置都+N，那么也不会有冲突
  3. 一个索引变化，另一个不变化

第三种情况，有没有可能出现，扩容前不冲突，扩容后冲突的情况。因为扩容后，索引要么不变，要么+N，如果想要扩容后发生冲突，那么需要两个hash值，为hash1，hash2

假设

  1. hash1与hash2在扩容前不冲突，扩容后冲突。

则一定有:

  1. hash1在扩容后+N，hash2扩容后不移动

  2. 扩容前hash2的索引正好比hash1大N

  3. 扩容前取模运算保留低位的n位，而扩容后保留n+1位，

因为hash1在扩容后+N，说明hash1的第n+1位是1，而hash2扩容后不移动，说明hash2的第n+1位是0，

扩容前hash2的索引正好比hash1大N, 就需要hash2的索引的低n-1位和hash1的索引的低n-1位相同。并且hash2的索引的第n位是1，hash1的索引的第n位是0

那么我们会得到

            n+1   n    相同的低位

    hash1:  1     0    XXX

    hash2:  0     1    XXX

因为hash1和hash2的低n+1位不完全一致，所以扩容后取n位hash1和hash2不可能落到一个索引上，假设不成立。