Java 8 容器源码-TreeSet

撸了今年阿里、腾讯和美团的面试,我有一个重要发现…….

作者:潘威威
出处:https://blog.csdn.net/panweiwei1994


昨天已经学习了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的类结构层次图。

MarkdownPhotos/master/CSDNBlogs/container/TreeSet/TreeSetTH.jpg

    /**
     * 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种构造方法:

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

其他方法

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

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

赞(1) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » Java 8 容器源码-TreeSet
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