HashMap底层原理

---

1. 基本概念

HashMap 是基于 Map 接口实现的一个存储键值对数据的集合

最多允许一个为 null 的 key 值，且 HashMap 存储的数据是无序的

2. HashMap 的底层数据结构

HashMap 底层是由 数组 + 链表 / 红黑树 组成，当链表过长，会影响 HashMap 的性能，链表就会转变成红黑树，数组是 HashMap 的主体，数组中存储链表或红黑树的头节点

链表转换成红黑树的前提条件：

• 当链表长度超过 8 并且数组长度超过 64 才会转换成红黑树
• 链表转变为红黑树之前会进行判断，如果数组长度小于 64，那么会继续对数组扩容，而不是转变成红黑树

3. HashMap 的 put 方法流程

简要流程如下：

1. 判断数组是否为空，是空就调用 resize 对数组初始化

2. 根据 key 值计算 hash 值，得到该节点对在数组中存储的下标

3. 如果没发生哈希冲突将该节点直接存入对应的数组下标处

4. 冲突后先判断当前 Map 中 key 值是否存在，如果存在直接替换当前 Map 中 key 对应的 value

5. 如果 key 值不存在且冲突节点处是红黑树，直接将该节点存入树上

6. 如果 key 值不存在且冲突节点处是链表：

   • 判断链表长度是否大于 8
   • 小于 8 直接存入链表，
   • 如果大于 8，就判断数组长度是否大于 64，大于 64 链表转换成红黑树，将该节点存入树上；小于 64 先对数组进行扩容，再重新计算 hash 值进行存储

4. 怎么计算节点存储的下标

先通过源码看一下 JDK 8 中是如何计算 hash 值的

1. 先判断 key 值是否为 null，为 null 直接返回 0
2. 如果不为 null，先调用 hashCode 方法得到 hashCode
3. 将得到的 hashCode 按位右移 16 位，再与原来的 hashCode 进行异或操作得到 hash 值

计算下标：

通过 HashMap 存储节点的源码可以看出，HashMap 将节点存储在 (table.length - 1) & hash 下标处

即节点下标是数组长度减一再按位与 hash 值得到的

5. Hash 冲突

1）概念

hash 冲突是指，通过 hash 函数得到的存放节点的地址已经被占用了

2）解决 hash 冲突的办法

解决 hash 冲突的方法有：开放定址法、再哈希法、链地址法、建立公共溢出法。HashMap 中采用的是 链地址法

开放地址法

如果出现了冲突，就以上次得到的 hash 值再次进行运算得到一个新的 hash 值，直到找到一个没有冲突的 hash 值

再哈希法

提供多个不同的 hash 函数，如果发生了冲突，就用其他 hash 函数计算 hash 值，直到一个没有冲突的 hash 值

链地址法

将 hash 值相同的元素构成一个单链表，并将单链表的头指针存入哈希表中。此方法就是 HashMap 的底层数据结构，数组加链表的形式

建立公共溢出区

将哈希表分为公共表和溢出表，凡是发生冲突的数据统一放在溢出区

6. HashMap 的扩容机制

1）扩容时涉及到的几个属性

1. capacity ：容量，默认 16
2. loadFactor：负载因子，默认是 0.75
3. threshold：阈值，阈值 = 容量 * 负载因子，默认是 12

2）扩容的条件

1. 链表长度大于 8，数组长度小于 64
2. HashMap 中的元素个数大于阈值

3）扩容的简要流程

创建一个容量更大的数组，一般为原来数组的两倍，将原来数组的元素拷贝到新的数组中，扩容完成之后，阈值也变为原来的两倍