HashMap的底层原理和扩容机制

桃扇骨 2024-03-17 23:20 123阅读 0赞

**一，HashMap的基本数据结构**

**HashMap继承了Map****抽象类，实现****了M****ap，****Cloneable****，Serializable接口。**

*  **1.7 数组 + 链表**
 *  **1.8 数组 + （链表 | 红黑树）**

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

**Node的基本属性**

*  **hash：key的哈希值**
 *  **key：节点的key，类型和定义HashMap时的key相同**
 *  **value：节点的value，类型和定义HashMap时的value相同**
 *  **next：该节点的下一节点**

#### **二， 为什么要进行树化？树化的规则？** ####

**树化意义**

**hash 表的查找，更新的时间复杂度是 O(1)，而红黑树的查找，更新的时间复杂度是 O(log\_2⁡n )，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的。**

**三，HashMap的索引是如何计算的？**

*  **首先，计算对象的 hashCode()，得到原始hash值**
 *  **再进行调用 HashMap 的 hash() 方法进行二次哈希，得到二次hash值**
 *  **最后 & (capacity – 1) 得到索引（使用二次hash值和数组容量 - 1进行位与运算）**

**四，数组容量为何是 2 的 n 次幂？**

*  **计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模**
 *  **扩容时重新计算索引效率更高：hash（原始hash） & oldCap（原始容量） == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap（原始容量）**

**五，为什么要进行二次 hash？**

*  **二次 hash() 是为了综合高位数据，让哈希分布更为均匀**
 *  **二次 hash 是为了配合 容量是 2 的 n 次幂 这一设计前提，如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash**
 *  **容量是 2 的 n 次幂 这一设计计算索引效率更好，但 hash 的散列性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable**

**六，HashMap的Put流程**

1.  **HashMap 是懒惰创建数组的，首次使用才创建数组**
2.  **计算索引（桶下标）**
3.  **如果桶（bucket）下标还没人占用，创建 Node 占位返回**
4.  **如果桶下标已经有人占用**
    
    **a、已经是 TreeNode 走红黑树的添加或更新逻辑**
    
    **b、是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑**
5.  **返回前检查容量是否超过阈值，一旦超过进行扩容**

**七，HashMap如何进行扩容。**

**什么时候触发扩容？**

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

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

![e610573e76d230708709fd7621dde01c.png][]

**即永远不会超出阈值了）。**

**这要分HashMap1.7和HashMap1.8情况**

**HashMap1.7**

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

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

**HashMap 1.8**

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

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

**此外还有几个细节需要注意：**

*  **首次put时，先会触发扩容（算是初始化），然后存入数据，然后判断是否需要扩容；**
 *  **不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容；**
 *  **1.7 是大于阈值（threshold = factor \* capacity ）且没有空位时才扩容，而 1.8 是大于阈值就扩容**
 *  **1.7是先扩容再插入数据，1.8是先插入数据再扩容**
 *  **扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容**
 *  **HashMap的容量达到2的30次方，就不会再进行扩容了**

![d630eba78980a8e7d80028d99abd3fe5.jpeg][]

**八，扩容因子（factor）为何默认是 0.75？**

**在空间占用与查询时间之间取得较好的权衡**

*  **大于0.75，空间节省了，但链表就会比较长影响性能**
 *  **小于0.75，冲突减少了，但扩容就会更频繁，空间占用也更多**

**九，HashMap的key**

1.  **HashMap 的 key 可以为 null，但 Map 的其他实现则不然**
2.  **作为 key 的对象，必须实现 hashCode 和 equals，并且 key 的内容不能修改（不可变）**
3.  **key 的 hashCode 应该有良好的散列性**

#### **十，总结HashMap1.7和1.8有什么不同？** ####

**1. 数据结构**

*  **1.7 数组 + 链表**
 *  **1.8 数组 + （链表 | 红黑树）**

**2. 初始化方式**

*  **1.7中resize()方法负责扩容，inflateTable()负责创建表**
 *  **1.8中resize()方法在表为空时，创建表；在表不为空时，扩容；**

**3. 扩容方式**

**扩容时机**

**1.7在插入数据之前扩容，而1.8插入数据成功之后扩容**

**1.7 是大于阈值（threshold = factor \* capacity ）且没有空位时才扩容，而 1.8 是大于阈值就扩容**

**插入方式**

**1.7 是头插法，1.8是尾插法，因此1.7可能会出现并发死链现象，两者在并发情况下都会出现数据错乱**

**索引计算**

**1.8在扩容时计算索引做了优化**

[e610573e76d230708709fd7621dde01c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cdf281bbe8f5429ba044196e163bd4e4.png
[d630eba78980a8e7d80028d99abd3fe5.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/3742623078224db297f88af14753a592.png