哈希碰撞触发链表变长，当链表长度≥8且数组容量≥64时转为红黑树以优化查找效率；节点≤6时退化回链表，避免频繁切换。
哈希碰撞本身不是目标，而是触发 HashMap 内部结构演进的关键信号。真正需要关注的，是碰撞在什么条件下积累、如何被识别、以及为什么系统选择此时转向红黑树——这不是“退化”，而是有明确阈值和前提的主动优化。
哈希碰撞如何导致链表变长
当多个不同 key 经过扰动函数（h ^ (h >>> 16)）和取模运算（(n - 1) & hash）后落到同一个数组索引（即同一个桶），就会发生哈希碰撞。HashMap 用链表把这些节点串起来。如果这些 key 的 hashCode 分布极不均匀（比如自定义类未重写 hashCode 或重写不合理），或数据本身存在强规律（如连续整数 ID 作为 key 且容量非 2 的幂），碰撞会集中爆发，链表迅速变长。
- 每次 put 操作都会遍历链表比对 key.equals()，链表越长，查找/插入/删除平均耗时越高（O(n)）
- 但仅链表变长还不足以触发红黑树——必须同时满足两个硬性条件
触发红黑树转换的双条件机制
链表长度 ≥ 8 且数组容量 ≥ 64 才会树化。这两个条件缺一不可，设计逻辑清晰：
- 链表长度 ≥ 8：这是性能拐点。泊松分布分析表明，在理想哈希分布下，桶中节点数达到 8 的概率极低（约 0.00000006）。一旦出现，说明哈希质量差或数据异常，线性查找开销已不可忽视
- 数组容量 ≥ 64：避免小容量时“早熟树化”。容量为 16 或 32 时，冲突多因桶太少导致；此时扩容（翻倍）能自然打散链表，比引入红黑树更轻量、更高效
从链表到红黑树的实际转换过程
转换不是简单复制，而是一次结构重建：
- 原链表节点被逐个取出，按 key 的 hashCode 重新比较大小（而非链表顺序），构建左/右子树
- 插入过程中实时维护红黑树性质：节点着色、旋转平衡（左旋/右旋）、根节点上提
- 转换后，该桶的引用由 Node 指针变为 TreeNode 指针，后续操作自动走树逻辑
- TreeNode 同时保留 next 指针，兼容链表遍历，也支持树形查找（O(log n)）
红黑树何时会退化回链表
树不是一劳永逸的方案。当执行 remove 等操作导致树中节点数 ≤ 6 时，HashMap 会主动将红黑树还原为普通链表：
- 因为少量节点下，链表的内存开销更低、操作更直接，红黑树的维护成本反而成为负担
- 退化判断只看当前树的节点总数，不依赖数组容量或其他桶状态
- 这个“8→6”的不对称阈值（树化门槛高、退化门槛低）是为了防止频繁切换，提升稳定性
理解这个过程的关键，是把哈希碰撞看作探针，把链表长度和数组容量看作决策仪表盘。HashMap 不是在“应对问题”，而是在用可量化的指标，动态选择最适合当前数据特征的存储形态。
