HashMap扩容机制

╰+哭是因爲堅強的太久メ 2023-10-14 14:11 36阅读 0赞

1.  介绍一下几个名词：  
    容量：capacity ，默认16。  
    加载因子：loadFactor，默认是0.75  
    阈值：threshold，默认12。threshold=capacity![\\times][times]tloadFactor；当元素个数超过阈值时，就会触发扩容。
2.  什么时候需要扩容：  
    HashMap数组中元素个数超过阈值，即触发扩容。  
    例如：默认情况下，容量16，加载因子0.75，阈值12，当HashMap中的元素个数超过12，会把数组大小扩大为2![\\times][times]容量=2![\\times][times]16=32，即容量变为原来的2倍，阈值=新容量![\\times][times]加载因子 = 32![\\times][times]0.75 = 24。然后重新计算出每个元素在数组中的位置。
3.  JDK7扩容  
    3.1 默认无参构造函数：以默认容量、默认负载因子、默认阈值，此时并未初始化数组。  
    3.2 有参构造函数，根据参数确定容量，负载因子和阈值，此时并未初始化数组。  
    3.3 第一次put时候，会初始化数组，判断当前容量是否为2的幂数，不是则将容量变为2的幂数，并根据负载因子确定阈值（第一次扩容，初始化数组）。  
    3.4 不是第一次扩容，则当数组元素超过阈值时候，新容量=旧容量![\\times][times]2，新阈值=新容量![\\times][times]负载因子。  
    3.5 扩容时，是创建一个新的数组，然后重新计算每个元素的hash值，找到元素在新数组中的对应位置，然后将链表以头插入的方式一一插入（每次扩容链表都会倒置）
4.  JDK8扩容  
    4.1 JDK8扩容有分两种情况，一种是元素个数超过阈值需要扩容，一种是当链表上的元素大于8，数组个数还没到达64，无法转化为红黑树，也会进行扩容。  
    4.2 默认构造函数：初始实例化的HashMap默认内部数组是null。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。  
    4.3 有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值。第一次调用put方法时，将阈值赋值给容量，然后让阈值 ＝容量![\\times][times]负载因子。  
    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 = 2

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

[times]: https://math.jianshu.com/math?formula=%5Ctimes