我平时在代码里处理“有序去重”这件事时最省事的一个工具就是TreeSet。很多同事一看到它就直接当成“有顺序的 HashSet”来用结果要么插入时报ClassCastException要么发现自定义对象明明重写了equals却还是丢数据。这些坑追根溯源全在它对“相等”的定义上而这套定义又是直接从底层TreeMap继承过来的。所以我一直觉得与其反复背用法不如直接打开 JDK 源码把TreeSet这层壳剥开看一眼以后再碰到排序、区间查询、最值获取之类的场景脑子里自然就有路线了。TreeSet的作用一句话就能说清它在内部维护一棵红黑树所有元素按照自然顺序或你指定的比较器排列读写操作的平均和最优复杂度都是O(log n)。相比HashSet它能直接拿到有序遍历结果相比手动Collections.sort它把排序成本摊到了每次插入里适合“边插入边有序”的场景。这篇文章适合两类读者一类是刚接触集合源码、想弄明白TreeSet背后机制的新手另一类是已经在项目里用过它、但遇到排序失败或去重异常后想找根因的开发者。我会从类结构、核心方法、排序规则、区间操作到踩坑实录一层层拆开讲。1. TreeSet 真实面纱它其实是 TreeMap 的一层壳1.1 类声明与底层结构打开 JDK 源码TreeSet的声明长这样public class TreeSetE extends AbstractSetE implements NavigableSetE, Cloneable, java.io.Serializable它继承了AbstractSet实现了NavigableSet。重点在这个NavigableSet它不是普通Set能比的里面定义了lower、floor、ceiling、higher、subSet、headSet、tailSet这些有序集合专属的区间方法。所以TreeSet能做的不仅是“去重 排序”还能做精准的“邻居查询”和“范围切片”这是其他 Set 实现给不了的。往下看成员变量发现玄机private transient NavigableMapE,Object m; private static final Object PRESENT new Object();TreeSet本身没有存储结构它把所有元素作为 key 存进了一个NavigableMap。NavigableMap是接口实际构造时传进来的实现几乎永远是TreeMap。value 固定是一个名叫PRESENT的共享占位对象和HashSet里保存PRESENT的思路一模一样。换句话说TreeSet就是披着 Set 外衣的TreeMap所有元素管理、排序、比较、平衡都交给红黑树完成。为什么要这样设计答案很简单复用。TreeMap已经实现了有序键值对的完整逻辑包括红黑树的插入、删除、查找、旋转、平衡还有子区间视图、降序视图等导航功能。TreeSet如果把这些逻辑再实现一遍不仅代码量爆炸维护成本也翻倍。JDK 里这种组合模式很常见典型的就是HashSet内部组合HashMapTreeSet内部组合TreeMap。理解了这层关系你再看TreeSet的任何方法都会觉得像在看TreeMap的门面。1.2 构造函数全解那六个构造器到底做了什么TreeSet的构造器公开的加上包私有的一共有六个初看很多拆开其实就三类public TreeSet() { this(new TreeMapE, Object()); } public TreeSet(Comparator? super E comparator) { this(new TreeMap(comparator)); } public TreeSet(Collection? extends E c) { this(); addAll(c); } public TreeSet(SortedSetE s) { this(s.comparator()); addAll(s); } TreeSet(NavigableMapE,Object m) { this.m m; }第一类是无参构造器直接 new 一个TreeMap元素使用自然顺序排序。第二类是传入Comparator的构造器同样交给底层TreeMap明确指定比较规则。第三类是接收已有Collection或SortedSet的构造器先建空树再批量addAll。真正有意思的是那个包私有的构造器TreeSet(NavigableMapE,Object m)。它不对外公开而是给TreeMap的视图方法用的。你调用subSet、headSet、tailSet、descendingSet时返回的TreeSet正是通过这个构造器创建的。它直接复用传进来的子图而不是复制一份数据。这样返回的集合实际上是对原集合某个区间的“动态视图”原集合增删元素子集视图也会跟着变化。这是很多人没用对subSet的根源所在。2. 常用方法源码级拆解增删改查背后发生了什么2.1 add 和 remove一次插入的完整路径先说add源码就两行public boolean add(E e) { return m.put(e, PRESENT) null; }它调用底层TreeMap.put(key, value)key 是你要插入的元素value 是固定的PRESENT。TreeMap.put返回的是该 key 之前关联的旧 value如果 key 原本不存在返回 nullTreeSet.add返回 true插入成功如果 key 已经存在返回旧 value也就是 PRESENTTreeSet.add返回 false插入失败并把新 value 覆盖上去。这里引出一个特别关键的点TreeMap判断 key 是否存在不是靠equals而是靠比较器或Comparable的compareTo结果是否为 0。所以TreeSet去重规则是“比较结果相等即视为同一个元素”哪怕两个对象的equals返回 false。反过来如果两个对象equals返回 true 但compareTo永远不返回 0TreeSet会认为它们是两个元素。这个细节不搞清楚自定义对象丢数据是迟早的事。TreeMap.put走的是标准的红黑树插入流程先按照比较器或自然顺序从根节点向下查找合适位置找到 key 相等的节点就直接替换 value找不到就在叶子节点挂上新节点然后返回来做颜色调整和旋转保证整棵树依然满足红黑树的五个约束条件。整个过程涉及 O(log n) 次比较如果比较器内部逻辑复杂比如多层字段判断性能开销会明显增加。remove方法同样简洁public boolean remove(Object o) { return m.remove(o) PRESENT; }逻辑和add对称TreeMap.remove返回被删除节点关联的旧 value如果 o 存在则返回 PRESENT不存在返回 null。这里注意remove的参数类型是Object不是泛型E因为TreeMap的删除操作同样基于比较结果定位节点不需要强制转换类型。2.2 contains 与大小判断二叉搜索还是遍历contains的内部实现是通过TreeMap.containsKey完成的public boolean contains(Object o) { return m.containsKey(o); }TreeMap.containsKey的定位路径和插入查找完全一致从根节点开始如果比较器不为 null 就调用比较器否则将 key 强转为Comparable一路比较下去。这是典型的二叉搜索路径复杂度 O(log n)。和HashSet的 O(1) 相比虽然常数更大但换来的是有序能力。如果你频繁用contains且数据量达到百万级TreeSet的劣势会放大这时候要权衡是否值得牺牲顺序性。size和isEmpty就更直接了public int size() { return m.size(); }红黑树的节点数量由TreeMap内部维护size()直接返回维护好的计数变量不需要遍历树。所以别担心size()有性能问题它和HashSet一样是常数时间。2.3 迭代器的升序保证与遍历性能TreeSet最实用的特性之一就是迭代器输出的元素一定是有序的。这个顺序来自红黑树的中序遍历。代码层面TreeSet的iterator()是这样的public IteratorE iterator() { return m.keySet().iterator(); }底层实际上是TreeMap的KeyIterator它维护一个栈按照“左根右”的顺序遍历。所以当你执行TreeSetInteger set new TreeSet(Arrays.asList(9, 3, 5, 1, 7)); set.forEach(System.out::println);输出一定是1 3 5 7 9。这个特性在需要生成排序报表、有序下拉列表、排行榜等场景里非常实用省去了每次取出来再Collections.sort的额外步骤。遍历的时间复杂度是 O(n)和树高无关因为中序遍历每个节点恰好访问一次。唯一要注意的是迭代过程中不要通过add或remove修改集合否则会触发快速失败机制抛出ConcurrentModificationException。3. 排序规则的两种实现Comparable 与 Comparator3.1 自然排序对象自己决定顺序如果创建TreeSet时不传入比较器底层TreeMap会使用元素的自然顺序。自然顺序要求元素实现java.lang.Comparable接口例如Integer、String、Long、BigDecimal这些常见类型都已经实现了。源码里TreeMap.put在查找插入位置时会执行这样的逻辑Comparator? super K cpr comparator; if (cpr ! null) { cmp cpr.compare(key, t.key); } else { Comparable? super K k (Comparable? super K) key; cmp k.compareTo(t.key); }注意这里有个强转如果没有比较器TreeMap会把 key 强转为Comparable。如果你往TreeSet里塞了一个没实现Comparable的类对象第一次add就在这个强转处抛ClassCastException。所以“自然排序”不是自动的它有前提元素类型必须实现Comparable且compareTo的返回值语义要和equals保持一致否则会出现TreeSet判定去重方式和我们预期不符的问题。自然排序的优点是简洁缺点也明显类本身的排序逻辑被固定死了。比如一个User类业务要求有时按 userId 排有时按年龄排有时按姓名拼音排。如果只靠Comparable你只能写死一种排序规则换个场景就得再建一个 TreeSet没法动态替换。这时候就要用自定义比较器。3.2 自定义比较器把一个无序类塞进有序集合Comparator是java.util包下的函数式接口核心方法就是int compare(T o1, T o2)。TreeSet在创建时通过构造器把Comparator传给底层TreeMap后续所有比较操作都走它。一点经验Comparator写的时候要尽量完整覆盖所有字段避免出现“全部字段都相等”却返回非 0 的情况否则TreeSet可能允许两个实际上完全一样的对象共存。更稳妥的做法是先按主字段排序主字段相同再按次字段排把所有字段都用上保证排序结果稳定且去重符合直觉。TreeSet构造器接受比较器的另一个好处是匿名类和 lambda 都行随手写TreeSetString set new TreeSet((a, b) - a.length() - b.length());这段代码按字符串长度排序。要注意的是这种比较器返回 0 时TreeSet把这个字符串视为重复导致相同长度的字符串只保留一个。这通常不是期望行为所以自定义比较器时要特别小心“只按单一属性排序”带来的误去重。3.3 决定去重的不是 equals是 compareTo这是整个TreeSet最容易踩坑的核心点。HashSet去重靠hashCode和equalsTreeSet去重靠的是compareTo或compare是否返回 0。我用一个例子说明。假设有个Student类class Student { String name; int score; Student(String name, int score) { this.name name; this.score score; } public boolean equals(Object obj) { // 按 name 判断相等 } public int hashCode() { return name.hashCode(); } }如果Student实现了ComparablecompareTo只按score比较那么两个名字不同但分数相同的Student会被TreeSet视为“重复”后插入的被丢弃。这会让很多开发者一头雾水明明equals返回 false为什么还是插不进去原因就藏在TreeMap.put的流程里当比较结果 cmp 0 时TreeMap认为 key 相等直接替换 value 并返回旧 value根本不会调用equals。因此TreeSet对“重复”的定义完全依赖比较器结果。解决办法是让compareTo的返回 0 条件和equals保持一致比如compareTo里把所有参与equals判断的字段都纳入比较范围。反过来如果你就是想按某个业务字段去重那也没问题但要明确这个规则是出自比较器而不是承袭equals语义。4. NavigableSet 接口比 Collection 多一半子集武器库4.1 查询方法 lower/floor/ceiling/higherNavigableSet提供了一组用于“找邻居”的查询方法这四个方法非常容易混淆我每次用都要在脑子里过一遍定义方法返回条件无满足元素时lower(e)严格小于 e 的最大元素nullfloor(e)小于等于 e 的最大元素nullceiling(e)大于等于 e 的最小元素nullhigher(e)严格大于 e 的最小元素null它们在源码里都是对TreeMap方法的直接转发比如public E lower(E e) { return m.lowerKey(e); }这种“找邻居”的能力在场景里非常有用。比如做题库系统输入当前分数想找下一个更高分数的人调higher一次搞定想找上一名分数在十分位附近的记录floor和lower是现成的。这些操作如果自己写循环遍历至少要 O(n)红黑树里一次查询就是 O(log n)。还有一对偷懒神器pollFirst()和pollLast()分别取出并删除最小和最大元素。它们内部调TreeMap.pollFirstEntry直接在树上做删除并返回 key。适合实现优先级队列或从有序集合中按顺序消费数据。4.2 子集视图 subSet/headSet/tailSet这三个方法是SortedSet时代就有的NavigableSet把它增强成带布尔参数的版本用来控制区间边界是否包含。public NavigableSetE subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new TreeSet(m.subMap(fromElement, fromInclusive, toElement, toInclusive)); }headSet和tailSet同理源码分别转到了TreeMap.navigableKeySet或subMap视图。注意返回的是new TreeSet(视图 map)上面提过的那个包私有构造器在这里派上了用场。它不是复制数据而是把视图 map 直接装进一个新的TreeSet外壳。所以原TreeSet和子集视图是“牵一发动全身”的关系原集合新增元素落到区间内子集视图遍历马上能看到。这个特性在做分页、按时间范围过滤、按分数段统计时很方便但也会让一些开发者在修改原集合后意外发现子集内容变了误以为出了 bug。边界参数也要多留个心眼。subSet要求fromElement toElement如果传反了会抛IllegalArgumentException。headSet(e, false)表示“严格小于 e”tailSet(e, true)表示“大于等于 e”。这些细节直接决定区间切片是否符合预期。4.3 逆序视图 descendingSet降序版本并不是把元素复制一套然后反过来存储而是返回一个映射关系反转的视图public NavigableSetE descendingSet() { return new TreeSet(m.descendingMap()); }TreeMap.descendingMap返回的是一个反向视图对外遍历顺序从大到小内部各操作通过逆序比较实现。这个视图同样和原集合共享数据原集合改一个元素降序视图立即可见。descendingSet的iterator()就是倒序迭代器很适合“排行榜倒序展示”这类需求。另外descendingSet还支持所有 NavigableSet 方法比如你可以在降序集合上继续调用subSet、headSet顺序语义也会相应反转。初用时会觉得别扭搞清方向后反而能写出更简洁的区间查询代码。5. 实操演示从创建到遍历的完整路径5.1 使用默认自然排序完成增删查与遍历我平时最常用的验证方式就是写一段最小的代码跑一遍确认脑子里的源码推导和实际行为一致。import java.util.TreeSet; public class TreeSetDemo { public static void main(String[] args) { TreeSetInteger numbers new TreeSet(); numbers.add(10); numbers.add(8); numbers.add(15); numbers.add(8); numbers.add(12); numbers.add(20); System.out.println(集合内容 numbers); System.out.println(第一个元素 numbers.first()); System.out.println(最后一个元素 numbers.last()); System.out.println(大于10的最小元素 numbers.higher(10)); System.out.println(小于等于15的最大元素 numbers.floor(15)); System.out.println(删除最大元素 numbers.pollLast()); System.out.println(删除后集合 numbers); } }这段代码的输出可以预料集合内容[8, 10, 12, 15, 20] 第一个元素8 最后一个元素20 大于10的最小元素12 小于等于15的最大元素15 删除最大元素20 删除后集合[8, 10, 12, 15]第二个 8 被去重了这验证了TreeSet的去重是基于自然顺序的相等判断。first()、last()底层是取树的最左最右叶子也是 O(log n)。5.2 用自定义比较器封装一个降序整数集合如果希望整数从大到小排序没必要自己写比较器Comparator.reverseOrder()一行搞定TreeSetInteger descNumbers new TreeSet(Comparator.reverseOrder()); descNumbers.addAll(Arrays.asList(5, 1, 4, 2, 3)); System.out.println(descNumbers);输出[5, 4, 3, 2, 1]注意这里去重规则依然是“比较结果相等即重复”所以不会因为 reverse 而出现重复元素共存。5.3 自定义对象按多个字段排序项目中真正的价值都在自定义对象上。假设一个简单的Customer类有level和name两个属性class Customer { int level; String name; Customer(int level, String name) { this.level level; this.name name; } public String toString() { return Customer{ level level , name name \ }; } }创建一个按等级升序、等级相同按姓名升序的比较器TreeSetCustomer customers new TreeSet( Comparator.comparingInt(Customer::getLevel) .thenComparing(Customer::getName) ); customers.add(new Customer(2, 张三)); customers.add(new Customer(1, 李四)); customers.add(new Customer(2, 王五)); customers.add(new Customer(1, 赵六)); System.out.println(customers);输出[Customer{level1, name赵六}, Customer{level1, name李四}, Customer{level2, name张三}, Customer{level2, name王五}]这个案例说明几个问题Comparator.comparingInt(...).thenComparing(...)是链式写比较器的主流方式语义清晰TreeSet在多个字段组合比较下既能保证排序稳定也能让去重结果符合“所有参与比较的字段都相等才算重复”的直觉。5.4 子集视图的动态特性演示一个容易踩坑又很实用的例子是区间动态视图。我们构造一个 1 到 10 的集合取出 3 到 7 的区间然后往原集合里添加新元素再看子集变化TreeSetInteger all new TreeSet(); for (int i 1; i 10; i) { all.add(i); } NavigableSetInteger sub all.subSet(3, true, 7, true); System.out.println(初始子集 sub); all.add(6); all.add(9); all.add(11); all.remove(4); System.out.println(原集合 all); System.out.println(修改后子集 sub);这段代码跑下来子集会实时反映原集合中落在 [3, 7] 区间内的元素变化新增 6 会立即出现在子集中删除 4 会立即从子集消失新增 9 和 11 则不会影响子集。这种视图行为如果没看过源码第一直觉会以为sub是独立快照进而怀疑遇到了并发问题。理解了包私有构造器复用 NavigableMap 的原理就对这种现象习以为常了。6. 常见问题与踩坑实录6.1 null 元素和 ClassCastExceptionTreeSet默认不能装 null。原因不是 Set 实现刻意拒绝而是底层TreeMap在比较时会强转Comparable或调用Comparator.comparenull 参与比较大概率抛NullPointerException。我见过有人往TreeSet里 add null 后试图 catchNullPointerException但add方法本身并不做 null 检查异常类型也不是IllegalArgumentException这会让上层代码很难理解。与其依赖异常不如在业务层自己控制保证入参非空。如果确实需要支持 null可以通过自定义比较器给 null 分配一个特殊位置比如让 null 永远排最前面TreeSetString set new TreeSet((a, b) - { if (a null b null) return 0; if (a null) return -1; if (b null) return 1; return a.compareTo(b); });这种方法能用但不推荐随意引入因为它会让代码阅读成本变高也让排序规则变得不那么直观。6.2 修改元素导致顺序错乱TreeSet的元素一旦放入就不应该再被修改到“参与比较的字段”。红黑树的顺序是在插入时确定的节点在树中的位置不会因为字段变化自动调整。如果你修改了一个元素比如自定义比较器按score比较而某个元素的score变了树结构依然保持旧位置遍历结果就不再有序甚至可能导致contains、remove行为变得不可预测。这种问题比HashSet的 hash 值变化更隐蔽因为HashSet里修改会影响hashCode但那个问题只要保证hashCode参与字段不变就不会出现。TreeSet则是所有排序字段都不宜在入树后变动。实在要改规范做法是先remove再add让节点重新进入红黑树。看起来多了一次删除和插入的开销但换来的是集合状态可靠。6.3 线程安全与并发修改TreeSet和大多数集合一样是非线程安全的。多线程环境下同时写轻则数据错乱重则抛出ConcurrentModificationException。JDK 官方推荐的做法是用Collections.synchronizedSortedSet(new TreeSet())包一层但这种包装只解决单个方法调用的原子性无法保证复合操作的安全性例如“先 contains 再 add”中间仍可能有其他线程插入。如果你需要真正的并发安全又必须保持有序可以考虑ConcurrentSkipListSet。它是基于跳表实现的有序并发集合写入和查询复杂度同样是 O(log n)但通过乐观锁和无锁数据结构支持高并发。很多即时排行榜场景用这个替代TreeSet会更合适。源码层面克制一下ConcurrentSkipListSet是另一个值得研究的数据结构但那是后话。6.4 性能对比什么时候不要用 TreeSetTreeSet不是万能的它的 O(log n) 读写和红黑树旋转带来的常数因子在大部分场景下慢于HashSet。我把三种常见 Set 的特性做了对比实现读复杂度写复杂度有序性适用场景HashSetO(1)O(1)否快速去重、成员判断LinkedHashSetO(1)O(1)保持插入顺序去重且需要按插入序遍历TreeSetO(log n)O(log n)按比较器排序有序集合、区间查询、最值查找如果你的业务只是“去重”不关心遍历顺序优先选HashSet。如果既要去重又要保留插入顺序选LinkedHashSet。只有当你明确需要按元素内容排序、频繁做范围遍历或找相邻元素时才值得付出 O(log n) 的代价用TreeSet。数据量很小几十到几百条时差异肉眼看不出来一旦到了十万级TreeSet的contains查询会比HashSet慢好几个数量级尤其在热路径上这种性能损耗会被放大。所以“能有序又能去重”不等于“处处用它好”选型还是要回到数据结构的本质。我个人在实际项目里用TreeSet有一条经验凡是最终要生成“有序列表”且数据会动态增删的场景优先考虑它凡是只在内存里临时去重、完了就转成 List 的场景直接用HashSet。做区间统计时还会先估算一下子集视图会不会长时间持有防止引用问题导致内存无法释放。源码看多了会发现集合类的选型本质是读、写、有序、并发这四个维度的权衡TreeSet在其中占了“有序”这一格而那一格恰好是很多业务离不开的能力。