(44) 剖析TreeSet / 计算机程序的思维逻辑

41节介绍了HashSet,我们提到,HashSet有一个重要局限,元素之间没有特定的顺序,我们还提到,Set接口还有另一个重要的实现类TreeSet,它是有序的,与HashSet和HashMap的关系一样,TreeSet是基于TreeMap的,上节我们介绍了TreeMap,本节我们来详细讨论TreeSet。

下面,我们先来看TreeSet的用法,然后看实现原理,最后总结分析TreeSet的特点。

基本用法

构造方法

TreeSet的基本构造方法有两个:

public TreeSet()
public TreeSet(Comparator<? super E> comparator)

默认构造方法假定元素实现了Comparable接口,第二个使用传入的比较器,不要求元素实现Comparable。

基本例子

TreeSet经常也只是当做Set使用,只是希望迭代输出有序,如下面代码所示:

Set<String> words = new TreeSet<String>();
words.addAll(Arrays.asList(new String[]{
    "tree", "map", "hash", "map",     
}));
for(String w : words){
    System.out.print(w+" ");
}

输出为:

hash map tree 

TreeSet实现了两点:排重和有序。

如果希望不同的排序,可以传递一个Comparator,如下所示:

Set<String> words = new TreeSet<String>(new Comparator<String>(){

    @Override
    public int compare(String o1, String o2) {
        return o1.compareToIgnoreCase(o2);
    }});
words.addAll(Arrays.asList(new String[]{
    "tree", "map", "hash", "Map",     
}));
System.out.println(words);

忽略大小写进行比较,输出为:

[hash, map, tree]

需要注意的是,Set是排重的,排重是基于比较结果的,结果为0即视为相同,"map"和"Map"虽然不同,但比较结果为0,所以只会保留第一个元素。

以上就是TreeSet的基本用法,简单易用。不过,因为有序,TreeSet还实现了NavigableSet和SortedSet接口,NavigableSet扩展了SortedSet,此外,TreeSet还有几个构造方法,我们来看下。

高级用法

SortedSet接口

SortedSet接口与SortedMap接口类似,具体定义为:

public interface SortedSet<E> extends Set<E> {
    Comparator<? super E> comparator();
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
    E first();
    E last();

first()返回第一个元素,last()返回最后一个,headSet/tailSet/subSet都返回一个视图,包括原Set中的一定取值范围的元素,区别在于范围:

  • headSet:严格小于toElement的所有元素
  • tailSet: 大于等于fromElement的所有元素
  • subSet: 大于等于fromElement,且小于toElement的所有元素

与之前介绍的视图概念一样,对返回视图的操作会直接影响原Set。

comparator()返回使用的比较器,如果没有自定义的比较器,返回值为null。

我们来看一段简单的示例代码,以增强直观感受,输出用注释说明:

SortedSet<String> set = new TreeSet<String>();
set.addAll(Arrays.asList(new String[]{
    "c", "a", "b", "d","f"    
}));

System.out.println(set.first()); //a
System.out.println(set.last()); //f
System.out.println(set.headSet("b"));//[a]
System.out.println(set.tailSet("d"));//[d, f]
System.out.println(set.subSet("b", "e")); //[b, c, d]
set.subSet("b", "e").clear(); //会从原set中删除
System.out.println(set); //[a, f]

NavigableSet接口

与NavigableMap类似,NavigableSet接口扩展了SortedSet,主要增加了一些查找邻近元素的方法,比如:

E floor(E e); //返回小于等于e的最大元素
E lower(E e); // 返回小于e的最大元素
E ceiling(E e); //返回大于等于e的最小元素
E higher(E e); //返回大于e的最小元素

相比SortedSet中的视图方法,NavigableSet增加了一些方法,以更为明确的方式指定返回值中是否包含边界值,如:

NavigableSet<E> headSet(E toElement, boolean inclusive);
NavigableSet<E> tailSet(E fromElement, boolean inclusive);
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);

NavigableSet也增加了两个对头尾的操作:

E pollFirst(); //返回并删除第一个元素
E pollLast(); //返回并删除最后一个元素

此外,NavigableSet还有如下方法,以方便逆序访问:

NavigableSet<E> descendingSet();
Iterator<E> descendingIterator();

我们来看一段简单的示例代码,以增强直观感受,输出用注释说明:

NavigableSet<String> set = new TreeSet<String>();
set.addAll(Arrays.asList(new String[]{
    "c", "a", "b", "d","f"    
}));
System.out.println(set.floor("a")); //a
System.out.println(set.lower("b")); //a
System.out.println(set.ceiling("d"));//d
System.out.println(set.higher("c"));//d
System.out.println(set.subSet("b", true, "d", true)); //[b, c, d]
System.out.println(set.pollFirst()); //a
System.out.println(set.pollLast()); //f
System.out.println(set.descendingSet()); //[d, c, b]

其他构造方法

TreeSet的其他构造方法为:

