HashMap扩容机制

1. 介绍一下几个名词：
   容量：capacity ，默认16。
   加载因子：loadFactor，默认是0.75
   阈值：threshold，默认12。threshold=capacitytloadFactor；当元素个数超过阈值时，就会触发扩容。

2. 什么时候需要扩容：
   HashMap数组中元素个数超过阈值，即触发扩容。
   例如：默认情况下，容量16，加载因子0.75，阈值12，当HashMap中的元素个数超过12，会把数组大小扩大为2容量=216=32，即容量变为原来的2倍，阈值=新容量加载因子 = 320.75 = 24。然后重新计算出每个元素在数组中的位置。

3. JDK7扩容
   3.1 默认无参构造函数：以默认容量、默认负载因子、默认阈值，此时并未初始化数组。
   3.2 有参构造函数，根据参数确定容量，负载因子和阈值，此时并未初始化数组。
   3.3 第一次put时候，会初始化数组，判断当前容量是否为2的幂数，不是则将容量变为2的幂数，并根据负载因子确定阈值（第一次扩容，初始化数组）。
   3.4 不是第一次扩容，则当数组元素超过阈值时候，新容量=旧容量2，新阈值=新容量负载因子。
   3.5 扩容时，是创建一个新的数组，然后重新计算每个元素的hash值，找到元素在新数组中的对应位置，然后将链表以头插入的方式一一插入（每次扩容链表都会倒置）

4. JDK8扩容
   4.1 JDK8扩容有分两种情况，一种是元素个数超过阈值需要扩容，一种是当链表上的元素大于8，数组个数还没到达64，无法转化为红黑树，也会进行扩容。
   4.2 默认构造函数：初始实例化的HashMap默认内部数组是null。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。
   4.3 有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值。第一次调用put方法时，将阈值赋值给容量，然后让阈值 ＝容量负载因子。
   4.4 JDK8在迁移元素时是正序的，不会出现链表转置的发生
   4.5 JDK8扩容时，不需要重新计算每个元素新位置，只需要判断原来的hash值新增的那个bit是1还是0就可以了。
   例如：原长度是16，扩容后长度32，元素的hashCode为52，那么在扩容前后的下标是这样计算的：
   原table（长度16）：

(16-1) & 52 = 0000 0000 0000 0000 0000 0000 0000 1111 & 0000 0000 0000 0000 0000 0000 0011 0100 =  0000 0000 0000 0000 0000 0000 0000 0100 = 4

新table（长度32）：

(32-1) & 52 = 0000 0000 0000 0000 0000 0000 0001 1111 & 0000     0000 0000 0000 0000 0000 0011 0100 =  0000 0000 0000 0000   0000 0000 0001 0100 = 20

刚好是原数组的下标+原数组的长度。