HashMap底层原理

1.什么是HashMap？

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

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

2.HashMap的组成

其底层是由 数组 + 链表/红黑树 组成

当链表长度大于8 且数组长度 超过 64 将链表转换为红黑树结构

当链表长度大于8 但数组长度小于 64 则不会转成红黑树，数组继续扩容。

3. HashMap put方法流程

1.判断数组是否为空？ 空 ==> 执行resize()方法对数组进行初始化

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

3.若没发生hash冲突，直接将该节点存储对应的数组下标中

4.若发生hash冲突

​ 判断该key是否在map中存在

​ 4-1 存在 直接替换key对应的value值

​ 4-2 不存在 且冲突下标处以红黑树结构存储，直接存入树上

​ 4-3 不存在 且冲突下标处以链表结构存储

​ 判断链表长度是否大于 8

​ 小于8 直接存入链表

​ 大于8

​ 判断数组长度是否大于64 大于64 将链表转成红黑树再存入树中

​ 小于64 将数组扩容，重新根据key计算hash值进行存储

4.计算节点的存储下标

1.先判断key是否为null，为null直接返回0

2.若不为null 调用 hashCode()方法，得到hashCode

3.将得到的hashCode按位右移16位，再与原来的hashCode进行异或操作得到hash值

4.最后将hash值与数组.length-1 进行 & 操作，得到节点的存储下标 index = hash & (table.length - 1)

5. Hash冲突

通过hash()函数得到存放的下标，但该下标已被占用

解决hash冲突的四种方法

1. 开放地址法：以上次得到的hahs值再次进行运算得到新的hash值
2. 再哈希法：提供多个hash函数，如果发生冲突则换一个新的hash函数计算hash值
3. 链地址法：在冲突下标处链成一个链表存储
4. 建立公共溢出区：将hash表分为公共表和溢出表，凡是发生冲突的数据统一放在溢出区

6.HashMap的扩容机制

6-1 扩容属性：

capacity：数组长度 默认16

loadFactor：负载因子 默认0.75

threshold：扩容阈值 阈值 = 容量 * 扩容因子，默认是12

6-2 扩容条件

链表长度大于8 且数组长度小于64

HashMap中的元素个数大于阈值

6-3 扩容简要流程

创建一个更大容量的数组，一般为原来数组的两倍，将原数组的数据拷贝进去，扩容完成后，扩容阈值也变为原来的两倍