HashMap底层是“数组+链表+红黑树”三级结构，红黑树仅在链表≥8且数组长度≥64时触发树化，本质是链表的升级替补；TreeNode兼具双向链表与红黑树特性，复用TreeMap旋转逻辑，未实现Comparable或Comparator将导致ClassCastException。
HashMap 底层不是单纯靠红黑树，而是“数组 + 链表 + 红黑树”三级结构，红黑树只在特定条件下启用。理解源码时，不能把红黑树当成 HashMap 的主干，而要把它看作链表的“升级替补”——只有当链表太长、影响查询效率时，才触发树化。真正贯穿始终的是哈希寻址、扩容逻辑和节点迁移策略，红黑树只是其中一环优化。
红黑树何时出现：树化的两个硬性条件缺一不可
链表转红黑树不是只要长度 ≥8 就发生。源码里 TREEIFY_THRESHOLD = 8 只是表面阈值，背后还有关键限制：
- 当前桶（bin）中链表节点数 ≥ 8
- 整个哈希表的数组长度
table.length ≥ MIN_TREEIFY_CAPACITY（即 ≥64）
如果数组才 16 或 32，即使某个桶里链表有 10 个节点，HashMap 也不会树化，而是优先触发扩容（resize()）。这是为了用更廉价的数组扩容来缓解冲突，避免过早引入红黑树带来的空间开销（TreeNode 比 Node 多约 50% 字段）。
TreeNode 不是独立红黑树，而是嵌套在哈希桶里的双向链表+树结构
源码中 TreeNode 继承自 Node，同时实现了红黑树节点和双向链表节点的双重身份：
立即学习“Java免费学习笔记（深入）”；
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
- 保留了
next和新增的prev，用于维持插入顺序（和链表兼容） - 新增了
parent、left、right、red字段，支撑红黑树操作 - 树化过程（
treeifyBin()）本质是遍历原链表，把每个Node包装成TreeNode，再按 key 的自然序或 Comparator 排序后构建成左倾红黑树
这意味着：同一个桶里的 TreeNode 既能在红黑树中按大小关系快速查找，也能在链表中按插入顺序遍历——这对 LinkedHashMap 的子类实现和迭代一致性很关键。
平衡旋转不是 HashMap 自己写的，而是复用 TreeMap 的核心逻辑
HashMap 中红黑树的插入修复（balanceInsertion()）、删除修复（balanceDeletion()）等方法，和 TreeMap 共享同一套旋转与变色逻辑。比如右旋操作：
- 把原节点
p的左子l提升为新根 -
l的右子变成p的左子 -
p成为l的右子 - 更新父引用和颜色标记，确保满足红黑树五条性质
这些旋转本身不依赖哈希值，只依赖 key 的比较结果（compareTo() 或 compare()）。所以如果你往 HashMap 里放没实现 Comparable 又没传 Comparator 的自定义对象，哪怕进了树，后续 get() 或 put() 也会抛 ClassCastException——这不是 bug，是设计使然。
源码阅读建议：从 putVal() 跟到 treeifyBin() 再跳进 balanceInsertion()
想结合红黑树理解 HashMap 源码，推荐按这个路径读 JDK8 的 HashMap.java：
- 先看
put(K,V)→ 进入putVal()，关注 hash 计算、桶定位、冲突判断 - 当发现是链表且
binCount >= TREEIFY_THRESHOLD - 1（即第 8 次冲突），调用treeifyBin() - 进入
treeifyBin()，注意它会先检查tab.length ，决定扩容还是树化 - 树化后首次插入调用
putTreeVal()，里面会调用balanceInsertion()——这里就是红黑树旋转的起点
重点观察 balanceInsertion() 中对祖父节点、叔叔节点颜色的判断分支，以及 rotateLeft()/rotateRight() 的指针重连逻辑。你会发现，它和《算法导论》里标准红黑树插入伪代码高度一致，只是 Java 实现得更紧凑。
