coding……
但行好事 莫问前程

Java编程拾遗『TreeSet』

上篇文章我们讲了TreeMap的实现,熟悉了TreeMap的一大重要特征——保证键值对之间根据键的有序性。之前在讲HashSet时,我们知道HashSet是通过HashMap实现的。同样的道理,TreeSet其实也是基于TreeMap实现的。TreeSet相比于HashSet,一个突出的特点就是,可以保证元素之间的顺序。TreeSet类继承关系如下:

TreeSet继承了AbstractSet抽象类,可以方便地实现Set接口的基本方法。另外TreeSet实现了NavigableSet接口,NavigableSet接口又继承了SortedSet接口,所以TreeSet可以很方便的获取第一个、最后一个或者某个区间的元素。

1. 使用规则

1.1 TreeSet基本定义

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{

    private transient NavigableMap<E,Object> m;

    private static final Object PRESENT = new Object();

    //methods
}
  • m:用于实现TreeSet的NavigableMap对象,TreeSet可以看做是所有Value都为默认值的一个NavigableMap的key组成的Set
  • PRESENT:TreeSet内部NavigableMap的value默认值

1.2 构造函数

S.N. 方法 说明
1 public TreeSet() 默认构造函数,调用TreeMap的默认构造函数,实例化TreeMap对象赋值给m
2 public TreeSet(Collection<? extends E> c) 通过Collection对象实例化TreeSet,m也是通过TreeMap的默认构造函数构造出来的
3 public TreeSet(Comparator<? super E> comparator) 通过TreeMap(Comparator<? super K> comparator)构造函数构造TreeMap对象赋值给m
4 public TreeSet(SortedSet<E> s) 通过SortedMap对象构造TreeSet

1.3 SortedSet

S.N. 方法 说明
1 Comparator<? super E> comparator() 返回SortedSet集合中元素之间用于比较的Comparator,如果SortedMap内部comparator为null(使用自然排序),返回null
2 E first() 返回SortedSet集合中第一个元素,如果集合为空,抛NoSuchElementException异常
3 E last() 返回SortedSet集合中最后一个元素,如果集合为空,抛NoSuchElementException异常
4 SortedSet<E> headSet(E toElement) 返回SortedSet中小于toElement的所有元素组成的子SortedSet视图,对视图的改变会影响SortedSet的内容
5 SortedSet<E> tailSet(E fromElement) 返回SortedSet大于等于fromElement的所有元素组成的子SortedSet视图,对视图的改变会影响SortedSet的内容
6 SortedSet<E> subSet(E fromElement, E toElement) 返回SortedSet中大于等于fromElement小于toElement的所有元素组成的子SortedSet视图,对视图的改变会影响SortedSet的内容
7 default Spliterator<E> spliterator() Java8新方法,返回SortedSet的Spliterator迭代器

1.4 NavigableSet

S.N. 方法 说明
1 E lower(E e) 返回NavigableSet中严格小于e的最大元素
2 E higher(E e) 返回NavigableSet中严格大于e的最小元素
3 E floor(E e) 返回NavigableSet中小于等于e的最大元素
4 E ceiling(E e) 返回NavigableSet中大于等于e的最小元素
5 NavigableSet<E> descendingSet() 返回NavigableSet所有元素逆序的NavigableSet视图,对视图的改变会影响NavigableSet的内容
6 Iterator<E> descendingIterator() 返回NavigableSet的逆序Iterator迭代器,等效于descendingSet().iterator()
7 Iterator<E> iterator() 返回NavigableSet的正向迭代器
8 E pollFirst() 删除并返回NavigableSet中第一个元素,如果NavigableSet为空,返回null
9 E pollLast() 删除并返回NavigableSet中最后一个元素,如果NavigableSet为空,返回null
10 NavigableSet<E> headSet(E toElement, boolean inclusive) 返回NavigableSet中小于toElement的所有元素组成的子NavigableSet视图,inclusive表示是否包含边界,
对视图的改变会影响SortedMap的内容
10 NavigableSet<E> tailSet(E fromElement, boolean inclusive) 返回NavigableSet中大于fromElement的所有元素组成的子NavigableSet视图,inclusive表示是否包含边界,
对视图的改变会影响SortedMap的内容
11 NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive)
返回NavigableSet中大于fromElement小于toElement的所有元素组成的子NavigableSet视图,
fromInclusive、toInclusive表示是否包含边界,对视图的改变会影响SortedMap的内容

1.5 Set

