HashMap 底层原理

HashMap 基于数组+链表/红黑树实现，通过哈希函数将键（Key）映射到数组索引，解决哈希冲突时用链表存储相同索引的元素，当链表长度超过阈值（默认8）且数组长度≥64时，链表会转为红黑树以提升查询效率。

核心概念

•	哈希表（数组）：存储数据的主体结构，每个元素称为“桶”（Bucket），存放链表或红黑树的头节点。

•	哈希函数：对 Key 的 hashCode 进行扰动计算（如异或、移位），得到哈希值，再通过 哈希值 & (数组长度-1) 确定数组索引（数组长度需为2的幂，保证计算结果在索引范围内）。

•	哈希冲突：不同 Key 经哈希计算得到相同索引，通过链表/红黑树串联这些元素。

•	负载因子：默认0.75，计算公式为“元素个数/数组长度”，用于判断是否需要扩容（超过阈值则数组扩容为原来的2倍）。

增删改查运行过程

1. 新增（put）

   1. 计算 Key 的哈希值，确定数组索引。

   2. 若索引位置为空，直接存入元素（Node 对象，包含 Key、Value、哈希值、下一个节点引用）。

   3. 若索引位置有元素，判断是否为同一 Key（哈希值相同且 equals 比较相等）：

   ◦ 是则覆盖 Value。

   ◦ 否则遍历链表/红黑树，若存在相同 Key 则覆盖，否则在尾部添加新节点。

   4. 添加后若链表长度≥8且数组长度≥64，将链表转为红黑树。

   5. 若元素总数超过“数组长度×负载因子”，数组扩容为2倍，重新计算所有元素的索引并迁移。

2. 删除（remove）

   1. 计算 Key 的哈希值，确定数组索引。

   2. 遍历该索引处的链表/红黑树，找到目标 Key 对应的节点。

   3. 若为链表节点，修改前后节点的引用，移除目标节点；若为红黑树节点，删除后调整树结构以维持平衡。

   4. 若删除后红黑树节点数≤6，将红黑树转回链表。

3. 修改（本质是 put 操作的覆盖）

   1. 执行 put 操作，计算目标 Key 的索引。

   2. 若找到相同 Key 的节点，直接用新 Value 覆盖旧值；若未找到，则新增节点。

4. 查询（get）

   1. 计算 Key 的哈希值，确定数组索引。

   2. 遍历该索引处的链表/红黑树：

   ◦ 链表：逐个比较节点的哈希值和 Key，找到则返回 Value，否则返回 null。

   ◦ 红黑树：通过树的搜索规则（如比较 Key 大小）快速定位节点，返回 Value 或 null。