TreeSet基于TreeMap红黑树实现,按自然顺序或Comparator排序,时间复杂度O(log n),要求Comparable/Comparator逻辑一致且处理null需显式指定。
TreeSet 默认按自然顺序排序,本质是基于 TreeMap 的红黑树实现
TreeSet 本身不存储元素,它只是 TreeMap 的一个包装:内部用 TreeMap 的 key 存元素,value 固定为 PRESENT(一个空的 Object)。所以 TreeSet 的排序逻辑完全继承自 TreeMap —— 底层是左倾红黑树,插入、删除、查找都是 O(log n)。
这意味着:只要元素实现了 Comparable 接口(比如 Integer、String),或者你传入了 Comparator,TreeSet 就能自动维护有序性。它不依赖插入顺序,也不做额外排序操作。
自定义排序必须确保 Comparator 或 Comparable 逻辑严格一致
常见错误是 compareTo() 或 compare() 返回 0 的条件和 equals() 不一致,导致集合行为异常——比如两个“逻辑相等”但 equals() 返回 false 的对象,可能同时存在于 TreeSet 中;反之,若 compareTo() 总返回 0,所有元素会被当成同一个 key,只保留一个。
- 必须满足自反性:
a.compareTo(a) == 0 - 必须满足传递性:若
a.compareTo(b) > 0且b.compareTo(c) > 0,则a.compareTo(c) > 0 - 若用
Comparator,建议用Comparator.nullsFirst()或Comparator.nullsLast()显式处理 null,避免NullPointerException
例如:
立即学习“Java免费学习笔记(深入)”;