欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java集合----TreeSet

程序员文章站 2022-05-14 13:29:18
...

一.前言

TreeSet 是java 集合中 Set 分支下的一个集合,其存储的元素会根据 key 的大小进行排序,下面就看看 TreeSet 的具体实现。

二.分析

1.简介

下面引用自源码的注释翻译

TreeSet 是基于 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 方法返回的迭代器是快速失败 的:在创建迭代器之后,如果从结构上对 set 进行修改,除非通过迭代器自身的 remove 方法,否则在其他任何时间以任何方式进行修改都将导致迭代器抛出 ConcurrentModificationException。因此,对于并发的修改,迭代器很快就完全失败,而不会冒着在将来不确定的时间发生不确定行为的风险。

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

总结如下:

  • TreeSet 的内部实现是通过 TreeMap 来支持的
  • TreeSet 的查找添加删除等操作的时间复杂度都是 O(logn)
  • TreeSet 的比较是通过 compare 或者 compareTo 来判断的或者排序的
  • TreeSet 不是线程安全的,如果需要同步可以需要 synchronizedSortedSet 进行同步的包装。
  • TreeSet 的迭代器采用的快速失败的机制,也就是说如果生成了一个迭代器,如果这个时候对集合进行了修改,迭代器就会失效,除非是迭代器的 remove 方法。
2.变量
    //提供支持的 map
    private transient NavigableMap<E,Object> m;
    //因为内部的实现是一个 Map , 所以就需要一个
    //虚拟的 value 作为所有的 key 的  value
    private static final Object PRESENT = new Object();

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

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

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

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

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

从上面的构造器中可以看出,对于普通的 TreeSet ,最后都是交由 TreeMap 去实现。

4.增删该查
    public int size() {
        return m.size();
    }

   
    public boolean isEmpty() {
        return m.isEmpty();
    }

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

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

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

   
    public void clear() {
        m.clear();
    }

可以看到所有的实现,最后都对应着 TreeMap 的实现,
详细可以看这篇 java集合----TreeMap,这里就不做重复地分析了。

相关标签: TreeSet