聊到 Java 里的集合框架，HashMap 的出镜率实在太高了，面试八股背了一套又一套。但真到了需要有序键值对的场景，TreeMap 才是那个真正干活的工具。前几天我帮同事排查一个排行榜功能，他每次插入完都要对整个 List 做一次Collections.sort，数据量一大就肉眼可见地卡。我让他换成 TreeMap，插入天然有序，遍历顺序就是排行榜顺序。他补了一句：那底层到底怎么保证有序的？红黑树究竟做了什么？于是就有了这篇 TreeMap 源码级拆解。
这篇文章适合两类人看：一类是准备面试、需要把“红黑树”讲清楚的求职者；另一类是每天都在写业务代码，但想真正搞懂集合原理、提升代码质量和排查问题能力的开发者。我会从红黑树的核心机制讲起，完整拆解 JDK 8 中 TreeMap 的插入、查找、删除、遍历四条主链路，最后再讲讲我实际使用时踩过的坑。整个过程不追求把每个方法逐行背出来，而是要让你读完能自己去看源码、能画出树的变化过程。
1. 为什么单独把 TreeMap 拎出来讲一遍
1.1 我先聊聊自己真正用上 TreeMap 的场景
很多人对 TreeMap 的印象停留在“有序 Map”，但面对 HashMap 和 LinkedHashMap 的时候，又会犹豫到底该用哪个。我最早真正意识到 TreeMap 价值，是在做一个区间查询的需求。
当时有个用户积分体系，积分数值在 0 到 10000 之间，需要根据积分区间映射到不同等级。最直观的写法是一串 if-else 判断，但区间段位多了之后，代码又丑又慢。后来我改用 TreeMap：
TreeMap<Integer, String> levelMap = new TreeMap<>(); levelMap.put(0, "青铜"); levelMap.put(1000, "白银"); levelMap.put(3000, "黄金"); levelMap.put(6000, "铂金"); levelMap.put(9000, "钻石"); // 用户积分 4500 落在什么段位？ String level = levelMap.floorEntry(4500).getValue();写完后我自己都愣了一下，一个floorEntry就把二分查找给做了，复杂度 O(log n)。这其实是 TreeMap 里getFloorEntry这类导航方法的能力，不只是“有序遍历”这么简单。
后来我又在需要自动排序的定时任务调度场景里用了 TreeMap 按时间戳存任务，每次取最早的任务就是firstKey()。这类需求用 HashMap 根本做不了，用外部排序又要维护额外的排序状态，TreeMap 就是最顺手的答案。
1.2 TreeMap 与 HashMap、LinkedHashMap 的核心差异
要真正理解 TreeMap 的定位，最适合的方式是先做一张对比表。我用 Java 8 版本的 JDK 作为参考依据，这也是目前大多数生产环境还在用的版本。
| 维度 | TreeMap | HashMap | LinkedHashMap |
|---|---|---|---|
| 底层结构 | 红黑树 | 数组 + 链表/红黑树 | 数组 + 链表/红黑树 + 双向链表 |
| 是否有序 | 按键的自然顺序或比较器排序 | 无序 | 按插入顺序或访问顺序 |
| 核心操作复杂度 | O(log n) | O(1) 平均 | O(1) 平均 |
| 是否允许 null key | 不允许 | 允许（hash 为 0 的桶） | 允许 |
| 是否允许 null value | 允许 | 允许 | 允许 |
| 典型场景 | 区间查询、排行榜、有序遍历、自动排序 | 快速存取 | 缓存淘汰（LRU）、需要保持插入顺序 |
这张表有一个值得展开的点：为什么 TreeMap 不允许 null key，却允许 null value？
原因在于 TreeMap 的排序机制。无论走自然排序还是自定义 Comparator，插入时都要拿 key 去和其他 key 做比较，而null无法参与任何比较运算。即使你写了一个允许 null 的 Comparator，需要非常小心地处理各种比较边界，源码作者为了不把复杂度抛给调用方，直接在入口处限制死了。我后面在“踩坑”部分会具体解释这个约束。
1.3 从选型角度回答“什么时候该用 TreeMap”
如果你正在纠结要不要用 TreeMap，我建议按下面这个思路来判断：
- 如果你需要按键有序遍历，且这个顺序需要动态维护，首选 TreeMap；
- 如果你只需要插入顺序，LinkedHashMap 更轻量；
- 如果你有区间查询（如“找大于某个 key 的最小键”），TreeMap 的
ceilingEntry、floorEntry、subMap几乎是量身定制； - 如果你的数据量很小（比如几十条），排序成本可以忽略，用不用 TreeMap 都行；
- 如果你的场景是并发写多读多，别忘了 TreeMap 不是线程安全的，这时候要么加锁，要么换
ConcurrentSkipListMap——跳表在并发环境下往往表现更好，这一点我会在第 5 部分详细说。
简单说，TreeMap 的价值不是“比 HashMap 快”，而是在排序这个维度上，它把复杂度从“每次排序 O(n log n)”降到了“维护有序 O(log n)”，同时还能做范围导航。
2. 红黑树核心机制：五个性质如何约束 TreeMap 的行为
2.1 红黑树五性质，先背下来再理解
TreeMap 的底层是红黑树，这是一棵自平衡的二叉搜索树。二叉搜索树本身在极端情况下会退化成链表，插入顺序恰好是递增序列时，查找复杂度会从 O(log n) 退化到 O(n)。红黑树通过“染色 + 旋转”两条手段，保证树始终是近似平衡的。
红黑树有五个性质，我先把标准定义写出来：
- 每个节点要么是红色，要么是黑色；
- 根节点是黑色；
- 每个叶子节点（NIL 节点）是黑色；
- 不能有两个连续的红色节点（即红色节点的父节点和子节点必须都是黑色）；
- 从任一节点到其每个叶子节点的所有路径，都包含相同数目的黑色节点。
第 5 条有人叫“黑高相等”，这是整棵树平衡性的根基。红黑树不是严格意义上的平衡树（不像 AVL 要求左右子树高度差不超过 1），它只要求黑色高度一致，红色节点可以打破高度差，但受到了“不能连续红”的约束，所以整体高度上限被压住了。
2.2 “最长路径不超过最短路径两倍”的推导
红黑树有一条经典结论：最长路径不会超过最短路径的两倍。很多文章直接写出了这条结论，但没解释为什么。这里我用大白话推一遍。
因为性质 5，从根到任意叶子，黑色节点数相同，假设这个黑色节点数为 h。那么：
- 最短路径，就是全部由黑色节点组成的路径，长度就是 h；
- 最长路径，由于不能出现连续红色节点，红色节点只能穿插在黑色节点之间，所以一条路径上红色节点的最大数量也就是 h 个（在每个黑节点之间最多插一个红）。
因此最长路径最多是“交替红黑红黑”的状态，长度不超过 2h，也就是最短路径的两倍。两倍的高度差意味着查找路径长度还是 O(log n) 的量级，这就是红黑树在“不追求绝对平衡”的前提下，仍然能保证性能的核心原因。
相比 AVL 树的绝对平衡，红黑树的旋转次数明显更少，因为在插入和删除时，红黑树允许一定程度的“不平衡”，只在违反五条性质时才做修复。天然适合写入频繁的业务场景。
2.3 TreeMap 源码里红黑树的定义方式
打开 JDK 8 的 TreeMap 源码，前面有一大段注释，明确写了“This is a red-black tree implementation”。核心字段就这几个：
private final Comparator<? super K> comparator; private transient Entry<K,V> root; private transient int size = 0; private transient int modCount = 0;modCount这个字段很关键，它是所有 Java 集合的“并发修改计数器”。后面讲迭代器的时候会专门展开。comparator为 null 时，TreeMap 走自然排序，也就是要求 key 实现Comparable接口。
真正的树节点是内部静态类Entry：
static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK; Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } }注意这里颜色用的是boolean类型，初始默认是黑色。为什么不直接用枚举？因为枚举对象在 HotSpot 里是一个完整的 Java 对象，内存开销远大于一个 boolean 字段。TreeMap 节点数量大时，这个差异会被放大。源码里所有对颜色的操作都抽到了colorOf、setColor这样的方法里，比如：
private static <K,V> boolean colorOf(Entry<K,V> p) { return (p == null ? BLACK : p.color); }设置成 static 方法处理 null 节点，是因为红黑树里的所有叶子节点在逻辑上都是“黑色 NIL 节点”，代码里用 null 代替 NIL，因此colorOf(null)必须返回黑色。
2.4 为什么不选 AVL 树或跳跃表
既然红黑树既不是绝对平衡，实现又复杂，为什么不直接选 AVL 树，或者干脆像 ConcurrentSkipListMap 一样用跳表？这是我读源码时自己问过的问题。
先说 AVL 树。AVL 要求任意节点的左右子树高度差不超过 1，所以查找效率确实比红黑树更稳定。但它为了维护这种严格平衡，每次插入和删除都可能引发多轮旋转。对 TreeMap 这种 Map 实现来说，写操作（put/remove）和读操作（get）都很多，红黑树在“写多时减少旋转、读多时略多几次比较”之间拿捏得更均衡。
再说跳表。跳表实现简单、并发友好（ConcurrentSkipListMap 就是例子），查找复杂度同样是 O(log n)。但它每个节点要维护多个层级的指针数组，平均每个节点额外占用约 1.33 个指针（按标准跳表的概率分布），而红黑树每个节点只有 left、right、parent 三个指针加一个 boolean，内存密度上红黑树更占优。还有更关键的一点：JDK 里 TreeMap 是从 Java 1.2 就存在的集合，红黑树算法成熟到不能再成熟，替换成跳表的迁移成本收益不划算。所以你看 ConcurrentSkipListMap 是后来加的，没有动 TreeMap 的底层，两条路线并行存在。
3. put() 全链路拆解：插入、父节点查找与旋转修复
3.1 完整插入流程分几步
我建议你直接在 IDE 里打开 TreeMap 源码，跟着下面的顺序看。put完整流程可以拆成三步：
- 如果 root 为 null，说明整棵树是空的，直接把新节点当根节点，方法结束；
- 从 root 开始做“二叉搜索树插入”，根据比较结果向左或者向右走，直到找到 null 位置，新节点挂在父节点的 left 或 right 上；
- 执行
fixAfterInsertion，对红黑树第五条性质和“不能连续红”的性质进行修复，最后强制把根节点染黑。
第一步有一个面试里常考的细节，根节点初始化时调用了compare(key, key)。为什么要拿 key 和自己比一次？注释写得很清楚：type (and possibly null) check。这是一次类型安全检查，如果 key 本身是 null，或者 key 没有实现 Comparable 且没有 Comparator，在这里就会直接暴露问题，而不是等到后续真正比较时才报错。
第二步中，JDK 对“有无 Comparator”做了两条并行路径：
Comparator<? super K> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); }注意看if (cpr != null)这个分支里没有显式的 null key 判断，而是通过cpr.compare(key, key)在根节点逻辑中完成检查。若自定义 Comparator 没对 null 做保护，同样会抛空指针。所以“TreeMap 不允许 null key”这个结论在两种模式下都成立，只是抛出异常的时机和手法有差异。
还有一个细节：当比较结果相等时，TreeMap 直接return t.setValue(value)，用新 value 覆盖旧 value，而不会新建节点。这也意味着 TreeMap 的 key 天然具有唯一性，和 HashMap 的语义一致，判定唯一性的标准是 Comparator/Comparable 的比较结果，而不是 equals 方法。这点很多人会踩坑：如果你自定义的比较器里只比较了 partId，那么 partId 相同但其他字段不同的两个对象会被视为同一个 key，后插入的会覆盖先前的 value。
找到插入位置后，核心逻辑如下：
Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++;注意modCount++在这里出现了，不管新增还是覆盖，只要有结构性修改，计数器就会增加。
3.2 fixAfterInsertion 的三种场景与源码逻辑
新插入的节点默认是红色。为什么不默认黑色？因为把它染红，性质 5（黑高相等）不会被破坏，你不需要处理整棵树的黑高问题。后续要处理的，就是性质 4（不能连续红）。
fixAfterInsertion的源码值得完整看一遍：
private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { Entry<K,V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == rightOf(parentOf(x))) { x = parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK; }我把核心逻辑简化成三种情况，理解这三种情况比背源码重要：
Case 1：叔叔节点是红色。此时父节点和叔叔节点都是红色，祖父节点必须是黑色（否则违反性质 4）。解决方案是把父节点和叔叔节点都染黑，祖父节点染红，然后把“当前节点”上移为祖父节点，继续循环。这一步的本质是把红色上抛，不碰任何旋转。
Case 2：叔叔节点是黑色，且当前节点是“内侧”插入。比如父节点在祖父左边，当前节点却插到了父节点的右边。这时候要先围绕父节点做一次旋转，让当前节点变成“外侧”节点，进入 Case 3。有人称这个是“先转进来，再转出去”。
Case 3：叔叔节点是黑色，且当前节点是“外侧”插入。此时方案很统一：把父节点染黑，祖父节点染红，然后围绕祖父节点做一次旋转。注意旋转完成后，祖父节点变成了原来父节点的位置，而父节点变黑，整条路径黑色节点数保持不变。
这里的核心思路是：能变色解决就不旋转，必须旋转时尽量从祖父节点旋。变色解决不了的时候，就是当前节点、父节点、祖父节点形成了“之”字形，需要先变成“直线型”，再做一次大旋转。
3.3 旋转操作源码，左旋右旋其实是一对镜像
旋转是红黑树最基础的动作。左旋和右旋互为镜像，我以左旋为例拆一下：
private void rotateLeft(Entry<K,V> p) { if (p != null) { Entry<K,V> r = p.right; p.right = r.left; if (r.left != null) r.left.parent = p; r.parent = p.parent; if (p.parent == null) root = r; else if (p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; } }整个过程其实做三件事：
- 把 p 的右孩子 r 提上来作为“新的子树根”；
- 把 r 原来的左孩子挂到 p 的右孩子位置；
- 处理 p 的父节点与 r 之间的父子关系。
右旋就是把 left 和 right 对调后的完全镜像操作。我在最开始学红黑树的时候，总觉得旋转很抽象，后来总结成一句口诀：旋转后，被提升的节点继承原父节点的父节点，原来的父节点变成被提升节点的子节点。你只要记住谁升谁降，指针关系就不会画错。
这里还有一个面试容易问到的点：为什么左旋右旋不会破坏“二叉搜索树顺序”？因为旋转发生在局部，选中的节点始终满足“左小右大”。右旋时，p 的右子树里所有节点都大于 p，而 r 左子树里的节点都介于 p 和 r 之间，挂到 p 的右边依然满足顺序。这就是旋转只调整“结构”不动“顺序”的数学基础。
4. 从 get()、remove() 到迭代器：TreeMap 的其他核心操作
4.1 getEntry：二分查找在树上的映射
TreeMap 的get方法底层是getEntry：
final Entry<K,V> getEntry(Object key) { if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; while (p != null) { int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } return null; }这就是在二叉搜索树上做二分查找，每次比较决定向左还是向右，走到 null 说明 key 不存在。流程不复杂，但有一个有意思的点：containsKey和get底层复用同一套逻辑。比如containsKey直接调用getEntry(key) != null，remove的第一步也是通过getEntry找目标节点。所以这几个操作的时间复杂度都是 O(log n)，而不是像 HashMap 那样平均 O(1)。
另外，TreeMap 还提供了一系列导航方法，它们也依赖这套查找逻辑，比如：
ceilingEntry(key)：返回大于等于 key 的最小节点；floorEntry(key)：返回小于等于 key 的最大节点；higherEntry(key)：严格大于 key 的最小节点；lowerEntry(key)：严格小于 key 的最大节点。
这些方法是 TreeMap 相比其他 Map 最大的差异化能力。实现逻辑是在二叉搜索树查找的基础上加入对“当前比较结果”的记录，找不到完全相等的 key 时，返回路径上最近的合适节点。比如getCeilingEntry，遍历过程记录最后一个“大于目标 key”的节点，一旦走到空就返回这个记录。玩法很朴素，但非常实用——我上文提区间段位时用的floorEntry就是这个。
4.2 deleteEntry 与 fixAfterDeletion：删除是红黑树里最绕的部分
删除比插入难，难点在于删掉一个黑色节点后，它所在路径的黑高少了一个，可能违反性质 5。
TreeMap 的deleteEntry分三种情况：
- 被删节点没有左孩子也没有右孩子，直接删除；
- 被删节点只有一个孩子，用这个孩子顶替它的位置；
- 被删节点有两个孩子，这时候不能直接删，要找它的后继节点（中序遍历的下一个节点），用后继节点的 key 和 value 覆盖当前节点，然后转而去删除后继节点。因为后继节点一定没有左孩子，可以递归套回情况 1 或 2。
这个“找后继”的动作封装在successor方法里，我后面讲迭代器时会再见到它。
deleteEntry的源码核心如下：
if (p.left != null && p.right != null) { Entry<K,V> s = successor(p); p.key = s.key; p.value = s.value; p = s; } Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) { replacement.parent = p.parent; ... if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { root = null; } else { if (p.color == BLACK) fixAfterDeletion(p); ... }注意replacement为 null 时（被删节点是叶子），如果 p 是黑色，需要先对 p 做fixAfterDeletion，再把 p 从树上断开。这里的顺序很关键：修复必须在删除之前做，因为删除后 p 就不在树上了，你无法再围绕它调整颜色和旋转。
fixAfterDeletion的完整源码比插入修复长很多，本质是处理“double black”问题。删掉一个黑色节点后，替代它的节点相当于多背负了一个黑色，这时有四种情况：
- 兄弟节点是红色；
- 兄弟节点是黑色，且兄弟的两个孩子都是黑色；
- 兄弟节点是黑色，且兄弟的左孩子是红色、右孩子是黑色；
- 兄弟节点是黑色，且兄弟的右孩子是红色。
每种情况对应一套“染色 + 旋转”的组合。我个人读这段源码时的一个经验是：不要直接硬啃所有分支，先在纸上画一个满足红黑树性质的例子，依次用这四种情况套一遍，每套一步就把树重新画出来。我大概花了两个小时才把整条链路的几何变换彻底搞明白，但搞明白之后再看源码，就是一个个“哦原来这里在对应那张图”的感觉。
4.3 迭代器与 successor()：从有序遍历看中序的意义
TreeMap 的迭代器输出的 key 一定是升序的（或按 Comparator 排序）。这个顺序是怎么做到的？因为迭代器底层走的是中序遍历。
红黑树是二叉搜索树，中序遍历恰好是先左子树、根节点、右子树，输出自然有序。TreeMap 迭代器的nextEntry方法里调用了一个核心函数，就是上一节提到的successor：
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) return null; else if (t.right != null) { Entry<K,V> p = t.right; while (p.left != null) p = p.left; return p; } else { Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } }successor的逻辑很清晰：
- 如果当前节点有右子树，下一个节点就是右子树里最左边的节点；
- 如果没有右子树，就一直向上找，直到找到“自己不在父节点右子树”的那一层，父节点就是后继。
这个函数既是迭代器的核心，也是删除操作中“找后继”的依赖。TreeMap 的firstEntry方法会从根一路走到最左节点，得到整棵树最小的 key；lastEntry则对应最右节点。这些在实现subMap、headMap、tailMap的区间遍历时也会被反复使用。
还有一点很多人忽略了：迭代器遍历 TreeMap 的时间复杂度不是 O(n)。因为每次从后继节点往上回溯时，最坏情况可能走 O(log n) 步，整棵树遍历完是 O(n log n) 吗？其实是 O(n)。这个结论来自中序遍历的时间复杂度——每个节点最多被访问常数次。只不过代码层面确实需要一些向上回溯的指针移动，比数组遍历的常数项更大。所以如果你只是要遍历一个有序 Map，TreeMap 是合理的；但如果数据量极大且遍历极频繁，也要评估一下是否值得。
4.4 modCount 与 fail-fast：TreeMap 的线程安全问题
TreeMap 不是线程安全的，这一点在类注释里没有明确写出，但源码里的modCount机制处处都在昭示这一点。
每次结构性修改（put 新增节点、remove 节点）都会执行modCount++，而迭代器构造时会保存当前的modCount快照：
private class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> { EntryIterator(Entry<K,V> first) { super(first); } } PrivateEntryIterator(Entry<K,V> first) { modCount = TreeMap.this.modCount; ... }每次next()前都会检查当前modCount是否和快照一致：
final Entry<K,V> nextEntry() { Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); ... }这个设计叫fail-fast——一旦检测到并发修改，立刻抛异常，而不是继续遍历产生不可预期的数据。注意这里针对的是“同一线程修改 + 遍历”或者“多线程同时修改”的情况。单线程下迭代过程中自己往里 put，也会触发这个异常，因为迭代器持有的快照没有更新。
如果确实需要线程安全的 TreeMap，有两个方向：
- 用
Collections.synchronizedSortedMap(new TreeMap<>())，包装后所有方法都是同步的； - 换
ConcurrentSkipListMap，它是线程安全的并发有序 Map，底层是基于跳表的 CAS 操作，读多写多场景下普遍比加锁的 TreeMap 性能好。
5. 源码阅读与实战中容易踩的坑
5.1 自定义 Comparator 的两个典型错误
TreeMap 允许通过构造函数传入自定义 Comparator，但很多人只记住了怎么传，没意识到 Comparator 的一致性直接影响 TreeMap 的正确性。
第一个典型错误是拿“会变化的字段”做比较。比如你按照对象的某个可变属性来排序，属性一变，树结构就乱了。TreeMap 不会感知到 key 内部的变化，它只在你 put、get、remove 时调用 Comparator，一旦树结构本身已经不符合“左小右大”的性质，查找结果就是错的。这是红黑树最隐蔽的坑，比线程安全更隐蔽。
第二个典型错误是 Comparator 实现没有保持自反性。JDK 文档里明确要求 Comparator 和 equals 保持一致，但很多人只重写了 Comparator，没重写 equals；或者写 Comparator 时，只判断了部分字段。前面在讲 put 时提到过，比较结果为 0 就意味着 key 相同，后插入的 value 会覆盖先前的 value。如果你只按 id 比较，但业务里同一个 id 有两条不同的数据，第二条就会莫名其妙把第一条覆盖掉。
我的建议是：自定义 key 时优先把它设计成不可变对象，同时保证 equals、hashCode、compareTo 三者结论一致。这个要求对 TreeMap 来说尤其重要，因为它把“相等”的全部判断都交给了比较器，根本不会去调用 equals。
5.2 null 值处理：key 不能为 null 的真正原因
很多人在面试时会背“TreeMap 不允许 null key，因为要排序”，但如果你只回答到这一步，追问一下就露馅了。
更深一层的原因是：Java 的基础类型里，null 没有自然顺序，如果有 Comparator，null 也不一定有顺序（取决于你 Comparator 的实现）。TreeMap 的设计哲学是“顺序必须确定”，所以它把 null key 直接拒之门外。在无 Comparator 模式下，源码明确写了if (key == null) throw new NullPointerException()；在有 Comparator 模式下，通过compare(key, key)做检查，如果比较器没有对 null 做容错，同样会抛异常。
而 null value 是允许的，因为 value 不参与任何比较和排序，存储一个 null value 不影响树的结构。所以你可以写treeMap.put(1, null)，但不能写treeMap.put(null, "x")。
5.3 subMap/headMap/tailMap 视图的区间陷阱
TreeMap 的视图方法特别实用，但要非常小心它们的边界语义。subMap(fromKey, toKey)是一个左闭右开区间，headMap(toKey)不包含 toKey，tailMap(fromKey)包含 fromKey。这些默认行为经常让新手写出边界差一的问题。
更隐蔽的是，视图不是快照，而是和原 TreeMap 共享数据的视图。通过 subMap 往里 put 数据，会直接写到原 Map；反过来，原 Map 里删掉的数据，视图也看不到了。如果你需要稳定快照，必须自己拷贝一份。
还有一个越界问题。向 subMap 视图里插入一个不在区间内的 key，会抛IllegalArgumentException。我自己的项目里就出现过一次：向headMap(endKey)子视图添加了一个大于等于 endKey 的 key，线上直接抛错。这类问题在测试环境很难发现，因为很多时候区间外数据量不大，不会走到边界。
另外要注意，如果你用没有实现 Comparable 的 key，或者自定义 Comparator 和自然排序混用，subMap 的区间判断也是依赖同一个 Comparator 的。所以视图方法的边界判断逻辑，本质上就是比较器逻辑的延伸。
5.4 调试 TreeMap 的小工具：把树打出来看
阅读和调试红黑树最大的障碍是你“看不见”这棵树。我之前调试一个自定义排序 bug 时，最笨但最有效的办法是写一个递归打印树结构的方法。下面这个工具方法我保留了挺久，分享给大家参考：
public static void printTree(AbstractMap.SimpleEntry<Integer, String> root, int depth) { // 简化版，实际可传入 TreeMap 的 root } public static void printNode(Object node, int depth) { if (node == null) { return; } Class<?> clazz = node.getClass(); try { Object left = clazz.getDeclaredField("left").get(node); Object right = clazz.getDeclaredField("right").get(node); Object key = clazz.getDeclaredField("key").get(node); Object parent = clazz.getDeclaredField("parent").get(node); boolean color = clazz.getDeclaredField("color").getBoolean(node); printNode(left, depth + 1); StringBuilder sb = new StringBuilder(); for (int i = 0; i < depth; i++) { sb.append(" "); } sb.append(key).append(color ? "(黑)" : "(红)"); if (parent != null) { sb.append(" parent=").append(clazz.getDeclaredField("key").get(parent)); } System.out.println(sb); printNode(right, depth + 1); } catch (Exception ignored) { } }调用方式是利用反射获取 TreeMap 的 root 字段，再传入上面这个方法。虽然颜色没法直观地显示，但结构关系一眼就能看清，尤其是搞明白旋转前后父节点和子节点的挂载关系时特别管用。
如果你不想写反射，更省事的方式是在 IDE 的 Debug 模式里，直接展开 root 节点的字段，一层层看 left/right/parent/color。IntelliJ IDEA 的 Debugger 可以自定义数据视图，把 TreeMap 的 root 渲染成树状结构，调试效率高很多。
6. 我对 TreeMap 源码阅读的一些体会
我在读 TreeMap 源码时遇到过不少挫折，其中大部分都发生在fixAfterDeletion上。后来总结出一个对自己特别有效的读法：先把二叉搜索树的操作（插入、删除、查找）跑通，再单独把红黑树的五条性质写在便签上，然后用小数据集（比如 1 到 10 的插入序列）手动模拟每一步颜色变化和旋转动作。纸上过完一遍之后，再回头看源码，逻辑是顺的。
还有一点想提醒大家，源码注释里经常提到参考了 CLRS（算法导论）的红黑树章节，所以如果哪段代码看不懂，先去翻书里的对应章节，再把书里的伪代码和 JDK 实现对照着看，往往比死抠源码更高效。TreeMap 的实现虽然整体上遵循经典算法，但在细节上做了很多工程化取舍，比如用 boolean 表示颜色、用 null 代替 NIL 节点、把根节点强制染黑等，这些都是 JDK 作者为节省内存和提高可读性做的改进。
最后说一个我现在的选型习惯：遇到排序需求先问自己三句话——数据量级多大？写入频率高还是查询频率高？是否需要范围导航？如果只需要在数据展示前排一次序，直接用 Stream 的 sorted 更简单；如果需要动态维护有序且查询多，TreeMap 很合适；如果并发环境下还要有序，优先考虑 ConcurrentSkipListMap。源码是拿来用的，不是拿来背的——TreeMap 这段源码最大的价值，是帮你建立对有序数据结构整个链路的直觉。
