HashMap

什么时候触发扩容？

一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。
HashMap的容量是有上限的，必须小于1<<30，即1073741824。如果容量超出了这个数，则不再增长，且阈值会被设置为Integer.MAX_VALUE（ ，即永远不会超出阈值了）。

JDK7中的扩容机制

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

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

  JDK8中的扩容机制

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

   Jdk1.7到Jdk1.8 HashMap 发⽣了什么变化(底层)?

4. 1.7中底层是数组+链表，1.8中底层是数组+链表+红⿊树，加红⿊树的⽬的是提⾼HashMap插⼊和 查询整体效率
   2. 1.7中链表插⼊使⽤的是头插法，1.8中链表插⼊使⽤的是尾插法，因为1.8中插⼊key和value时需要 判断链表元素个数，所以需要遍历链表统计链表元素个数，所以正好就直接使⽤尾插法
   3. 1.7中哈希算法⽐较复杂，存在各种右移与异或运算，1.8中进⾏了简化，因为复杂的哈希算法的⽬的 就是提⾼散列性，来提供HashMap的整体效率，⽽1.8中新增了红⿊树，所以可以适当的简化哈希 算法，节省CPU资源

HashMap的扩容机制原理

1.7版本：
1. 先⽣成新数组
2. 遍历⽼数组中的每个位置上的链表上的每个元素
3. 取每个元素的key，并基于新数组⻓度，计算出每个元素在新数组中的下标
4. 将元素添加到新数组中去
5. 所有元素转移完了之后，将新数组赋值给HashMap对象的table属性
1.8版本 ：
1. 先⽣成新数组
2. 遍历⽼数组中的每个位置上的链表或红⿊树
3. 如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去
4. 如果是红⿊树，则先遍历红⿊树，先计算出红⿊树中每个元素对应在新数组中的下标位置
a. 统计每个下标位置的元素个数
b. 如果该位置下的元素个数超过了8，则⽣成⼀个新的红⿊树，并将根节点的添加到新数组的对
应位置
c. 如果该位置下的元素个数没有超过8，那么则⽣成⼀个链表，并将链表的头节点添加到新数组
的对应位置
5. 所有元素转移完了之后，将新数组赋值给HashMap对象的table属性