close

Mr.Muzi

一只很安静的monkey

Java Collection 13 - TreeSet

字数统计: 2.7k 阅读时长: 12 mins • 分类: 源码阅读 • 标签: JDK 1.7, Java集合

  关于 java.util.TreeSet<E> 的部分笔记，TreeSet是一个有序的、不可存储重复元素的Set集合实现类。TreeSet集合的顺序由Comparable实现或者Comparator指定。本文演示代码段的执行环境基于JDK版本1.7。

概述

  TreeSet是一个基于TreeMap的Set集合实现，继承了AbstractSet的同时实现了NavigableSet接口（该接口直接继承于SortedSet）中声明的方法操作。集合内的元素按照实现了Comparable接口的自然顺序进行排序，或者由Comparator指定一个排序顺序。TreeSet实现保证在调用add(E e)、remove(Object o) 、contains(Object o)方法时可以得到log(n)的时间性能。

  和LinkedHashSet不一致的是，TreeSet维护的顺序是基于元素内容的，按照事先定义好的比较规则比较插入TreeSet集合的每一个元素，因此在元素插入后，集合的顺序可能会随之发生变更。而LinkedHashSet维护的元素插入的顺序，这个顺序为固定的，只与元素被加入集合时的时间有关系。

  TreeSet集合也是一个非线程安全的集合实现类。如果需要在多线程环境中使用TreeSet集合，那么需要对TreeSet集合做额外的处理来保证其多线程环境下的线程安全。一种常见的处理方式是：

1
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

该处理需要在TreeSet初始化的同时就完成，避免因为多线程环境下使用时出现问题。

  TreeSet返回的迭代器也支持快速失败检查。

 

继承关系

1
2
3
4
5
// TreeSet<E>
--java.lang.Object
  --java.util.AbstractCollection<E>
    --java.util.AbstractSet<E>
      --java.util.TreeSet<E>

 

实现接口

类名 实现接口
TreeSet<E> Iterable<E>, Collection<E>, NavigableSet<E>, Set<E>, SortedSet<E>, Serializable, Cloneable

 

TreeSet

Constructor Summary

TreeSet(NavigableMap<E,Object> m)

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

  根据入参NavigableMap构建一个TreeSet集合。m集合会成为TreeSet集合的底层依赖集合实例。

public TreeSet()

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

  初始化一个空的TreeSet集合，集合排序按照元素的自然排序进行处理。

public TreeSet(Comparator<? super E> comparator)

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

  初始化一个空的TreeSet集合，集合排序按照comparator规则进行处理。

public TreeSet(Collection<? extends E> c)

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

  初始化一个空的TreeSet集合，并将集合c的所有元素加入到集合中。集合排序按照元素的自然排序规则进行处理。底层通过调用addAll(Collection<? extends E> c) 完成元素添加操作。

public TreeSet(SortedSet<E> s)

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

  初始化一个空的TreeSet集合，并将SortedSet集合s的所有元素加入到集合中。集合排序按照s的排序规则进行处理。底层通过调用addAll(Collection<? extends E> c) 完成元素添加操作。

部分方法

public Iterator<E> iterator()

1
2
3
public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}

  返回一个遍历当前TreeSet集合的迭代器，迭代器按照升序方式进行遍历迭代。底层调用NavigableMap.navigableKeySet().iterator()完成操作。

public Iterator<E> descendingIterator()

1
2
3
public Iterator<E> descendingIterator() {
    return m.descendingKeySet().iterator();
}

  返回一个遍历当前TreeSet集合的迭代器，迭代器按照降序方式进行遍历迭代。底层调用NavigableMap.descendingKeySet().iterator()完成操作。

public NavigableSet<E> descendingSet()

1
2
3
public NavigableSet<E> descendingSet() {
    return new TreeSet<>(m.descendingMap());
}

  返回当前集合的一个逆序集合表示。对该集合的修改会同步到原始集合上，反之亦然

public int size()

1
2
3
public int size() {
    return m.size();
}

  返回当前TreeSet集合存储的元素总数。

public boolean isEmpty()

1
2
3
public boolean isEmpty() {
    return m.isEmpty();
}

  判断当前TreeSet集合是否为空。

public boolean contains(Object o)

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

  判断当前TreeSet集合是否存储了元素o。如果有则返回true，反之返回false。

public boolean add(E e)

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

  将元素e加入到当前TreeSet集合中。

public boolean remove(Object o)

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

  从当前TreeSet集合中移除元素o。移除成功后返回true，表示集合中的元素o已经被移除掉。

public void clear()

1
2
3
public void clear() {
    m.clear();
}

  清空当前TreeSet集合中的所有元素。

public boolean addAll(Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public  boolean addAll(Collection<? extends E> c) {
    // Use linear-time version if applicable
    if (m.size()==0 && c.size() > 0 &&
        c instanceof SortedSet &&
        m instanceof TreeMap) {
        SortedSet<? extends E> set = (SortedSet<? extends E>) c;
        TreeMap<E,Object> map = (TreeMap<E, Object>) m;
        Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
        Comparator<? super E> mc = map.comparator();
        if (cc==mc || (cc != null && cc.equals(mc))) {
            map.addAllForTreeSet(set, PRESENT);
            return true;
        }
    }
    return super.addAll(c);
}

  将集合c中的元素加入到当前TreeSet集合中。如果当前TreeSet集合尚未存储任何元素，那么就执行第3 ~ 14行代码的操作，反之，则直接执行第15行代码。第11行代码的方法API是专门为TreeSet集合实现的，该方法可以保证大量元素插入的性能效率。所以如果满足采用优化操作插入元素的条件，那么就采用快速方法完成元素插入。否则就只有用AbstractCollection的addAll(Collection<? extends E> c)方法完成操作，而该方法将元素一个一个的加入到集合中，性能相对来说不是很理想。

public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

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

  返回一个以fromElement为起点，toElement为终点的子集合。由fromInclusive和toInclusive字段标记是否包含fromElement和toElement节点。对该集合的修改会同步到原始集合上，反之亦然。

public NavigableSet<E> headSet(E toElement, boolean inclusive)

1
2
3
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<>(m.headMap(toElement, inclusive));
}

  返回一个小于（等于）toElement元素的子集合。由inclusive指定是否可以返回等于toElement元素的元素。对该集合的修改会同步到原始集合上，反之亦然。