S.N. 方法 说明
1 boolean add(E e) 向Set中添加一个元素
2 boolean addAll(Collection<? extends E> c) 将Collection中的元素添加到Set中
3 boolean contains(Object o) 判断Set中是否包含o元素
4 boolean containsAll(Collection<?> c) 判断Collection中的元素是否全部存在于Set中
5 boolean equals(Object o) equals方法
6 int hashCode() hashCode方法
7 boolean isEmpty() 判断Set是否为空
8 Iterator<E> iterator() 返回Set的单向Iterator迭代器
9 boolean remove(Object o) 删除Set中的元素o
10 boolean removeAll(Collection<?> c) 删除Set中包含的Collection的所有元素,如果c也为Set,表示求差集
11 boolean retainAll(Collection<?> c) 保留Set中包含的Collection的所有元素,如果c也为Set,表示求交集
12 int size() 返回Set元素个数
13 default Spliterator<E> spliterator() 返回Set的并行流Spliterator迭代器
14 Object[] toArray() Set转Object[]数组
15 <T> T[] toArray(T[] a) Set转特定类型数组

2. 实现源码分析

2.1 构造函数

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

默认构造函数调用了另一个构造函数,传入的参数为调用TreeMap的默认构造函数创建的一个TreeMap对象(实例化得到的TreeMap comparator为null),该情形下要求TreeSet中的元素实现了Comparable接口。

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

该构造函数的访问权限为包访问权限,将上述TreeMap赋值给TreeSet内部的成员变量m。

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

该构造函数通过Collection对象实例化TreeSet,实现也比较简单,就是调用上述无参构造函数,对成员变量m赋值为一个空的TreeMap,然后调用addAll方法,将Collection中所有的元素添加到m中,从而达到实例化TreeSet的效果,该情形下也要求Collection中的元素实现了Comparable接口。

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

这种形式的构造函数,通过Comparator对象初始化TreeSet,其实就是调用TreeMap的TreeMap(Comparator<? super K> comparator)构造函数得到一个TreeMap对象,并将该对象赋值给TreeSet内部成员变量m。

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

这种形式的构造函数,通过SortedSet对象初始化TreeSet,就是调用上述TreeSet(Comparator<? super E> comparator)构造函数,对内部成员变量m赋值后,调用addAll方法,将SortedSet中所有的元素通过调用addAll方法添加到m中。

2.2 boolean add(E e)

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

就是调用TreeMap的put方法,e为TreeMap键值对的key,键值对值为静态Object常量PRESENT,put返回null表示原来没有对应的键,添加成功了。

2.3 boolean remove(Object o)

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

就是调用TreeMap的remove方法,返回值为PRESENT表示原来有对应的键且删除成功了。

2.4 boolean contains(Object o)

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

就是调用TreeMap的containsKey方法,判断TreeMap中是否包含对应的键。

2.5 NavigableSet<E> subSet

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

调用TreeMap的subMap方法获取TreeMap的子视图,然后调用TreeSet的构造函数初始化TreeSet。TreeMap的subMap方法的返回值是一个NavigableMap对象,该对象内部的红黑树其实跟原TreeMap内部的红黑树共享同一片内存空间,所以subMap方法返回的是原TreeMap的一个子视图,对视图的修改会同步影响到原TreeMap。调用TreeSet的构造函数,将subMap方法返回的NavigableMap对象作为参数传入,所以subSet是整个TreeSet的子视图

通过以上方法可以发现,其实TreeSet跟HashSet一样,实现都比较简单。HashSet主要通过调用HashMap的方法来实现,TreeSet主要是通过调用NavigableMap的方法来实现。

 3. TreeSet特点

TreeSet内部是通过TreeMap实现的,所以也可以讲TreeSet底层是通过红黑树实现的。TreeSet有以下特点:

  • TreeSet实现了Set接口,具有Set的一切特性,比如不存在重复元素
  • TreeSet相比于HashSet,元素之间是有序的,由于TreeSet实现了NavigableSet接口,所以可以很方便的操作第一个、最后一个或一定范围内的元素
  • TreeSet是基于TreeMap实现的,所以添加、删除、判断元素是否存在,效率比较高,时间复杂度为为O(logN)

参考链接:

  1. Java API源码
  2. 《Java编程的逻辑》

赞(0) 打赏
Zhuoli's Blog » Java编程拾遗『TreeSet』
分享到: 更多 (0)

评论 抢沙发

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

zhuoli's blog

联系我关于我

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

支付宝扫一扫打赏

微信扫一扫打赏