HashMap扩容是怎样扩容的，为什么都是2的N次幂的大小？

#### 触发扩容 在没有指定初始长度的情况下，HashMap数组的默认长度为16，在添加一个新的键值对时，会调用putVal()方法，在方法中，成功添加一个新的键值对以后，会判断当前的元素个数是否超过阀值(数组长度*负载因子0.75)，如果超过那么调用resize方法进行扩容。具体的扩容步骤如下： 计算扩容后的长度 如果当前table为null 那么直接初始化一个数组长度为16的数组返回。 如果当前table的length已经大于HashMap指定的最大值2的30次方 那么直接返回旧table，不进行扩容。 其他情况 将table的length扩容为2倍，然后计算新的扩容阀值（新数组长度*0.75）。 初始化新数组 会根据扩容后的数组长度初始化话一个新的数组，并且直接赋值给当前hashMap的成员变量table。 ```java Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; ``` 这一步就很有意思，也是HashMap是非线程安全的表现之一，因为此时newTab还是一个空数组，如果有其他线程访问HashMap，根据key去newTab中找键值对，会返回null。实际上可能key是有对应的键值对的，只不过键值对都保存在旧table中，还没有迁移过来。 （与之相反，HashTable在解决扩容时其他线程访问的问题，是通过对大部分方法使用sychronized关键字修饰，也就是某个线程在执行扩容方法时，会对HashTable对象加锁，其他线程无法访问HashTable。ConcurrentHashMap在解决扩容时其他线程访问的问题，是通过设置ForwardingNode标识节点来解决的，扩容时，某个线程对数组中某个下标下所有Hash冲突的元素进行迁移时，那么会将数组下标的数组元素设置为一个标识节点ForwardingNode，之后其他线程在访问时，如果发现key的hash值映射的数组下标对应是一个标识节点ForwardingNode（ForwardingNode继承于普通Node，区别字啊呀这个节点的hash值会设置为-1，并且会多一个指向扩容过程中新tab的指针nextTable），那么会根据ForwardingNode中的nextTable变量，去新的tab中查找元素。（如果是添加新的键值对时发现是ForwardingNode，当前线程会进行辅助扩容或阻塞等待，扩容完成后去新数组中更新或插入元素） #### 迁移元素 因为HashMap的数组长度总是2的N次幂，扩容后也是变为原来的2倍，所以有一个数学公式，当length为2的N次幂时， ```java hash%length=hash&(length-1) ``` 而因为length是2的N次幂，length-1在二进制中其实是N个1。例如： length为16，length用2进制表示是10000， length-1是15，用2进制表示是1111， 2*length为32，length用2进制表示是100000， 2*length-1为31，length用2进制表示是11111， 所以hash&(length-1)的计算结果与hash&(2*length-1)的计算结果差别在于扩容后需要多看一位，也就是看第N位的1与hash值的&结果。 假设原数组长度为16，length-1二进制表示为1111。key1的hash值为9，二进制表示为01001，key2的hash值为25，11001， 所以hash&(length-1)的结果只要看低4位的结果，9和25的低4位都是1001，所以计算结果一致，计算结果都是9，所以在数组中处于数组下标为9的元素链表中。 扩容后数组长度为32，length-1二进制表示为11111，key1的hash值为9，二进制表示为01001，key2的hash值为25，11001， 所以hash&(2*length-1)的结果需要看低5位的结果，9和25的低4位都是1001，所以计算结果不一致，计算结果都是9和25，因为key2的hash值的第五位为1，key1的hash值的第五位为0，所以会多16，也就是原数组长度的大小。 所以原数组同一下标index下的链表存储的hash冲突的元素，扩容后在新数组中的下标newIndex要么为index，要么为index+length（去决定于hash值的第N位为1，还是0，也就是hash&length的结果，原数组长度length为2的N-1次幂） 所以会遍历链表(或者红黑树)，然后对数组下标index下每个节点计算hash&length的结果，然后存放在两个不同的临时链表中，遍历完成后，hash&length结果为0的元素组成的临时链表会存储在新数组index位置，hash&length结果为1的元素组成的临时链表会存储在新数组index+length位置。