TreeMap源码级拆解：红黑树如何保证有序键值对

聊到 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 判断但区间段位多了之后代码又丑又慢。后来我改用 TreeMapTreeMapInteger, 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 作为参考依据这也是目前大多数生产环境还在用的版本。维度TreeMapHashMapLinkedHashMap底层结构红黑树数组 链表/红黑树数组 链表/红黑树 双向链表是否有序按键的自然顺序或比较器排序无序按插入顺序或访问顺序核心操作复杂度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 EntryK,V root; private transient int size 0; private transient int modCount 0;modCount这个字段很关键它是所有 Java 集合的“并发修改计数器”。后面讲迭代器的时候会专门展开。comparator为 null 时TreeMap 走自然排序也就是要求 key 实现Comparable接口。真正的树节点是内部静态类Entrystatic final class EntryK,V implements Map.EntryK,V { K key; V value; EntryK,V left; EntryK,V right; EntryK,V parent; boolean color BLACK; Entry(K key, V value, EntryK,V parent) { this.key key; this.value value; this.parent parent; } }注意这里颜色用的是boolean类型初始默认是黑色。为什么不直接用枚举因为枚举对象在 HotSpot 里是一个完整的 Java 对象内存开销远大于一个 boolean 字段。TreeMap 节点数量大时这个差异会被放大。源码里所有对颜色的操作都抽到了colorOf、setColor这样的方法里比如private static K,V boolean colorOf(EntryK,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。找到插入位置后核心逻辑如下EntryK,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(EntryK,V x) { x.color RED; while (x ! null x ! root x.parent.color RED) { if (parentOf(x) leftOf(parentOf(parentOf(x)))) { EntryK,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 { EntryK,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(EntryK,V p) { if (p ! null) { EntryK,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方法底层是getEntryfinal EntryK,V getEntry(Object key) { if (comparator ! null) return getEntryUsingComparator(key); if (key null) throw new NullPointerException(); Comparable? super K k (Comparable? super K) key; EntryK,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) ! nullremove的第一步也是通过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) { EntryK,V s successor(p); p.key s.key; p.value s.value; p s; } EntryK,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方法里调用了一个核心函数就是上一节提到的successorstatic K,V TreeMap.EntryK,V successor(EntryK,V t) { if (t null) return null; else if (t.right ! null) { EntryK,V p t.right; while (p.left ! null) p p.left; return p; } else { EntryK,V p t.parent; EntryK,V ch t; while (p ! null ch p.right) { ch p; p p.parent; } return p; } }successor的逻辑很清晰如果当前节点有右子树下一个节点就是右子树里最左边的节点如果没有右子树就一直向上找直到找到“自己不在父节点右子树”的那一层父节点就是后继。这个函数既是迭代器的核心也是删除操作中“找后继”的依赖。TreeMap 的firstEntry方法会从根一路走到最左节点得到整棵树最小的 keylastEntry则对应最右节点。这些在实现subMap、headMap、tailMap的区间遍历时也会被反复使用。还有一点很多人忽略了迭代器遍历 TreeMap 的时间复杂度不是 O(n)。因为每次从后继节点往上回溯时最坏情况可能走 O(log n) 步整棵树遍历完是 O(n log n) 吗其实是 O(n)。这个结论来自中序遍历的时间复杂度——每个节点最多被访问常数次。只不过代码层面确实需要一些向上回溯的指针移动比数组遍历的常数项更大。所以如果你只是要遍历一个有序 MapTreeMap 是合理的但如果数据量极大且遍历极频繁也要评估一下是否值得。4.4 modCount 与 fail-fastTreeMap 的线程安全问题TreeMap 不是线程安全的这一点在类注释里没有明确写出但源码里的modCount机制处处都在昭示这一点。每次结构性修改put 新增节点、remove 节点都会执行modCount而迭代器构造时会保存当前的modCount快照private class EntryIterator extends PrivateEntryIteratorMap.EntryK,V { EntryIterator(EntryK,V first) { super(first); } } PrivateEntryIterator(EntryK,V first) { modCount TreeMap.this.modCount; ... }每次next()前都会检查当前modCount是否和快照一致final EntryK,V nextEntry() { EntryK,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 没有自然顺序如果有 Comparatornull 也不一定有顺序取决于你 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)不包含 toKeytailMap(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.SimpleEntryInteger, 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 这段源码最大的价值是帮你建立对有序数据结构整个链路的直觉。