public TreeSet(Collection<? extends E> c)
public TreeSet(SortedSet<E> s)
TreeSet(NavigableMap<E,Object> m) 

前两个都是以一个已有的集合为参数,将其中的所有元素添加到当前TreeSet,区别在于,在第一个中,比较器为null,假定元素实现了Comparable接口,而第二个中,比较器设为和参数SortedSet中的一样。

第三个不是public的,是内部用的。

基本实现原理

41节介绍过,HashSet是基于HashMap实现的,元素就是HashMap中的键,值是一个固定的值,TreeSet是类似的,它是基于TreeMap实现的,我们具体来看一下代码,先看其内部组成。

内部组成

TreeSet的内部有如下成员:

private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();

m就是背后的那个TreeMap,这里用的是更为通用的接口类型NavigableMap,PRESENT就是那个固定的共享值。

TreeSet的方法实现主要就是调用m的方法,我们具体来看下。

构造方法

几个构造方法的代码为:

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

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

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);
}

代码都比较简单,就不解释了。

添加元素

add方法的代码为:

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

就是调用map的put方法,元素e用作键,值就是固定值PRESENT,put返回null表示原来没有对应的键,添加成功了。

检查是否包含元素

代码为:

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

就是检查map中是否包含对应的键。

删除元素

代码为:

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

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

子集视图

subSet方法的代码:

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

先调用subMap方法获取NavigatebleMap的子集,然后调用内部的TreeSet构造方法。

头尾操作

代码为:

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

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



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

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

代码都比较简单,就不解释了。

逆序遍历

代码为:

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

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

也很简单。

实现原理小结

TreeSet的实现代码都比较简单,主要就是调用内部NavigatableMap的方法。

TreeSet特点分析

与HashSet相比,TreeSet同样实现了Set接口,但内部基于TreeMap实现,而TreeMap基于大致平衡的排序二叉树 - 红黑树,这决定了它有如下特点:

  • 没有重复元素
  • 添加、删除元素、判断元素是否存在,效率比较高,为O(log2(N)),N为元素个数。
  • 有序,TreeSet同样实现了SortedSet和NavigatableSet接口,可以方便的根据顺序进行查找和操作,如第一个、最后一个、某一取值范围、某一值的邻近元素等。
  • 为了有序,TreeSet要求元素实现Comparable接口或通过构造方法提供一个Comparator对象。

小结

本节介绍了TreeSet的用法和实现原理,在用法方面,它实现了Set接口,但有序,同样实现了SortedSet和NavigatableSet接口,在内部实现上,它使用了TreeMap,代码比较简单。

至此,我们已经介绍完了Java中主要常见的容器接口和实现类,接口主要有队列(Queue),双端队列(Deque),列表(List),Map和Set,实现类有ArrayList, LinkedList, HashMap, TreeMap, HashSet和TreeSet。

关于接口Queue, Deque, Map和Set,Java容器类中还有其他一些实现类,它们各有特点,让我们在接下来的几节中继续探索。

原文发布于微信公众号 - 老马说编程(laoma_shuo)

原文发表时间:2016-10-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏好好学java的技术栈

”365算法每日学计划”:02打卡-线性表(赠书活动第①期预告)

1293
来自专栏用户画像

剑指offer 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

912
来自专栏开发之途

Java集合框架源码解析之LinkedList

1273
来自专栏电光石火

HashSet

HashSet类,是存在于java.util包中的类。同时也被称为集合,该容器中只能存储不重复的对象 方法摘要 boolean add(E e) 如...

1965
来自专栏nnngu

算法06 五大查找之:二分查找

二分查找属于顺序表查找,二分查找也称为折半查找。二分查找的时间复杂度为O(log2n)   1、二分查找的定义 什么是二分查找呢?二分查找的基本思想是:在有序表...

3448
来自专栏云霄雨霁

查找----基于二叉查找树

1110
来自专栏老马说编程

(38) 剖析ArrayList / 计算机程序的思维逻辑

从本节开始,我们探讨Java中的容器类,所谓容器,顾名思义就是容纳其他数据的,计算机课程中有一门课叫数据结构,可以粗略对应于Java中的容器类,我们不会介绍所有...

2185
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十七】Set接口集合详解

三、Set接口 Set是一种不包括重复元素的Collection。它维持它自己的内部排序,所以随机访问没有任何意义。与List一样,它同样运行nu...

3659
来自专栏IT可乐

JDK1.8源码(十)——java.util.LinkedHashSet类

  同 HashSet 与 HashMap 的关系一样,本篇博客所介绍的 LinkedHashSet 和 LinkedHashMap 也是一致的。在 JDK 集...

851
来自专栏Python爬虫与算法进阶

萌新刷题(十二)二叉树的前序遍历

题目 给出一棵二叉树,返回其节点值的前序遍历。 样例 给出一棵二叉树 {1,#,2,3}, 1 \ 2 / ...

3296

扫码关注云+社区

领取腾讯云代金券