先说个直觉只要你在Java里碰到“需要有序集合”这种需求十有八九会想到TreeSet。这个类的存在感一直不低但很多开发者对它的认知停留在“能用”“会add、会遍历”这个层面至于它底层怎么做到有序、为什么插入重复元素会静默失败、排序规则踩了哪些坑系统讲清楚的人不算多。我最初接触TreeSet时也吃了不少亏排序字段设计不合理导致运行时异常、视图方法边界记混、对象equals和compareTo结果不一致引发的诡异去重问题这类问题排查起来特别费神。所以这篇东西我想把TreeSet从头到尾拆一遍从底层实现到常用方法再到自定义排序、源码行为边界、性能对比把该踩的坑提前指出来。TreeSet适合谁来参考正在学Java集合框架的人或工作中需要选型“有序去重容器”的开发者都可以看看。读完之后你至少能回答三个问题TreeSet的有序到底怎么来的它的去重规则和HashSet有什么本质区别什么场景该用TreeSet、什么场景不该用1. 先搞清楚TreeSet的设计定位有序去重从哪来很多教程一上来就讲红黑树讲得人昏昏欲睡。其实你不需要先啃数据结构课本可以从“TreeSet到底是个什么东西”这个层面切入。1.1 从TreeMap说起TreeSet其实是个“壳”TreeSet的本质是TreeMap的一个视图。看名字就知道TreeSet内部维护的是一个TreeMap而它对外暴露的“集合”语义其实是基于这个Map的key集合实现的。我从源码层面验证过这一点。TreeSet的默认构造器里面写的是public TreeSet() { this(new TreeMapE, Object()); }这里有两个重载构造器一个是无参构造器内部直接new TreeMap另一个是接收NavigableMap参数的构造器比如TreeSet(NavigableMapE,Object m)这个构造器是包私有package-private的用于接收外部传入的NavigableMap比如通过descendingSet()返回的视图。有兴趣可以自己去翻JDK源码在java.util.TreeSet里你会看到一个private static final Object PRESENT new Object();这样的哨兵对象。每次add一个元素实际执行的是private static final Object PRESENT new Object(); public boolean add(E e) { return m.put(e, PRESENT) null; }也就是说你把一个元素add进TreeSet底层它的上是Map的keyvalue恒为这个静态的PRESENT对象。这个设计的妙处在于TreeMap本身已经实现了红黑树、排序、节点平衡这些复杂逻辑TreeSet不需要重复实现只需要复用Map的key机制。TreeSet移除元素也是一样的逻辑remove(Object o)对应TreeMap的remove(Object key)。所以理解TreeSet排序与去重机制本质上就是理解TreeMap如何管理key。1.2 红黑树是啥你为什么不用懂太深但要知道它带来的复杂度TreeMap之所以能有序核心是它用了一棵红黑树Red-Black Tree来存储节点。红黑树是自平衡的二叉查找树它保证数据在插入、删除后依然能维持大致平衡从而把查找、插入、删除的时间复杂度控制在O(log n)。这个复杂度意味着当你有100万个元素时TreeSet的操作大约需要20次比较就能定位到目标效率并不差。红黑树本身有五个约束条件比如节点是红色或黑色、根节点是黑色、红色节点的子节点必须是黑色、从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点等。这些约束保证了树的高度最长不会超过2倍的“黑高”从而避免了二叉搜索树退化成一个链表如果输入是有序数据普通二叉搜索树会完全退化成线性结构查找复杂度变成O(n)。红黑树的核心价值在工程上的表现是稳定的O(log n)而不是理论最优O(log n)。因为如果只是要求平均复杂度普通二叉搜索树也能做到但一旦遇到最坏情况比如顺序插入就会退化。红黑树的自平衡特性牺牲了部分插入性能每次插入最多两次旋转换来了最坏情况下的稳定查找效率。我在看TreeMap源码时有一个明确感受put方法在插入节点后调用了fixAfterInsertion这个私有方法里面根据叔父节点、父节点的颜色情况做左旋、右旋、变色操作这就是红黑树的平衡过程。你不用看懂每个旋转分支是怎么推导出来的只要知道“树在每次修改后会自动调整结构使查找路径保持较短”就可以了。注意红黑树的旋转和变色是在TreeMap内部完成对使用TreeSet的程序员完全透明。不需要你手动触发什么操作。2. TreeSet的基础使用从增删查到视图TreeSet的使用方法比HashMap简单很多但有几个方法的行为边界值得仔细确认。2.1 增删查六个常用方法一次说清TreeSet实现了NavigableSetE接口而NavigableSet继承自SortedSet所以它的核心方法除了add/remove/contains之外还有一整套与排序相关的API。增删查的核心逻辑就是TreeMap的put/get/remove但有一些语义细节add(E e)如果元素已存在按比较器或自然顺序比较不会覆盖旧元素直接返回false。这一点与Map.put不同Map.put会覆盖旧值。TreeSet里“已存在”的判断标准是comparator.compare(e, existing) 0不是equals。remove(Object o)返回boolean如果集合中存在这个元素则删除并返回true。注意参数是Object类型如果传入的对象类型不兼容比较时大概率抛ClassCastException。contains(Object o)同样基于比较结果定位元素看是否存在compare结果等于0的节点。按值查不到是O(log n)级别的操作。这几个方法的复杂度都是O(log n)和HashMap的近似O(1)相比在大量contains检查的场景下会有性能差异。除了增删查还有一个容易忽略的操作clear()。底层是TreeMap的clear直接把根节点置空同时size置零没有逐节点释放。2.2 视图方法subSet、headSet、tailSet的边界规则视图是TreeSet比较有特色的功能。所谓视图指的是基于原集合创建的一个“有条件的子集”视图它不是复制数据而是引用原集合的一部分范围。TreeSet提供了三个经典视图方法NavigableSetE subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) NavigableSetE headSet(E toElement, boolean inclusive) NavigableSetE tailSet(E fromElement, boolean inclusive)subSet返回从from到to之间的元素两个boolean参数分别控制两端是否包含边界headSet返回小于toElement的元素默认不含边界tailSet返回大于等于fromElement的元素。边界规则建议用例子记忆。假设有一个TreeSet包含了[1, 3, 5, 7, 9]subSet(3, true, 7, false)返回[3, 5]包含3不包含7headSet(5, false)返回[1, 3]tailSet(5, true)返回[5, 7, 9]视图有一个bug级别的坑你不能往视图里插入超出其边界范围的元素一插就抛IllegalArgumentException。举个例子subSet(3, true, 7, false)是[3, 5]你向这个视图更新add一个9会直接异常。这个异常信息往往只在运行时暴露代码编译期完全检查不出来。我第一次踩到这个坑时是在一个分页查询的逻辑里当时往subSet视图add了边界外的值线上环境弹出异常才开始排查后来反复看源码才发现视图add方法里有keyOutOfRange校验。反过来讲视图也支持在边界内add和remove这些操作会直接反映到原集合上因为它们是同一个红黑树的数据。视图不持有独立数据结构它持有原TreeMap的引用通过范围判断来限制操作范围。2.3 我能取到的“最值”first、last、ceiling、floor全家桶TreeSet不仅知道集合里有什么还能快速告诉你“最小的”“最大的”“向上最近的”“向下最近的”是什么。这是SortedSet接口赋予它的天然优势因为红黑树的最左节点就是最小值最右节点就是最大值。first()返回集合中最小的元素last()返回集合中最大的元素ceiling(E e)返回大于等于e的最小元素如果没有则返回nullfloor(E e)返回小于等于e的最大元素如果没有则返回nullhigher(E e)返回严格大于e的最小元素lower(E e)返回严格小于e的最大元素这六个方法在做区间查找时特别有用远比遍历集合然后自己判断来得高效。不过需要注意ceiling这类方法要求传入的参数E与集合中的元素类型一致如果是自定义对象comparator不能为null否则会按照自然顺序进行比较可能抛出ClassCastException。有人会问pollFirst()和pollLast()是什么意思这两个方法分别移除并返回最小/最大元素如果没有元素则返回null。它们的实现也是基于TreeMap的pollFirstEntry/pollLastEntry但有一个细节底层entry是延迟访问调用poll返回null时它不会额外查一次直接通过节点为空判断。3. 自定义排序这是TreeSet的灵魂如果你只用TreeSet放数字和字符串那基本体现不出它的强大。真正让TreeSet在业务中大放异彩的是它支持自定义排序规则特别是放入自定义对象时。3.1 Comparable vs Comparator两种写法怎么选TreeSet排序有两种方式元素本身实现Comparable接口或者给TreeSet传入一个外部Comparator。自然排序Comparable要求你的类实现compareTo方法比如public class Person implements ComparablePerson { private String name; private int age; public Person(String name, int age) { this.name name; this.age age; } Override public int compareTo(Person other) { return Integer.compare(this.age, other.age); } }外部排序Comparator是在创建TreeSet时传入lambda或匿名类TreeSetPerson people new TreeSet( (p1, p2) - p1.getName().compareTo(p2.getName()) );这两者怎么选我的经验是如果“排序规则”是对象这个业务实体固有的属性比如人的年龄、学生的学号可以考虑实现Comparable。但如果同一个类在不同业务场景下有不同排序需求比如某些页面按年龄排某些页面按姓名排那用Comparator更灵活每次创建TreeSet传入不同比较器即可。并且Comparator是Java 8之后函数式接口lambda写起来非常轻量所以我在实际开发里更倾向Comparator。还有一个细节如果同时实现了Comparable又传入了ComparatorTreeSet优先使用构造时传入的Comparator忽略元素自身的compareTo。这个行为在TreeMap的put方法里有明确分支你可以在源码中看到Comparator? super K cpr comparator; if (cpr ! null) { ... } else { ... }也就是说“外部比较器优先于自然顺序”。3.2 排序与去重的唯一标准compareTo返回值决定一切TreeSet的去重是基于比较结果而不是equals/hashCode。这一点务必牢记。TreeMap在put元素时核心逻辑是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); }当compare返回0时TreeMap不是插入新节点而是替换旧节点的value。到TreeSet这里因为value都是PRESENT所以效果就是“不插入add返回false”相当于去重。所以TreeSet的去重规则完全由compareTo/Comparator.compare的返回值决定。两个对象哪怕属性完全不同只要compare方法返回0它们就会被认为是同一个元素。反过来equals相等但compare结果不是0那TreeSet中会同时存在这两个对象因为红黑树走的是compare分支equals根本不会参与插入路径。这种“排序与equals不一致”的情况容易引发严重bug。比如某个人物对象id相同但姓名不同compare只按name排那id相同的两条记录可能同时共存这与数据库的唯一约束在语义上不一致会莫名其妙出现“重复”数据。最佳实践是放进TreeSet的自定义对象equals返回true的条件必须与compare 0的条件保持一致。如果不是完全一致至少在业务语义上要保证“compare结果为0的两个对象本质上代表同一条数据”。3.3 自定义对象排序的完整案例从定义到测试用一个完整案例来说明自定义排序怎么写避免纸上谈兵。场景一个在线考试系统的学生成绩排名功能需要按总分从高到低排序分数相同则按学号升序。先定义Student类注意不要实现Comparable用外部Comparator完成多级排序public class Student { private String studentId; private String name; private int totalScore; public Student(String studentId, String name, int totalScore) { this.studentId studentId; this.name name; this.totalScore totalScore; } public String getStudentId() { return studentId; } public String getName() { return name; } public int getTotalScore() { return totalScore; } Override public String toString() { return String.format(%s(%s): %d, name, studentId, totalScore); } }创建TreeSet并传入多级排序比较器TreeSetStudent rankSet new TreeSet( (s1, s2) - { // 总分降序 int scoreCmp Integer.compare(s2.getTotalScore(), s1.getTotalScore()); if (scoreCmp ! 0) { return scoreCmp; } // 总分相同按学号升序 return s1.getStudentId().compareTo(s2.getStudentId()); } ); rankSet.add(new Student(S001, 小张, 285)); rankSet.add(new Student(S002, 小李, 292)); rankSet.add(new Student(S003, 小王, 285)); System.out.println(rankSet);输出结果会是小李(S002): 292 小张(S001): 285 小王(S003): 285这个例子里如果小张和小王的总分一样但学号不同那么他们会被视为不同元素可以同时存在因为比较器返回的不是0。但如果有一个新对象与小王的总分和学号完全一样add时会返回false它就无法插入。这个多级排序在实际面试和业务中都很常见。“先按分数降序再按学号升序”这种复合排序用Comparator写起来清晰、稳定而且天然解决了“去重依据”的问题。如果只想按一个字段排比如按学号那后面的字段比较可以省略但在业务上如果学号相同就是同一个人那省略后去重规则也是合理的。4. 不可忽视的坑从源码反推出来的“行为边界”TreeSet的行为边界有时候不是一眼能看出来的需要通过源码和踩坑经验总结出来。这一部分我觉得比使用本身更有价值因为很多故障排查到最后问题根源都在这些比较隐蔽的细节里。4.1 排序字段必须是不可变的可变对象翻车实录这个问题我遇到过一次教训很深刻。当时有一个业务用TreeSet维护一批按“最后操作时间”排序的任务排序字段是一个可变的long字段本意是每次任务更新后将时间戳更改TreeSet能自动调整顺序。但红黑树的节点一旦插入树的结构就固定下来了修改元素内部的排序字段TreeSet不会重新调整节点位置。翻车现场是这样的class Task { long lastAccessTime; // getter setter 省略 } TreeSetTask taskSet new TreeSet(Comparator.comparingLong(t - t.lastAccessTime)); Task task new Task(); task.lastAccessTime 100; taskSet.add(task); // 修改任务时间 task.lastAccessTime 999; System.out.println(taskSet); // 顺序不会改变还是按100的位置存储如果后续你用taskSet.contains(task)去查这个task对象可能返回false因为contains时会用新的lastAccessTime999去红黑树中查找而树中该节点的位置是按100构建的查找路径会走错分支结果可能定位不到当前对象。这就是“对象存在于集合中却查不到自己”的诡异现象。正确做法排序字段设计成不可变或者需要修改排序属性时先remove再修改再重新add。remove后修改再add会触发重新插入和树平衡顺序才会刷新。4.2 null到底能不能塞进TreeSetTreeSet对null的态度有点微妙。如果是无参构造器创建的TreeSet即不传Comparator使用自然顺序那么add(null)会抛NullPointerException。因为String等自然排序的类在compareTo时会对null调用方法直接NPE。如果是传入Comparator的TreeSet取决于Comparator本身是否支持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); });这样add(null)能成功null会排在所有元素的前面因为null被认为比任何非null小。我在实际编码中不建议往TreeSet中放null那个“null在前”的排序规则理解和维护成本太高其他人在读代码时容易产生误会。如果确实需要表示“空”的情况建议用Optional或者预设的哨兵对象。4.3 TreeSet不是线程安全的怎么破TreeSet本身并未做任何同步处理和HashMap一样多线程并发修改场景下可能出现数据不一致甚至树的红黑结构被破坏毕竟put和remove都涉及指针修改和旋转操作。常见的解决方案有三个使用Collections.synchronizedSortedSet(new TreeSet())包装得到一个同步视图。这样每个方法都被synchronized保护但迭代时仍然需要外部同步否则ConcurrentModificationException照样出来。使用并发包里的ConcurrentSkipListSet。这是一个基于跳表实现的有序并发集合线程安全程度比包装的TreeSet高得多支持并发读写而不需要外部加锁。如果不强制要求红黑树特性这个类是TreeSet的并发替代品。全局加锁不过那样并发提升有限。我在一个配置中心项目里用过TreeSet做优先级任务排序同时会有多个线程提交任务后来并发量上来后发现偶发异常定位到是TreeSet内部结构在并发修改下出现了不一致。后来改用ConcurrentSkipListSet这个问题就再没出现过。如果要追求无锁读、分段写ConcurrentSkipListSet在某些场景下是更好的选择。5. 性能对比与选型什么时候该用它最后从选型角度讨论一下TreeSet的定位。Java集合框架里有序、去重的容器不只是TreeSet一种和它最常被比较的是HashSet与LinkedHashSet三者的特性差异直接决定使用场景。5.1 HashSet、LinkedHashSet、TreeSet三兄弟对比为了表述清晰我整理了一张对比表维度HashSetLinkedHashSetTreeSet底层结构哈希表HashMap哈希表 链表红黑树TreeMap是否有序无序按插入顺序按排序规则自然或自定义时间复杂度O(1) 平均O(1) 平均O(log n)是否允许null允许一个null允许一个null自然排序不允许指定Comparator时可允许去重依据hashCode equalshashCode equalscompareTo / Comparator 0内存占用较低但hash扩容较高额外链表指针较高树节点左右指针颜色位适用场景快速查重、无序集合需要保持插入顺序的去重集合需要排序、范围查询、极值查询关键区别在三点排序能力、去重依据、时间复杂度。如果只需要去重且不关心遍历顺序HashSet是最简单高效的。如果需要保持插入顺序选LinkedHashSet。如果遍历时要“从小到大”或“按业务规则排序”TreeSet是天然契合的。5.2 实测场景100万条数据的表现为了让大家对这些复杂度差异有一个直观感受我做过一个简单的基准测试向HashSet、TreeSet分别插入100万条随机整数然后随机contains100万次。在我的普通开发机上HashSet插入和查询耗时大约在100~200ms级别TreeSet在300~500ms级别整体差距在2~3倍左右。这不是绝对数据具体受JVM参数、数据分布影响但大体量级可以参考。结论是如果只是简单的去重和查找HashSet的常数优势足够明显没必要因为“以后可能要排序”而上TreeSet。排序真正的价值不在数据量小的时候体现而在“需要对有序集合做范围查询、极值查询、视图截取”时表现突出。比如在一个排行榜场景里你需要随时取出Top NTreeSet的descendingSet()配合迭代器取前N个实现起来非常直观TreeSetStudent rankSet new TreeSet( Comparator.comparingInt(Student::getTotalScore).reversed() ); // 插入若干学生... // 取前10名 ListStudent top10 new ArrayList(); int count 0; for (Student s : rankSet) { if (count 10) break; top10.add(s); }这种场景如果用HashSet你需要自己维护一个排序集合或者每次全量排序麻烦而且费时。5.3 典型应用场景排名、区间、自动排序结合我的开发经验TreeSet最适合的三类场景如下。排名与Top N比如游戏排行榜、考试排名等要求集合按分数排序且插入需去重。用TreeSet自定义Comparator能轻松取前N个或任意区间。这里要注意分数相同时必须有次级排序字段如学号、id否则分数相同但id不同的记录会被当作相同元素产生不期望的去重。区间查询比如“查询价格在100到200之间的商品”TreeSet的subSet(100, true, 200, true)可以在O(log n k)的复杂度内返回结果k为返回元素个数。这个能力是HashSet完全不具备的。滑动窗口或最近活跃集合如果元素按时间排序需要不断淘汰过期数据TreeSet配合pollFirst可以高效移除最老元素。当然如果并发要求高可以考虑ConcurrentSkipListSet。我在一个模拟系统中用TreeSet维护了在线用户列表按照最后活跃时间排序每过一段时间就取出最不活跃的若干用户并清理整体代码非常清爽避免了每次全量排序的开销。最后分享两个实操中的小技巧如果用TreeSet处理自定义对象一定重新定义equals和hashCode吗我的答案是确保equals和compare行为一致但不必强求两者返回完全相同的语义。如果是简单对象且Comparator只按一个唯一业务字段比较equals和hashCode也基于该字段实现那么放入TreeSet后逻辑自洽。如果两者不一致最危险的是contains、remove等操作可能与预期不符因为它们虽然在TreeMap内部其实只使用compare定位但如果别的集合如HashMap中也放了同样的对象就可能导致两个集合表现不一致。所以我通常建议如果对象要同时放进HashSet和TreeSet保持equals/hashCode与compare语义一致是最省心的。第二点关于“排序稳定性”。TreeSet不保证当排序字段相同时的元素顺序与插入顺序一致也不保证equals相同但compare相同的元素保留哪一个TreeMap的put会把新值覆盖旧值TreeSet不会保留旧节点也不会像LinkedHashSet那样保留插入序。所以如果业务上需要“相同分数按时间先来后到”这样的规则一定要写在Comparator里依赖TreeSet的隐式顺序是不靠谱的。TreeSet是一个值得深入掌握的集合类它的有序能力不是装饰而是红黑树这个数据结构带来的真实功能。把它的行为边界和源码逻辑摸清楚后再用它真的香。希望这篇总结能帮你少踩几个坑。
先说个直觉只要你在Java里碰到“需要有序集合”这种需求十有八九会想到TreeSet。这个类的存在感一直不低但很多开发者对它的认知停留在“能用”“会add、会遍历”这个层面至于它底层怎么做到有序、为什么插入重复元素会静默失败、排序规则踩了哪些坑系统讲清楚的人不算多。我最初接触TreeSet时也吃了不少亏排序字段设计不合理导致运行时异常、视图方法边界记混、对象equals和compareTo结果不一致引发的诡异去重问题这类问题排查起来特别费神。所以这篇东西我想把TreeSet从头到尾拆一遍从底层实现到常用方法再到自定义排序、源码行为边界、性能对比把该踩的坑提前指出来。TreeSet适合谁来参考正在学Java集合框架的人或工作中需要选型“有序去重容器”的开发者都可以看看。读完之后你至少能回答三个问题TreeSet的有序到底怎么来的它的去重规则和HashSet有什么本质区别什么场景该用TreeSet、什么场景不该用1. 先搞清楚TreeSet的设计定位有序去重从哪来很多教程一上来就讲红黑树讲得人昏昏欲睡。其实你不需要先啃数据结构课本可以从“TreeSet到底是个什么东西”这个层面切入。1.1 从TreeMap说起TreeSet其实是个“壳”TreeSet的本质是TreeMap的一个视图。看名字就知道TreeSet内部维护的是一个TreeMap而它对外暴露的“集合”语义其实是基于这个Map的key集合实现的。我从源码层面验证过这一点。TreeSet的默认构造器里面写的是public TreeSet() { this(new TreeMapE, Object()); }这里有两个重载构造器一个是无参构造器内部直接new TreeMap另一个是接收NavigableMap参数的构造器比如TreeSet(NavigableMapE,Object m)这个构造器是包私有package-private的用于接收外部传入的NavigableMap比如通过descendingSet()返回的视图。有兴趣可以自己去翻JDK源码在java.util.TreeSet里你会看到一个private static final Object PRESENT new Object();这样的哨兵对象。每次add一个元素实际执行的是private static final Object PRESENT new Object(); public boolean add(E e) { return m.put(e, PRESENT) null; }也就是说你把一个元素add进TreeSet底层它的上是Map的keyvalue恒为这个静态的PRESENT对象。这个设计的妙处在于TreeMap本身已经实现了红黑树、排序、节点平衡这些复杂逻辑TreeSet不需要重复实现只需要复用Map的key机制。TreeSet移除元素也是一样的逻辑remove(Object o)对应TreeMap的remove(Object key)。所以理解TreeSet排序与去重机制本质上就是理解TreeMap如何管理key。1.2 红黑树是啥你为什么不用懂太深但要知道它带来的复杂度TreeMap之所以能有序核心是它用了一棵红黑树Red-Black Tree来存储节点。红黑树是自平衡的二叉查找树它保证数据在插入、删除后依然能维持大致平衡从而把查找、插入、删除的时间复杂度控制在O(log n)。这个复杂度意味着当你有100万个元素时TreeSet的操作大约需要20次比较就能定位到目标效率并不差。红黑树本身有五个约束条件比如节点是红色或黑色、根节点是黑色、红色节点的子节点必须是黑色、从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点等。这些约束保证了树的高度最长不会超过2倍的“黑高”从而避免了二叉搜索树退化成一个链表如果输入是有序数据普通二叉搜索树会完全退化成线性结构查找复杂度变成O(n)。红黑树的核心价值在工程上的表现是稳定的O(log n)而不是理论最优O(log n)。因为如果只是要求平均复杂度普通二叉搜索树也能做到但一旦遇到最坏情况比如顺序插入就会退化。红黑树的自平衡特性牺牲了部分插入性能每次插入最多两次旋转换来了最坏情况下的稳定查找效率。我在看TreeMap源码时有一个明确感受put方法在插入节点后调用了fixAfterInsertion这个私有方法里面根据叔父节点、父节点的颜色情况做左旋、右旋、变色操作这就是红黑树的平衡过程。你不用看懂每个旋转分支是怎么推导出来的只要知道“树在每次修改后会自动调整结构使查找路径保持较短”就可以了。注意红黑树的旋转和变色是在TreeMap内部完成对使用TreeSet的程序员完全透明。不需要你手动触发什么操作。2. TreeSet的基础使用从增删查到视图TreeSet的使用方法比HashMap简单很多但有几个方法的行为边界值得仔细确认。2.1 增删查六个常用方法一次说清TreeSet实现了NavigableSetE接口而NavigableSet继承自SortedSet所以它的核心方法除了add/remove/contains之外还有一整套与排序相关的API。增删查的核心逻辑就是TreeMap的put/get/remove但有一些语义细节add(E e)如果元素已存在按比较器或自然顺序比较不会覆盖旧元素直接返回false。这一点与Map.put不同Map.put会覆盖旧值。TreeSet里“已存在”的判断标准是comparator.compare(e, existing) 0不是equals。remove(Object o)返回boolean如果集合中存在这个元素则删除并返回true。注意参数是Object类型如果传入的对象类型不兼容比较时大概率抛ClassCastException。contains(Object o)同样基于比较结果定位元素看是否存在compare结果等于0的节点。按值查不到是O(log n)级别的操作。这几个方法的复杂度都是O(log n)和HashMap的近似O(1)相比在大量contains检查的场景下会有性能差异。除了增删查还有一个容易忽略的操作clear()。底层是TreeMap的clear直接把根节点置空同时size置零没有逐节点释放。2.2 视图方法subSet、headSet、tailSet的边界规则视图是TreeSet比较有特色的功能。所谓视图指的是基于原集合创建的一个“有条件的子集”视图它不是复制数据而是引用原集合的一部分范围。TreeSet提供了三个经典视图方法NavigableSetE subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) NavigableSetE headSet(E toElement, boolean inclusive) NavigableSetE tailSet(E fromElement, boolean inclusive)subSet返回从from到to之间的元素两个boolean参数分别控制两端是否包含边界headSet返回小于toElement的元素默认不含边界tailSet返回大于等于fromElement的元素。边界规则建议用例子记忆。假设有一个TreeSet包含了[1, 3, 5, 7, 9]subSet(3, true, 7, false)返回[3, 5]包含3不包含7headSet(5, false)返回[1, 3]tailSet(5, true)返回[5, 7, 9]视图有一个bug级别的坑你不能往视图里插入超出其边界范围的元素一插就抛IllegalArgumentException。举个例子subSet(3, true, 7, false)是[3, 5]你向这个视图更新add一个9会直接异常。这个异常信息往往只在运行时暴露代码编译期完全检查不出来。我第一次踩到这个坑时是在一个分页查询的逻辑里当时往subSet视图add了边界外的值线上环境弹出异常才开始排查后来反复看源码才发现视图add方法里有keyOutOfRange校验。反过来讲视图也支持在边界内add和remove这些操作会直接反映到原集合上因为它们是同一个红黑树的数据。视图不持有独立数据结构它持有原TreeMap的引用通过范围判断来限制操作范围。2.3 我能取到的“最值”first、last、ceiling、floor全家桶TreeSet不仅知道集合里有什么还能快速告诉你“最小的”“最大的”“向上最近的”“向下最近的”是什么。这是SortedSet接口赋予它的天然优势因为红黑树的最左节点就是最小值最右节点就是最大值。first()返回集合中最小的元素last()返回集合中最大的元素ceiling(E e)返回大于等于e的最小元素如果没有则返回nullfloor(E e)返回小于等于e的最大元素如果没有则返回nullhigher(E e)返回严格大于e的最小元素lower(E e)返回严格小于e的最大元素这六个方法在做区间查找时特别有用远比遍历集合然后自己判断来得高效。不过需要注意ceiling这类方法要求传入的参数E与集合中的元素类型一致如果是自定义对象comparator不能为null否则会按照自然顺序进行比较可能抛出ClassCastException。有人会问pollFirst()和pollLast()是什么意思这两个方法分别移除并返回最小/最大元素如果没有元素则返回null。它们的实现也是基于TreeMap的pollFirstEntry/pollLastEntry但有一个细节底层entry是延迟访问调用poll返回null时它不会额外查一次直接通过节点为空判断。3. 自定义排序这是TreeSet的灵魂如果你只用TreeSet放数字和字符串那基本体现不出它的强大。真正让TreeSet在业务中大放异彩的是它支持自定义排序规则特别是放入自定义对象时。3.1 Comparable vs Comparator两种写法怎么选TreeSet排序有两种方式元素本身实现Comparable接口或者给TreeSet传入一个外部Comparator。自然排序Comparable要求你的类实现compareTo方法比如public class Person implements ComparablePerson { private String name; private int age; public Person(String name, int age) { this.name name; this.age age; } Override public int compareTo(Person other) { return Integer.compare(this.age, other.age); } }外部排序Comparator是在创建TreeSet时传入lambda或匿名类TreeSetPerson people new TreeSet( (p1, p2) - p1.getName().compareTo(p2.getName()) );这两者怎么选我的经验是如果“排序规则”是对象这个业务实体固有的属性比如人的年龄、学生的学号可以考虑实现Comparable。但如果同一个类在不同业务场景下有不同排序需求比如某些页面按年龄排某些页面按姓名排那用Comparator更灵活每次创建TreeSet传入不同比较器即可。并且Comparator是Java 8之后函数式接口lambda写起来非常轻量所以我在实际开发里更倾向Comparator。还有一个细节如果同时实现了Comparable又传入了ComparatorTreeSet优先使用构造时传入的Comparator忽略元素自身的compareTo。这个行为在TreeMap的put方法里有明确分支你可以在源码中看到Comparator? super K cpr comparator; if (cpr ! null) { ... } else { ... }也就是说“外部比较器优先于自然顺序”。3.2 排序与去重的唯一标准compareTo返回值决定一切TreeSet的去重是基于比较结果而不是equals/hashCode。这一点务必牢记。TreeMap在put元素时核心逻辑是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); }当compare返回0时TreeMap不是插入新节点而是替换旧节点的value。到TreeSet这里因为value都是PRESENT所以效果就是“不插入add返回false”相当于去重。所以TreeSet的去重规则完全由compareTo/Comparator.compare的返回值决定。两个对象哪怕属性完全不同只要compare方法返回0它们就会被认为是同一个元素。反过来equals相等但compare结果不是0那TreeSet中会同时存在这两个对象因为红黑树走的是compare分支equals根本不会参与插入路径。这种“排序与equals不一致”的情况容易引发严重bug。比如某个人物对象id相同但姓名不同compare只按name排那id相同的两条记录可能同时共存这与数据库的唯一约束在语义上不一致会莫名其妙出现“重复”数据。最佳实践是放进TreeSet的自定义对象equals返回true的条件必须与compare 0的条件保持一致。如果不是完全一致至少在业务语义上要保证“compare结果为0的两个对象本质上代表同一条数据”。3.3 自定义对象排序的完整案例从定义到测试用一个完整案例来说明自定义排序怎么写避免纸上谈兵。场景一个在线考试系统的学生成绩排名功能需要按总分从高到低排序分数相同则按学号升序。先定义Student类注意不要实现Comparable用外部Comparator完成多级排序public class Student { private String studentId; private String name; private int totalScore; public Student(String studentId, String name, int totalScore) { this.studentId studentId; this.name name; this.totalScore totalScore; } public String getStudentId() { return studentId; } public String getName() { return name; } public int getTotalScore() { return totalScore; } Override public String toString() { return String.format(%s(%s): %d, name, studentId, totalScore); } }创建TreeSet并传入多级排序比较器TreeSetStudent rankSet new TreeSet( (s1, s2) - { // 总分降序 int scoreCmp Integer.compare(s2.getTotalScore(), s1.getTotalScore()); if (scoreCmp ! 0) { return scoreCmp; } // 总分相同按学号升序 return s1.getStudentId().compareTo(s2.getStudentId()); } ); rankSet.add(new Student(S001, 小张, 285)); rankSet.add(new Student(S002, 小李, 292)); rankSet.add(new Student(S003, 小王, 285)); System.out.println(rankSet);输出结果会是小李(S002): 292 小张(S001): 285 小王(S003): 285这个例子里如果小张和小王的总分一样但学号不同那么他们会被视为不同元素可以同时存在因为比较器返回的不是0。但如果有一个新对象与小王的总分和学号完全一样add时会返回false它就无法插入。这个多级排序在实际面试和业务中都很常见。“先按分数降序再按学号升序”这种复合排序用Comparator写起来清晰、稳定而且天然解决了“去重依据”的问题。如果只想按一个字段排比如按学号那后面的字段比较可以省略但在业务上如果学号相同就是同一个人那省略后去重规则也是合理的。4. 不可忽视的坑从源码反推出来的“行为边界”TreeSet的行为边界有时候不是一眼能看出来的需要通过源码和踩坑经验总结出来。这一部分我觉得比使用本身更有价值因为很多故障排查到最后问题根源都在这些比较隐蔽的细节里。4.1 排序字段必须是不可变的可变对象翻车实录这个问题我遇到过一次教训很深刻。当时有一个业务用TreeSet维护一批按“最后操作时间”排序的任务排序字段是一个可变的long字段本意是每次任务更新后将时间戳更改TreeSet能自动调整顺序。但红黑树的节点一旦插入树的结构就固定下来了修改元素内部的排序字段TreeSet不会重新调整节点位置。翻车现场是这样的class Task { long lastAccessTime; // getter setter 省略 } TreeSetTask taskSet new TreeSet(Comparator.comparingLong(t - t.lastAccessTime)); Task task new Task(); task.lastAccessTime 100; taskSet.add(task); // 修改任务时间 task.lastAccessTime 999; System.out.println(taskSet); // 顺序不会改变还是按100的位置存储如果后续你用taskSet.contains(task)去查这个task对象可能返回false因为contains时会用新的lastAccessTime999去红黑树中查找而树中该节点的位置是按100构建的查找路径会走错分支结果可能定位不到当前对象。这就是“对象存在于集合中却查不到自己”的诡异现象。正确做法排序字段设计成不可变或者需要修改排序属性时先remove再修改再重新add。remove后修改再add会触发重新插入和树平衡顺序才会刷新。4.2 null到底能不能塞进TreeSetTreeSet对null的态度有点微妙。如果是无参构造器创建的TreeSet即不传Comparator使用自然顺序那么add(null)会抛NullPointerException。因为String等自然排序的类在compareTo时会对null调用方法直接NPE。如果是传入Comparator的TreeSet取决于Comparator本身是否支持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); });这样add(null)能成功null会排在所有元素的前面因为null被认为比任何非null小。我在实际编码中不建议往TreeSet中放null那个“null在前”的排序规则理解和维护成本太高其他人在读代码时容易产生误会。如果确实需要表示“空”的情况建议用Optional或者预设的哨兵对象。4.3 TreeSet不是线程安全的怎么破TreeSet本身并未做任何同步处理和HashMap一样多线程并发修改场景下可能出现数据不一致甚至树的红黑结构被破坏毕竟put和remove都涉及指针修改和旋转操作。常见的解决方案有三个使用Collections.synchronizedSortedSet(new TreeSet())包装得到一个同步视图。这样每个方法都被synchronized保护但迭代时仍然需要外部同步否则ConcurrentModificationException照样出来。使用并发包里的ConcurrentSkipListSet。这是一个基于跳表实现的有序并发集合线程安全程度比包装的TreeSet高得多支持并发读写而不需要外部加锁。如果不强制要求红黑树特性这个类是TreeSet的并发替代品。全局加锁不过那样并发提升有限。我在一个配置中心项目里用过TreeSet做优先级任务排序同时会有多个线程提交任务后来并发量上来后发现偶发异常定位到是TreeSet内部结构在并发修改下出现了不一致。后来改用ConcurrentSkipListSet这个问题就再没出现过。如果要追求无锁读、分段写ConcurrentSkipListSet在某些场景下是更好的选择。5. 性能对比与选型什么时候该用它最后从选型角度讨论一下TreeSet的定位。Java集合框架里有序、去重的容器不只是TreeSet一种和它最常被比较的是HashSet与LinkedHashSet三者的特性差异直接决定使用场景。5.1 HashSet、LinkedHashSet、TreeSet三兄弟对比为了表述清晰我整理了一张对比表维度HashSetLinkedHashSetTreeSet底层结构哈希表HashMap哈希表 链表红黑树TreeMap是否有序无序按插入顺序按排序规则自然或自定义时间复杂度O(1) 平均O(1) 平均O(log n)是否允许null允许一个null允许一个null自然排序不允许指定Comparator时可允许去重依据hashCode equalshashCode equalscompareTo / Comparator 0内存占用较低但hash扩容较高额外链表指针较高树节点左右指针颜色位适用场景快速查重、无序集合需要保持插入顺序的去重集合需要排序、范围查询、极值查询关键区别在三点排序能力、去重依据、时间复杂度。如果只需要去重且不关心遍历顺序HashSet是最简单高效的。如果需要保持插入顺序选LinkedHashSet。如果遍历时要“从小到大”或“按业务规则排序”TreeSet是天然契合的。5.2 实测场景100万条数据的表现为了让大家对这些复杂度差异有一个直观感受我做过一个简单的基准测试向HashSet、TreeSet分别插入100万条随机整数然后随机contains100万次。在我的普通开发机上HashSet插入和查询耗时大约在100~200ms级别TreeSet在300~500ms级别整体差距在2~3倍左右。这不是绝对数据具体受JVM参数、数据分布影响但大体量级可以参考。结论是如果只是简单的去重和查找HashSet的常数优势足够明显没必要因为“以后可能要排序”而上TreeSet。排序真正的价值不在数据量小的时候体现而在“需要对有序集合做范围查询、极值查询、视图截取”时表现突出。比如在一个排行榜场景里你需要随时取出Top NTreeSet的descendingSet()配合迭代器取前N个实现起来非常直观TreeSetStudent rankSet new TreeSet( Comparator.comparingInt(Student::getTotalScore).reversed() ); // 插入若干学生... // 取前10名 ListStudent top10 new ArrayList(); int count 0; for (Student s : rankSet) { if (count 10) break; top10.add(s); }这种场景如果用HashSet你需要自己维护一个排序集合或者每次全量排序麻烦而且费时。5.3 典型应用场景排名、区间、自动排序结合我的开发经验TreeSet最适合的三类场景如下。排名与Top N比如游戏排行榜、考试排名等要求集合按分数排序且插入需去重。用TreeSet自定义Comparator能轻松取前N个或任意区间。这里要注意分数相同时必须有次级排序字段如学号、id否则分数相同但id不同的记录会被当作相同元素产生不期望的去重。区间查询比如“查询价格在100到200之间的商品”TreeSet的subSet(100, true, 200, true)可以在O(log n k)的复杂度内返回结果k为返回元素个数。这个能力是HashSet完全不具备的。滑动窗口或最近活跃集合如果元素按时间排序需要不断淘汰过期数据TreeSet配合pollFirst可以高效移除最老元素。当然如果并发要求高可以考虑ConcurrentSkipListSet。我在一个模拟系统中用TreeSet维护了在线用户列表按照最后活跃时间排序每过一段时间就取出最不活跃的若干用户并清理整体代码非常清爽避免了每次全量排序的开销。最后分享两个实操中的小技巧如果用TreeSet处理自定义对象一定重新定义equals和hashCode吗我的答案是确保equals和compare行为一致但不必强求两者返回完全相同的语义。如果是简单对象且Comparator只按一个唯一业务字段比较equals和hashCode也基于该字段实现那么放入TreeSet后逻辑自洽。如果两者不一致最危险的是contains、remove等操作可能与预期不符因为它们虽然在TreeMap内部其实只使用compare定位但如果别的集合如HashMap中也放了同样的对象就可能导致两个集合表现不一致。所以我通常建议如果对象要同时放进HashSet和TreeSet保持equals/hashCode与compare语义一致是最省心的。第二点关于“排序稳定性”。TreeSet不保证当排序字段相同时的元素顺序与插入顺序一致也不保证equals相同但compare相同的元素保留哪一个TreeMap的put会把新值覆盖旧值TreeSet不会保留旧节点也不会像LinkedHashSet那样保留插入序。所以如果业务上需要“相同分数按时间先来后到”这样的规则一定要写在Comparator里依赖TreeSet的隐式顺序是不靠谱的。TreeSet是一个值得深入掌握的集合类它的有序能力不是装饰而是红黑树这个数据结构带来的真实功能。把它的行为边界和源码逻辑摸清楚后再用它真的香。希望这篇总结能帮你少踩几个坑。
![[基于OpenEvals的自动化评估-13]Agent执行轨迹评估[LLM-as-a-Judge]](http://pic.xiahunao.cn/yaotu/[基于OpenEvals的自动化评估-13]Agent执行轨迹评估[LLM-as-a-Judge])
