hashmap采用链地址法处理哈希冲突，链表长度≥8且数组长度≥64时树化为红黑树，≤6时退化回链表；通过hash扰动和2的幂次方容量优化分布，并在扩容时重新散列以缓解冲突。
HashMap 在发生哈希冲突时，底层采用链地址法（拉链法）为主、红黑树优化为辅的方式处理，核心目标是在保持 O(1) 平均时间复杂度的同时，避免极端情况下的性能退化。
链表存储冲突元素
当多个 key 经过哈希计算后落到同一个数组索引（即“桶”）时，HashMap 不会覆盖或丢弃，而是将新节点以尾插法追加到该桶位置的链表末尾（JDK 1.8 起）。每个节点包含 hash、key、value 和 next 指针，天然支持链式结构。
- 查找时，先定位桶位置，再遍历链表逐个比对 key 的 hash 值和 equals 结果
- 插入时若发现相同 key（hash 相同且 equals 为 true），则直接更新 value
- 链表长度较短时（如 ≤7），操作开销小，空间占用也低
链表转红黑树的触发条件
为防止链表过长导致最坏查找变为 O(n)，JDK 1.8 引入了红黑树降级机制：
- 链表长度 ≥ 8 且 数组长度 ≥ 64 时，该链表才会树化为红黑树
- 红黑树节点数 ≤ 6 时，会自动退化回链表
- 树化不是立即发生——它需要两次条件同时满足，避免小容量下频繁树化/退化
哈希扰动降低冲突概率
冲突无法完全避免，但 HashMap 主动减少其发生频率：
- 不直接使用 key.hashCode()，而是执行扰动函数：
h ^ (h >>> 16) - 让高 16 位参与索引计算，避免仅低位变化导致大量 key 映射到同一桶
- 配合数组长度为 2 的幂次方，用
(n - 1) & hash高效取模，使分布更均匀
扩容时的重新散列
当元素数量超过阈值（容量 × 负载因子，默认 0.75），HashMap 会扩容（通常翻倍），并重新计算所有元素的桶位置：
- 原数组中每个桶的链表或红黑树会被拆分到新数组的两个位置（旧索引 或 旧索引 + 原容量）
- 这个过程天然打散部分已有聚集，有助于缓解局部冲突
- 扩容是代价较高的操作，因此合理预设初始容量可减少触发次数
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
