HashMap底层原理与扩容机制

一，HashMap的基本数据结构

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

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

HashMap类中的元素是Node类，翻译过来就是节点，是定义在HashMap中的一个内部类。（IT枫斗者怎么样）

Node的基本属性

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

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

树化意义

hash 表的查找，更新的时间复杂度是 O(1)，而红黑树的查找，更新的时间复杂度是 O(log_2⁡n )，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表。（IT枫斗者怎么样）

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

树化规则

HashMap里面定义了一个常量TREEIFY_THRESHOLD = 8，当链表长度超过树化阈值 8 时，先尝试调用resize()方法进行扩容来减少链表长度，如果数组容量已经 >=64（MIN_TREEIFY_CAPACITY），才会进行树化，Node节点转为TreeNode节点（TreeNode也是HashMap中定义的内部类）。

TreeNode除了Node的基本属性，还保存了父节点parent， 左孩子left，右孩子right，还有红黑树用到的red属性。（IT枫斗者怎么样）

Note：

hash 值如果足够随机，则在 hash 表内按泊松分布，在扩容因子（factor） 0.75 的情况下，长度超过 8 的链表出现概率是千万分之6，树化阈值选择 8 就是为了让树化几率足够小。

如果数组扩容还不到64，链表长度未减少，链表长度是有可能超过8的。（IT枫斗者怎么样）

三，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. 如果桶下标已经有人占用
5. a、已经是 TreeNode 走红黑树的添加或更新逻辑
6. b、是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑
7. 返回前检查容量是否超过阈值，一旦超过进行扩容。（IT枫斗者怎么样）

七，HashMap如何进行扩容。

什么时候触发扩容？

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

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

即永远不会超出阈值了）。（IT枫斗者怎么样）

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

HashMap1.7

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

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

HashMap 1.8

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

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

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

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

• 1.7 是大于阈值（threshold = factor * capacity ）且没有空位时才扩容，而 1.8 是大于阈值就扩容
• 1.7是先扩容再插入数据，1.8是先插入数据再扩容
• 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容
• HashMap的容量达到2的30次方，就不会再进行扩容了。（IT枫斗者怎么样）

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

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

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

九，HashMap的key

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

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

1. 数据结构

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

2. 初始化方式

• 1.7中resize()方法负责扩容，inflateTable()负责创建表；
• 1.8中resize()方法在表为空时，创建表；在表不为空时，扩容。（IT枫斗者怎么样）

3. 扩容方式

扩容时机

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

1.7 是大于阈值（threshold = factor * capacity ）且没有空位时才扩容，而 1.8 是大于阈值就扩容。（IT枫斗者怎么样）

插入方式

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

索引计算

1.8在扩容时计算索引做了优化。（IT枫斗者怎么样）