Java集合框架中的TreeSet与元素排序机制_技术教程

TreeSet要求元素必须可比较，因其底层基于TreeMap实现，依赖自然顺序或Comparator维护红黑树；若元素未实现Comparable且未传Comparator，运行时调用compareTo会抛ClassCastException或NullPointerException。

TreeSet 为什么要求元素必须可比较

TreeSet 底层是基于 TreeMap 实现的，而 TreeMap 依赖键的自然顺序或自定义比较器来维护红黑树结构。如果插入的元素既

没实现 Comparable 接口，又没传入 Comparator，运行时调用 compareTo() 就会抛出 ClassCastException 或 NullPointerException。

常见错误现象：

向空 TreeSet 添加 new Person("Alice", 25) 报错：java.lang.ClassCastException: Person cannot be cast to java.lang.Comparable
使用匿名内部类传 Comparator 但漏写 return，导致所有元素被当成相等，集合只保留一个

实操建议：

优先让实体类实现 Comparable，重写 compareTo()，注意处理 null 字段（如用 Objects.compare(a, b, Comparator.nullsLast(Comparator.naturalOrder()))）
若无法改类（如第三方类），务必在构造 TreeSet 时传入 Comparator，例如：new TreeSet(Comparator.comparing(String::length))
避免在 compareTo() 中调用可能返回 null 的方法且不做判空——这会导致 NullPointerException 被包装成 ClassCastException

自然排序与定制排序的参数差异

TreeSet 提供了 4 个构造方法，真正影响排序行为的只有两个签名：

public TreeSet()
public TreeSet(Comparator comparator)

前者依赖元素自身的 compareTo()，后者完全由你控制。其他两个构造方法（接受 Collection 或 SortedSet）只是把已有数据塞进去，排序逻辑仍继承自原集合或默认规则。

关键细节：

传入 null 的 Comparator 等价于不传——即走自然排序，不是“无序”
Comparator 的类型参数是 ? super E，意味着你可以用父类的比较器比较子类对象（如用 Comparator 比较 String），但反过来不行
如果用 Comparator.nullsFirst(...)，要注意 TreeSet 不允许 null 元素（除非比较器显式支持，且 JDK ≥ 1.7；JDK 1.6 及以前直接抛 NullPointerException）

TreeSet.add() 的时间复杂度与重复判断逻辑

每次 add() 都要走红黑树查找路径，平均 O(log n)，最坏也是 O(log n)。它不是靠 equals() 判断重复，而是靠 compareTo() == 0 或 compare() == 0 —— 这意味着：即使两个对象 equals() 返回 true，只要 compareTo() 不为 0，TreeSet 就认为它们不同；反之，compareTo() 为 0 但 equals() 为 false，TreeSet 也会拒绝插入第二个。

典型陷阱：

自定义 compareTo() 只比字段 A，但 equals() 还比字段 B → TreeSet 可能存下逻辑上“相等”的多个对象
用 Comparator.comparingInt(obj -> obj.id) 比较，但 id 有重复 → 后续插入同 id 对象会被静默忽略，不报错也不提醒
在 compareTo() 中用了浮点数直接比较（如 a.value - b.value），导致精度误差引发重复判断失效

正确做法是：确保 compareTo() 与 equals() 语义一致（《Effective Java》第 12 条），或明确接受“排序唯一性 ≠ 业务唯一性”并做额外校验。

TreeSet 的迭代顺序与 headSet/tailSet 行为

TreeSet 的迭代器返回的是升序（自然顺序或 Comparator 定义的顺序），这是确定行为，不是巧合。但要注意：headSet(e)、tailSet(e)、subSet(from, to) 返回的是**视图（view）**，不是新集合——对原 TreeSet 的修改会实时反映在子集中，反之亦然。

容易被忽略的点：

headSet(e) 默认是 不包含 e 的（JDK 1.6+），如果需要包含，得用 headSet(e, true)
对子集调用 add() 时，如果新元素超出原 TreeSet 的范围（比如往 headSet(10) 里加 15），会抛 IllegalArgumentException
TreeSet 不支持随机访问，没有 get(int index)；想取第 k 小元素，只能用迭代器走 k 步，或转成数组（牺牲空间换时间）