概述

TreeSet是Java集合框架中用于存储唯一元素的树形数据结构，它实现了NavigableSet接口，这意味着TreeSet中的元素不仅是有序的，还支持一系列的导航方法。

TreeSet的内部实现主要依赖于TreeMap，通过TreeMap的键来维护元素的排序。 

类图

从以上类图可以看到，TreeSet 实现了三个接口，继承了一个抽象类：

• NavigableSet接口，提供了强大、灵活的排序与导航功能
• Serializable接口，表示TreeSet支持序列化功能
• Cloneable接口，表示TreeSet支持克隆
• AbstractSet抽象类，主要提供元素对比、删除等操作

源码解读

成员变量

// 底层依赖TreeMap（TreeMap实现了NavigableMap接口）
private transient NavigableMap<E,Object> m;

// 同HashSet，value使用统一占位符对象
// value没有用到为啥不直接用null，因为底层TreeMap插入、移除元素会返回当前元素。如果这里使用null值，就无法判断是否插入、移除成功
private static final Object PRESENT = new Object();

构造方法

TreeSet 中提供了四种构造方案：

• public TreeSet()默认构造函数
• public TreeSet(Comparator<? super E> comparator)创建一个自定义比较器的TreeSet集合
• public TreeSet(Collection<? extends E> c)创建一个包含集合c中所有元素的TreeSet集合
• public TreeSet(SortedSet<E> s)创建一个包含SortedSet集合s中所有元素的TreeSet集合，且会复用s的比较器

添加元素

TreeSet的添加元素操作是通过调用TreeMap的put方法实现的。

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

与HashSet类似，如果元素不存在于TreeMap中，put方法会返回null，表示添加成功；如果元素已存在，则返回旧值（在这种情况下是PRESENT），表示添加失败。

删除元素

TreeSet的删除元素操作是通过调用TreeMap的remove方法实现的。

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

如果成功删除了元素，remove方法会返回PRESENT；否则返回null。

获取元素

TreeSet的获取元素操作是通过调用TreeMap方法实现的，获取TreeMap key即TreeSet的元素。

// 返回第一个元素
public E first() {
    return m.firstKey();
}
// 返回最后一个元素
public E last() {
    return m.lastKey();
}
// 返回set中小于e的最大的元素
public E lower(E e) {
    return m.lowerKey(e);
}
// 返回set中小于/等于e的最大元素
public E floor(E e) {
    return m.floorKey(e);
}
// 返回set中大于/等于e的最大元素
public E ceiling(E e) {
    return m.ceilingKey(e);
}
// 返回set中大于e的最小元素
public E higher(E e) {
    return m.higherKey(e);
}

遍历元素

TreeSet的遍历元素操作是通过调用TreeMap方法实现的。升序遍历（iterator方法）、降序遍历（descendingIterator方法）。

// 升序遍历
public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}
// 降序遍历
public Iterator<E> descendingIterator() {
    return m.descendingKeySet().iterator();
}

出栈元素

TreeSet的出栈元素操作是通过调用TreeMap方法实现的。头结点出栈（pollFirst方法）、尾结点出栈（pollLast方法）。

// 获取TreeSet中第一个元素，并从Set中删除该元素
public E pollFirst() {
    Map.Entry<E,?> e = m.pollFirstEntry();
    return (e == null) ? null : e.getKey();
}
// 获取TreeSet中最后一个元素，并从Set中删除该元素
public E pollLast() {
    Map.Entry<E,?> e = m.pollLastEntry();
    return (e == null) ? null : e.getKey();
}

总结

通过以上的源码分析，可以看到TreeSet的底层实现主要依赖于TreeMap。TreeSet利用TreeMap的键来存储元素，并通过TreeMap的排序特性保证了元素的自然排序或自定义排序。