简述HashMap的扩容机制（JDK7 和JDK8 对比）

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

名词简述：

capacity 容量，默认16
loadFactor 负载因子，默认0.75
threshold 阈值阈值=容量*负载因子，默认12，空参构造hashMap时。当map中的元素个数大于阈值时会触发扩容

什么情况下会扩容（JDK7和JDK8的情况不同）

一般情况下，在元素个数大于阈值时会发生扩容，每次扩容的容量都是之前容量的两倍。
HashMap的容量是有上线的，容量最大为1>>30，自行百度计算大小。超过了这个值则不会再增长，并且阈值会设置成，即永远都不会超过阈值

对比JDK7 和JKD8 的扩容机制

JDK7的扩容机制相对简单，有以下特性：

空参构造函数：以默认容量、默认负载因子、默认阈值初始化数组，内部数组是空数组
有参构造函数：根据参数确定容量、负载因子、阈值等
第一次put时才会初始化数组，其容量变为不小于指定容量的2的幂数。然后根据负载因子确定阈值
如果不是第一次扩容，则新容量=旧容量x2 新阈值 = 新容量x负载因子

注意：
jdk7扩容的条件：只有在数组容量大于阈值时 并且 发生了哈希冲突时，才会进行扩容

则会出现下属情况：

假设默认长度为16的hashMap，阈值为12，负载因子为0.75。此时加入第12个或者第13个元素的时候没有发生哈希冲突，则不会发生扩容。在不发生哈希冲突的情况下，默认初始化的hashMap最多可以存16个元素。
同默认初始化的HashMap，可能存放最多26（11+15）个元素。前11个元素全部发生哈希冲突存放在同一个位置，此时元素个数为11，不超过12，不会发生扩容，后续15个元素全部存放在其他位置，此时因为新加入的元素没有发生哈希冲突，所以不会发生扩容。当加入第27个元素时，必定会发生哈希冲突，并且元素个数大于阈值发生扩容

JDK8的扩容机制 (做了许多调整)

JDK8中的hashMap扩容只需要满足一个条件：当存放的新值（注意不是替换已有元素的位置时）的时候已有的元素个数大于阈值（已有元素等于阈值，下一个存放必然触发扩容机制）

注：
（1）扩容一定是放入新值的时候，该新值不是替换以前的位置的情况下。
（2）扩容发生在存放元素之后，当数据存放之后（先存放，后扩容），判断当前存入对象的个数，如果大于阈值则进行扩容

HashMap的容量变化通常存在以下几种情况：

空参构造函数：实例化的HashMap默认内部数组时null，即没有实例化。第一次调用put方法时，才会开始第一次初始化扩容，长度为16
有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数赋值给**阈值。 **第一次调用put方法时，会将阈值复制给容量，然后让阈值 = 容量x负载因子。（因此并不是我们手动指定了容量就一定不会出发扩容，超过阈值后一样会扩容！！）
如果不是第一次扩容，则容量变为原来的两倍，阈值也变为原来的两倍

注意：

首次put时，会先触发扩容（算是初始化），然后存入数据，然后判断是否需要扩容
不是首次put，则不会再初始化，直接存入数据，然后判断是否需要扩容

背景知识

Java7中HashMap底层采用的时Entry对数组，而每个Entry对又向下延伸时一个链表，在链表的每一个Entry对上不仅存放着自己的K/V值，还存放了前一个和后一个Entry对的地址
Java8中的HashMap底层结构有一定的变化，还是使用的数组，但是数组的对象啊以前时Entry对，现在换成了Node对象（可以理解是Entry对，结构一样，存储时也会存K/V键值对，前一个和后一个的Node的地址），以前的所有Entry向下延伸都是链表，Java8变成了链表和红黑树的组合，数据少量存入的时候优先还是链表，当链表长度大于8，且总数据量大于64时，链表会转化为红黑树，所以Java8的数据存储是链表+红黑树的组合。如果数据量小于64则只有链表，如果数据量大于64，且某一个数组下标数据量大于8，那么该处即为红黑树。

思考：