Java Collection 13 - TreeSet

  关于 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! -------------


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