hello，大家好。今天跟大家说说HashMap的底层原理以及它的扩容机制。

1、HashMap的底层实现原理

1.1HashMap的基本数据结构

HashMap继承了AbstractMap抽象类，实现了Map、Cloneable、Serializable接口。

JDK1.7及以前，HashMap是由数组 + 链表构成的

JDK1.8 以后，HashMap是由数组 + (链表 | 红黑树)构成的

HashMap类中的元素是Node类，翻译过来就是节点，是定义在HashMap中的一个内部类。

Node的基本属性如下：

Hash--key的哈希值

Key--节点的key，类型和定义HashMap时的key相同

Value--节点的value，类型和定义HashMap时的value相同

Next--该节点的下一节点

HashMap使用拉链法管理其中的每个节点：定义了一个数组，这个数组记录了每个链表的第一个节点，可以通过不断的调用Node.next.next.next...，遍历整个链表。如果HashMap初始化的时候没有指定容量，那么初始化 table的时候会使用默认DEFAULT_INITIAL_ CAPACITY参数，也就是16，作为 table初始化时的长度。如果HashMap初始化的时候指定了容量，HashMap 会把这个容量修改为2的倍数，然后创建对应长度的table。

1.2为什么要进行树化？树化的规则？

树化意义：

hash表的查找，更新的时间复杂度是 O(1)，而红黑树的查找，更新的时间复杂度是 O(log2n)，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表。

但是红黑树用来避免 DoS 攻击，防止链表超长时性能下降O(n)，树化应当是偶然情况，是保底策略。

树化规则：

HashMap里面定义了一个常量TREEIFY_THRESHOLD = 8，当链表长度超过树化阈值 8 时，先尝试调用resize()方法进行扩容来减少链表长度，如果数组容量已经 >=64(MIN_TREEIFY_CAPACITY)，才会进行树化，Node节点转为TreeNode节点(TreeNode也是HashMap中定义的内部类)。TreeNode除了Node的基本属性，还保存了父节点parent，左孩子left，右孩子right，还有红黑树用到的red属性。

Note：

hash值如果足够随机，则在 hash表内按泊松分布，在扩容因子(factor)0.75 的情况下，长度超过 8 的链表出现概率是千万分之6，树化阈值选择 8 就是为了让树化几率足够小。如果数组扩容还不到64，链表长度未减少，链表长度是有可能超过8的。

1.3HashMap的一些原理问题

HashMap的索引是如何计算的：

首先，计算对象的 hashCode()，得到原始hash值

再进行调用 HashMap 的 hash() 方法进行二次哈希，得到二次hash值

最后 & (capacity – 1) 得到索引(使用二次hash值和数组容量 - 1进行位与运算)

为什么要进行二次 hash：

二次 hash是为了综合高位数据，让哈希分布更为均匀

二次 hash是为了配合容量是2的n次幂这一设计前提，如果 hash 表的容量不是2的n次幂，则不必二次 hash

容量是2的n次幂这一设计，计算索引效率更好，但 hash 的散列性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable

数组容量为何是 2 的 n 次幂：

计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模

扩容时重新计算索引效率更高：hash(原始hash) & oldCap(原始容量)== 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap(原始容量)

 

1.4HashMap的Put流程

HashMap 是懒惰创建数组的，首次使用才创建数组

计算索引(桶下标)

如果桶(bucket)下标还没人占用，创建 Node 占位返回

如果桶下标已经有人占用

a、已经是 TreeNode 走红黑树的添加或更新逻辑

b、是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑

返回前检查容量是否超过阈值，一旦超过进行扩容

2、HashMap的扩容原理

2.1HashMap扩容的概念

hashMap扩容就是重新计算容量，向hashMap不停的添加元素，当hashMap无法装载新的元素，对象将需要扩大数组容量，以便装入更多的元素。

2.2什么时候触发扩容？

HashMap默认的负载因子(loadFactor)大小为0.75

HashMap的扩容阈值threshold = capacity* loadFactor 

一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。

HashMap的容量是有上限的，必须小于1<<30，即1073741824。如果容量超出了这个数，则不再增长，且阈值会被设置为Integer.MAX_VALUE(即永远不会超出阈值了)。

2.3HashMap扩容的实现

HashMap的扩展原理是HashMap用一个新的数组替换原来的数组。重新计算原数组的所有数据并插入这个新数组，然后指向新数组。如果阵列在容量扩展前已达到最大值，阈值将直接设置为最大整数返回。

在JDK1.7的扩容机制相对简单，有以下特质：

空参数的构造函数：以默认容量、默认负载因子、默认阈值初始化数组。内部数组是空数组。

有参构造函数：根据参数确定容量、负载因子、阈值等。

第一次put时会初始化数组，其容量变为不小于指定容量的2的幂数。然后根据负载因子确定阈值。

如果不是第一次扩容，则 新容量=旧容量*2 新阈值=新容量*负载因子

 

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

空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。

有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值(threshold)。第一次调用put方法时，会将阈值赋值给容量，然后让 阈值=容量X负载因子(因此并不是我们手动指定了容量就一定不会触发扩容，超过阈值后一样会扩容！！)

如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。