public NavigableSet<E> tailSet(E fromElement, boolean inclusive)

1
2
3
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
    return new TreeSet<>(m.tailMap(fromElement, inclusive));
}

  返回一个大于（等于）fromElement元素的子集合。由inclusive指定是否可以返回等于fromElement元素的元素。对该集合的修改会同步到原始集合上，反之亦然。

public SortedSet<E > subSet(E fromElement, E toElement)

1
2
3
public SortedSet<E> subSet(E fromElement, E toElement) {
    return subSet(fromElement, true, toElement, false);
}

  返回一个以fromElement为起点（包含fromElement），toElement为终点（不包含toElement）的子集合。对该集合的修改会同步到原始集合上，反之亦然。

public SortedSet<E> headSet(E toElement)

1
2
3
public SortedSet<E> headSet(E toElement) {
    return headSet(toElement, false);
}

 返回一个小于toElement元素的子集合。对该集合的修改会同步到原始集合上，反之亦然。 

public SortedSet<E> tailSet(E fromElement)

1
2
3
public SortedSet<E> tailSet(E fromElement) {
    return tailSet(fromElement, true);
}

  返回一个大于fromElement元素的子集合。对该集合的修改会同步到原始集合上，反之亦然。

public Comparator<? super E> comparator()

1
2
3
public Comparator<? super E> comparator() {
    return m.comparator();
}

  返回当前集合采用的比较器。如果当前TreeSet集合采用的自然排序，那么返回null。

public E first()

1
2
3
public E first() {
    return m.firstKey();
}

  返回当前集合中第一个（也是最小）的元素。如果集合为空则抛出NoSuchElementException异常。

public E last()

1
2
3
public E last() {
    return m.lastKey();
}

  返回当前集合中最后（也是最大）的元素。如果集合为空则抛出NoSuchElementException异常。

public E lower(E e)

1
2
3
public E lower(E e) {
    return m.lowerKey(e);
}

  返回小于元素e的最大元素，如果没有返回null。

public E floor(E e)

1
2
3
public E floor(E e) {
    return m.floorKey(e);
}

  返回小于或者等于元素e的最大元素，如果没有返回null。

public E ceiling(E e)

1
2
3
public E ceiling(E e) {
    return m.ceilingKey(e);
}

  返回大于或者等于元素e的最小元素，如果没有返回null。

public E higher(E e)

1
2
3
public E higher(E e) {
    return m.higherKey(e);
}

  返回大于元素e的最小元素，如果没有返回null。

public E pollFirst()

1
2
3
4
public E pollFirst() {
    Map.Entry<E,?> e = m.pollFirstEntry();
    return (e == null) ? null : e.getKey();
}

  移除并返回集合中的最小（第一个）元素，如果集合为空返回null。该方法是在JDK1.6版本中加入的。

public E pollLast()

1
2
3
4
public E pollLast() {
    Map.Entry<E,?> e = m.pollLastEntry();
    return (e == null) ? null : e.getKey();
}

  移除并返回集合中的最大（最后一个）元素，如果集合为空返回null。该方法是在JDK1.6版本中加入的。

public Object clone()

1
2
3
4
5
6
7
8
9
10
11
public Object clone() {
    TreeSet<E> clone = null;
    try {
        clone = (TreeSet<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError();
    }

    clone.m = new TreeMap<>(m);
    return clone;
}

  返回当前TreeSet集合的一个浅复制实例。在复制过程中，集合中的元素不会被复制，而是先把集合复制出来，之后单独完成集合内元素的赋值操作。

private void writeObject(java.io.ObjectOutputStream s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
    // Write out any hidden stuff
    s.defaultWriteObject();

    // Write out Comparator
    s.writeObject(m.comparator());

    // Write out size
    s.writeInt(m.size());

    // Write out all elements in the proper order.
    for (E e : m.keySet())
        s.writeObject(e);
}

  将当前TreeSet集合执行序列化操作后保存到流中。在执行TreeSet的序列化操作时采用TreeSet自己实现的序列化方法完成操作。

private void readObject(java.io.ObjectInputStream s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden stuff
    s.defaultReadObject();

    // Read in Comparator
    Comparator<? super E> c = (Comparator<? super E>) s.readObject();

    // Create backing TreeMap
    TreeMap<E,Object> tm;
    if (c==null)
        tm = new TreeMap<>();
    else
        tm = new TreeMap<>(c);
    m = tm;

    // Read in size
    int size = s.readInt();

    tm.readTreeSet(size, s, PRESENT);
}

  从流中读取处序列化数据并执行反序列操作在内存中生成一个TreeSet集合实例。在执行TreeSet的反序列化操作时采用TreeSet自己实现的反序列化方法完成操作。

 

涉及基础知识点

  1. NIL

 

参考文献

  1. Lirx_Tech. [疯狂Java]集合：SortedSet、TreeSet [E]

 
 
 
 

------------- End of this article, thanks! -------------
 


  版权声明：本文由N.C.Lee创作和发表，采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可，转载请注明作者及出处。
  本文作者为 N.C.Lee
  本文标题为 Java Collection 13 - TreeSet
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-TreeSet.html