Java集合框架中的TreeSet与TreeMap实现_技术教程

TreeSet底层基于TreeMap实现，所有操作委托给TreeMap，使用PRESENT占位符，排序、去重、O(log n)复杂度均继承自TreeMap，不存null且依赖Comparable或Comparator。

TreeSet底层就是用TreeMap实现的

TreeSet本身不存储元素，它把所有操作都委托给内部封装的TreeMap实例。当你调用treeSet.add(e)，实际执行的是map.put(e, PRESENT)，其中PRESENT是一个

共享的静态Object占位符。这意味着TreeSet的排序、去重、时间复杂度（O(log n)）全部继承自TreeMap。

常见误解是认为两者各自独立实现红黑树逻辑——其实TreeSet连节点类都不定义，完全复用TreeMap.Entry结构。这也是为什么TreeSet无法存null（除非使用Comparator且明确允许）：因为TreeMap的put方法在键为null时会直接抛NullPointerException（JDK 8+）。

TreeMap的key必须可比较，否则运行时报错

如果构造TreeMap时不传Comparator，它会要求key类型实现Comparable接口，并在插入时调用key.compareTo(otherKey)。一旦某个key为null，或两个key的compareTo返回值不满足自反性/传递性，就会在第一次put或get时触发ClassCastException或NullPointerException。

错误示例：

TreeMap map = new TreeMap<>();
map.put(new StringBuffer("a"), 1); // 运行时报 ClassCastException

正确做法：要么让key类实现Comparable，要么显式传Comparator，例如
```
TreeMap map = new TreeMap<>((a, b) -> a.toString().compareTo(b.toString()));
```
注意：Comparator不能为null，否则构造时就抛NullPointerException

TreeSet与TreeMap的迭代顺序完全一致，但遍历方式不同

两者都按key的自然序（或指定Comparator）升序排列，底层共用同一套红黑树遍历逻辑。但暴露给用户的API不同：

TreeSet.iterator()返回Iterator，直接遍历元素值
TreeMap.keySet().iterator()也返回Iterator，效果等价；但若要同时访问key和value，必须用entrySet().iterator()
性能上无差异：两者迭代都是O(n)时间、O(1)额外空间，且顺序严格保证
陷阱：TreeSet没有get方法，想查某个元素是否存在只能用contains（本质是TreeMap.containsKey）

自定义Comparator时，equals和hashCode不参与排序判断

TreeMap和TreeSet只依赖Comparator.compare()或Comparable.compareTo()的结果，完全忽略equals和hashCode。这意味着：

两个逻辑上equals的对象，只要compare返回非零，就会被当作不同key存入TreeMap，或同时加入TreeSet
反之，若compare返回0，即使equals返回false，也会被视为重复而拒绝插入
典型坑：用Double作key时，new Double(0.0)和new Double(-0.0)的equals为true，但若用默认Double.compareTo，它们比较结果为0，会被视为同一key；而若用Comparator.comparingDouble(d -> d)，行为相同；但若误用Comparator.comparing(Object::toString)，则可能因字符串表示不同而拆成两个key