Java编程拾遗『TreeSet』

上篇文章我们讲了TreeMap的实现，熟悉了TreeMap的一大重要特征——保证键值对之间根据键的有序性。之前在讲HashSet时，我们知道HashSet是通过HashMap实现的。同样的道理，TreeSet其实也是基于TreeMap实现的。TreeSet相比于HashSet，一个突出的特点就是，可以保证元素之间的顺序。TreeSet类继承关系如下：

TreeSet继承了AbstractSet抽象类，可以方便地实现Set接口的基本方法。另外TreeSet实现了NavigableSet接口，NavigableSet接口又继承了SortedSet接口，所以TreeSet可以很方便的获取第一个、最后一个或者某个区间的元素。

1. 使用规则

1.1 TreeSet基本定义

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();

    //methods
}

• m：用于实现TreeSet的NavigableMap对象，TreeSet可以看做是所有Value都为默认值的一个NavigableMap的key组成的Set
• PRESENT：TreeSet内部NavigableMap的value默认值

1.2 构造函数

1.3 SortedSet

1.4 NavigableSet

1.5 Set

2. 实现源码分析

2.1 构造函数

public TreeSet() {
    this(new TreeMap<E,Object>());
}

默认构造函数调用了另一个构造函数，传入的参数为调用TreeMap的默认构造函数创建的一个TreeMap对象（实例化得到的TreeMap comparator为null），该情形下要求TreeSet中的元素实现了Comparable接口。

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

该构造函数的访问权限为包访问权限，将上述TreeMap赋值给TreeSet内部的成员变量m。

public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

该构造函数通过Collection对象实例化TreeSet，实现也比较简单，就是调用上述无参构造函数，对成员变量m赋值为一个空的TreeMap，然后调用addAll方法，将Collection中所有的元素添加到m中，从而达到实例化TreeSet的效果，该情形下也要求Collection中的元素实现了Comparable接口。

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

这种形式的构造函数，通过Comparator对象初始化TreeSet，其实就是调用TreeMap的TreeMap(Comparator<? super K> comparator)构造函数得到一个TreeMap对象，并将该对象赋值给TreeSet内部成员变量m。

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

这种形式的构造函数，通过SortedSet对象初始化TreeSet，就是调用上述TreeSet(Comparator<? super E> comparator)构造函数，对内部成员变量m赋值后，调用addAll方法，将SortedSet中所有的元素通过调用addAll方法添加到m中。

2.2 boolean add(E e)

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

就是调用TreeMap的put方法，e为TreeMap键值对的key，键值对值为静态Object常量PRESENT，put返回null表示原来没有对应的键，添加成功了。

2.3 boolean remove(Object o)

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

就是调用TreeMap的remove方法，返回值为PRESENT表示原来有对应的键且删除成功了。

2.4 boolean contains(Object o)

public boolean contains(Object o) {
    return m.containsKey(o);
}

就是调用TreeMap的containsKey方法，判断TreeMap中是否包含对应的键。

2.5 NavigableSet<E> subSet

public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                              E toElement,   boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                   toElement,   toInclusive));
}

调用TreeMap的subMap方法获取TreeMap的子视图，然后调用TreeSet的构造函数初始化TreeSet。TreeMap的subMap方法的返回值是一个NavigableMap对象，该对象内部的红黑树其实跟原TreeMap内部的红黑树共享同一片内存空间，所以subMap方法返回的是原TreeMap的一个子视图，对视图的修改会同步影响到原TreeMap。调用TreeSet的构造函数，将subMap方法返回的NavigableMap对象作为参数传入，所以subSet是整个TreeSet的子视图。

通过以上方法可以发现，其实TreeSet跟HashSet一样，实现都比较简单。HashSet主要通过调用HashMap的方法来实现，TreeSet主要是通过调用NavigableMap的方法来实现。

 3. TreeSet特点

TreeSet内部是通过TreeMap实现的，所以也可以讲TreeSet底层是通过红黑树实现的。TreeSet有以下特点：

• TreeSet实现了Set接口，具有Set的一切特性，比如不存在重复元素
• TreeSet相比于HashSet，元素之间是有序的，由于TreeSet实现了NavigableSet接口，所以可以很方便的操作第一个、最后一个或一定范围内的元素
• TreeSet是基于TreeMap实现的，所以添加、删除、判断元素是否存在，效率比较高，时间复杂度为为O(logN)

参考链接：

1. Java API源码
2. 《Java编程的逻辑》