Java集合-TreeSet

前言

TreeSet 是 Java 集合框架中的一种有序集合类，位于 java.util 包下。它实现了 SortedSet 接口（继承自 Set 接口），底层基于红黑树（Red-Black Tree）实现，能够自动对元素进行排序。TreeSet 的主要特点包括：

元素唯一：不允许重复元素（基于比较结果）。
有序性：元素按照自然顺序（或自定义比较器）排序。
线程不安全：非同步集合，多线程环境下需要外部同步。

TreeSet 底层依赖 TreeMap 实现，它的元素实际上是存储在 TreeMap 的键（key）中，而值（value）是一个固定的占位对象。

源码分析

类定义

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {
    private transient NavigableMap<E,Object> m;
    private static final Object PRESENT = new Object();
}

TreeSet 继承自 AbstractSet，实现 NavigableSet 接口（扩展了 SortedSet，提供导航方法）。
成员变量 m 是一个 NavigableMap 类型的引用，指向底层的 TreeMap。
PRESENT 是一个静态常量，作为 TreeMap 的值占位符，所有元素对应的值都是这个对象。

构造方法

TreeSet 提供了多种构造方法：

// 默认构造，使用元素的自然顺序
public TreeSet() {
    this.m = new TreeMap<>();
}

// 指定比较器的构造
public TreeSet(Comparator<? super E> comparator) {
    this.m = new TreeMap<>(comparator);
}

// 从另一个集合构造
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

默认构造方法创建一个空的 TreeMap，使用元素的自然顺序（需要元素实现 Comparable 接口）。
可以传入自定义 Comparator 来定义排序规则。
从其他集合构造时，会将元素逐个添加到 TreeSet 中。

核心方法

添加元素（add方法）

1
2
3

public boolean add(E e) {
    return m.put(e, PRESENT) == null;
}

add 方法调用 TreeMap 的 put 方法，将元素 e 作为键，PRESENT 作为值插入。
TreeMap 的 put 方法返回旧值，如果返回 null 表示插入成功（元素之前不存在），返回 true。
如果元素已存在，put 返回原来的值（PRESENT），add 返回 false，表示未添加成功。
底层红黑树会根据比较结果调整树结构以保持平衡和排序。

删除元素（remove方法）

1
2
3

public boolean remove(Object o) {
    return m.remove(o) == PRESENT;
}

调用 TreeMap 的 remove 方法删除指定键。
如果删除成功，返回原来的值 PRESENT，方法返回 true；否则返回 null，方法返回 false。

后记

TreeSet 是一个高效的有序集合，底层通过 TreeMap 的红黑树实现，保证了元素的唯一性和排序。源码分析显示其核心操作（如添加、删除）依赖红黑树的平衡调整，时间复杂度稳定在 $O(log n)$。