hashmap用链表和红黑树协同解决哈希冲突，核心是“先链后树、按需升级”：链表以尾插法串起同桶key，查找时先比hash再调equals；当链表长度≥8且数组容量≥64时升级为treenode构成的红黑树，退化阈值为6，实现时间与空间的动态平衡。
Java HashMap 用链表和红黑树协同解决哈希冲突，核心是“先链后树、按需升级”，不是简单替换，而是根据实际负载动态调整结构。
链表怎么处理哈希冲突
当多个 key 经过哈希计算落到同一个桶（数组下标）时，HashMap 把它们串成一条单向链表：
- 每个节点是 Node
，含 hash、key、value、next 四个字段； - 新节点默认插入到链表尾部（JDK 1.8 改为尾插，避免多线程扩容死循环）；
- 查找时，先比 hash 值快速过滤，再逐个调用 key.equals() 确认是否匹配；
- 链表适合轻度冲突——长度短时查找快，内存开销小，实现简单。
什么时候转成红黑树
链表不是永远存在。当某个桶中冲突加剧，链表变长，查找退化为 O(n)，这时触发树化：
- 必须同时满足两个条件：链表长度 ≥ 8 且 数组总容量 ≥ 64；
- 不满足容量条件时（比如刚初始化或扩容前），优先扩容数组而非树化；
- 树化后，原 Node 节点被“升级”为 TreeNode（继承自 Node），复用原有数据，不重新创建对象；
- 红黑树支持 O(log n) 查找、插入、删除，显著改善高冲突场景性能。
树怎么退化回链表
红黑树不是一劳永逸，它只在冲突严重时启用，负载降低就降级：
- 当树中节点数 ≤ 6 时，自动退化为链表；
- 这个阈值（6）比树化阈值（8）低，形成“缓冲带”，避免频繁树化/退化震荡；
- 退化过程是把 TreeNode 按原顺序还原为普通 Node 链表，不涉及数据丢失或重哈希。
为什么这样设计
本质是空间与时间的权衡：
- 数组提供 O(1) 定位基础，但无法避免冲突；
- 链表轻量、低开销，适合日常多数桶（统计表明，泊松分布下长度≥8的概率极低）；
- 红黑树重型但稳定，只在少数热点桶启用，避免全局性能被个别坏数据拖垮；
- 所有操作都基于同一套节点抽象（Node/TreeNode 继承关系），结构切换平滑无感知。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
