基于HashMap1.8

一、HashMap 原理分析

HashMap 是一个用来存数据的容器，存储格式为 key-value 。

HashMap 的底层以 数组+链表+红黑树 的格式进行存储。

往HashMap 中存键值对的原理图如下
image.png

往 HashMap 存值大概步骤如下
image.png

1.8 和 1.7 的流程一致，唯一区别在于 1.8 多了红黑树的处理。

1.1、存储原理

HashMap 采用（数组 + 链表 + 红黑树）进行存储。（同时也是 Hash冲突的解决）
相关存储如下：

image.png

hash冲突解决：当 hsah冲突，优先使用链表解决，当链表长度 >8 && 容器长度大于64，使用红黑树解决。

1.2、构造函数

以无参构造函数为例

image.png
无参函数对加载因子进行默认值设置，其他所有的值也都是默认值，加载因子默认值0.75。

1.3、插入函数（put）

1.3.1、第一次插入

image.png
如上述代码，第一次执行插入操作，会进行如下关键处理

  • 初始化数组 Node[] ，默认长度 1 << 4 = 16 (位运算效率更高)
  • 初始化扩容阈值 threshold ，默认:16 * 0.75 = 12。

1.3.2、索引值计算

索引值的计算步骤

  • 1、根据 key 计算 hashCode
  • 2、( 容器长度 - 1 ) / 步骤一获取的 hashCode

image.png

1.3.3、扩容操作

扩容操作方法在两种情况下执行

  • 第一次 put操作，初始化 Node[] 和 threshold
  • 容器中 键值对数量 > threshold

本次针对 容器中键值对数量 > threshold 的情况进行说明
image.png
根据上述代码得出结论

  • 容器扩容为原来的2倍
  • 容器容量上限为 MAXIMUM_CAPACITY = 1 << 30 = 2 ^ 30

    1.4、获取值(get)

    image.png