Java 8 容器源码-TreeSet

昨天已经学习了HashSet，今天开始学习TreeSet。TreeSet是依赖于TreeMap的NavigableSet接口的实现，实际上是个TreeMap的实例。如果对TreeMap源码很熟悉，那么学习TreeSet就会很简单了。TreeSet的特点是使用元素的自然顺序对元素进行排序，或者根据创建set时提供的Comparator进行排序。本文将从数据结构、实现原理、源码等多个方面详细讲解TreeSet。

数据结构

TreeSet是依赖于TreeMap的NavigableSet接口的实现。所以HashSet的数据结构也是红黑树。
这点可以从源码中很清楚地看出来。

                private transient NavigableMap<E,Object> m;
            
                TreeSet(NavigableMap<E,Object> m) {
                    this.m = m;
                }
            
                public TreeSet() {
                    this(new TreeMap<E,Object>());
                }

顶部注释

基于TreeMap的NavigableSet实现。使用元素的自然顺序对元素进行排序，或者根据创建set时提供的Comparator进行排序，具体取决于使用的构造方法。

此实现为基本操作（add、remove和contains）提供受保证的log(n)时间开销。

注意，如果要正确实现Set接口，则set维护的顺序（无论是否提供了显式比较器）必须与equals一致。（关于与equals一致的精确定义，请参阅Comparable或Comparator。）这是因为Set接口是按照equals操作定义的，但TreeSet实例使用它的compareTo（或compare）方法对所有元素进行比较，因此从set的观点来看，此方法认为相等的两个元素就是相等的。即使set的顺序与equals不一致，其行为也是定义良好的；它只是违背了Set接口的常规协定。

注意，此实现不是同步的。如果多个线程同时访问一个TreeSet，而其中至少一个线程修改了该set，那么它必须外部同步。这一般是通过对自然封装该set的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用Collections.synchronizedSortedSet方法来“包装”该set。此操作最好在创建时进行，以防止对set的意外非同步访问：
SortedSet s= Collections.synchronizedSortedSet(new TreeSet(…));

此类的iterator方法返回的迭代器是fail-fast的：在创建迭代器之后，如果从结构上对set进行修改（除非通过迭代器自身的remove方法），否则在其他任何时间以任何方式进行修改都将导致迭代器抛出ConcurrentModificationException。因此，对于并发的修改，迭代器很快就完全失败，而不会冒着在将来不确定的时间发生不确定行为的风险。

注意，迭代器的fail-fast行为无法得到保证，一般来说，存在不同步的并发修改时，不可能作出任何肯定的保证。fail-fast迭代器尽最大努力抛出ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测bug。

此类是Java Collections Framework的成员。

定义

public class TreeSet<E< extends AbstractSet<E&lt implements NavigableSet<E&lt, Cloneable, java.io.Serializable

从中我们可以了解到：

TreeSet：TreeSet支持泛型。
extends AbstractSet：继承了AbstractSet，实现Set接口时需要实现的工作量大大减少了。
implements NavigableSet：实现了NavigableSet，实现具有了为给定搜索目标报告最接近匹配项的导航方法。
implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。
implements Serializable：表明该类是可以序列化的。

下图是HashSet的类结构层次图。

域

                /**
                 * The backing map.
                 */
                private transient NavigableMap<E,Object> m;
            
                /**
                 *  前面讲了，TreeSet是依赖于TreeMap的，底层就是一个TreeMap实例。TreeMap是保存键值对的，但我们保存TreeSet的时候肯定只是想保存key，那么调用hashMap(key,value)时value应该传什么值呢？PRESENT就是要传value。
                 */
                private static final Object PRESENT = new Object();

特别关注的方法

没有需要特别关注的方法。

构造方法

TreeSet一共有5种构造方法：

TreeSet(NavigableMap<E,Object> m)：根据指定的NavigableMap构造一个set。
TreeSet()：构造一个新的空set，该set根据其元素的自然顺序进行排序。
TreeSet(Comparator<? super E> comparator)：构造一个新的空TreeSet，它根据指定比较器进行排序。
TreeSet(Collection<? extends E> c)：构造一个包含指定collection元素的新TreeSet，它按照其元素的自然顺序进行排序。
TreeSet(SortedSet s)：构造一个与指定有序set具有相同映射关系和相同排序的新TreeSet。

其他方法

没什么好讲的，TreeSet的实现完全依赖于TreeMap，几乎没有自己的东西，实现非常简单。如果有兴趣了解可以参考API。

也不作总结了，主要的点都在文章开头和【顶部注释】中。

阅读全文