Java集合框架之TreeSet

简述

TreeSet是基于TreeMap作为存储的可排序、可去重的有序集合

继承于AbstractSet,AbstractSet实现了equals和hashcode方法

实现了NavigableSet接口，意味着它支持一系列的导航方法，比如查找与指定目标最匹配项

实现了Cloneable接口，意味着它能被复制

实现了java.io.Serializable接口，意味着它支持序列化

TreeSet源码分析



public class TreeSet<E> extends AbstractSet<E>

    implements NavigableSet<E>, Cloneable, java.io.Serializable

{

    /**

     * 使用 NavigableMap 的 key 来存储 Set 集合的元素

     */

    private transient NavigableMap<E,Object> m;

    // 虚拟一个 PRESENT 作为 Map 集合的所有 value

    private static final Object PRESENT = new Object();

    /**

     * 包级别访问权限的构造器，以指定的 NavigableMap 对象创建 Set 集合

     */

    TreeSet(NavigableMap<E,Object> m) {

        this.m = m;

    }

    /**

     * 以自然排序方式创建一个新的 TreeMap，

     * 使用该 TreeMap 的 key 来保存 Set 集合的元素

     */

    public TreeSet() {

        this(new TreeMap<E,Object>());

    }

    /**

     * 根据自定义排序方式创建一个新的 TreeMap，

     * 使用该 TreeMap 的 key 来保存 Set 集合的元素

     */

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

        this(new TreeMap<>(comparator));

    }

    /**

     * 根据无参构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素

     * 向 TreeSet 中添加 指定Collection 集合 c 里的所有元素

     */

    public TreeSet(Collection<? extends E> c) {

        this();

        addAll(c);

    }

    /**

     * 根据有参构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素

     * 向 TreeSet 中添加 指定Collection 集合 c 里的所有元素

     */

    public TreeSet(SortedSet<E> s) {

        this(s.comparator());

        addAll(s);

    }

---------------下面来看addAll方法-------------------

    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 集合

            SortedSet<? extends E> set = (SortedSet<? extends E>) c;

            # 把NavigableMap集合强制转换为 TreeMap集合

            TreeMap<E,Object> map = (TreeMap<E, Object>) m;

            Comparator<?> cc = set.comparator();

            Comparator<? super E> mc = map.comparator();

            # 如果 cc 和 mc 两个 Comparator 相等

            if (cc==mc || (cc != null && cc.equals(mc))) {

            # 把指定集合Collection 中所有元素作为 TreeMap 集合的 key 进行存储

                map.addAllForTreeSet(set, PRESENT);

                return true;

            }

        }

        return super.addAll(c);

    }

}

从上面代码可以看出，TreeSet 的前两个构造器的都是新建一个 TreeMap 作为实际存储 Set 元素的容器，而另外 2 个构造器则分别依赖于前两个构造器，由此可见，TreeSet 底层实际使用的存储容器就是 TreeMap

TreeSet排序方式

由源码我们可知TreeSet的排序方式有两种：

一是自然排序，使用默认构造函数

Java提供了一个Comparable接口，该接口里定义了一个compareTo(Object obj)方法，该方法返回一个整数值，实现该接口的类必须实现该方法，实现了该接口的类的对象就可以比较大小了。当一个对象调用该方法与另一个对象进行比较，

例如 obj1.compareTo(obj2)

如果该方法返回0，则表明这两个对象相等；
如果该方法返回一个正整数，则表明obj1大于obj2；
如果该方法返回一个负整数，则表明obj1小于obj2。

Java的一些常用类已经实现了Comparable接口，并提供了比较大小的标准，下面是实现了Comparable接口的常用类：

BigDecimal、BigInteger以及所有数值型对应包装类：按它们对象的数值大小进行比较
Character ：按字符的Unicode值进行比较
Boolean ： true对应的包装类实例大于false对应的包装类实例
String : 按字符串中字符的Unicode值进行比较
Date、Time ：后面的时间、日期比前面的日期时间大。

二是比较器排序，使用指定比较器的构造函数

TreeSet的自然排序是根据集合元素的大小默认以升序排列。如果需要完成定制排序，例如以降序排列，则可以使用Comparator接口的帮助。

该接口里包含了一个int compare(T o1, T o2)方法，

该方法用于比较o1、o2的大小：

如果该方法返回正整数，则表明o1大于o2；

如果该方法返回0，则表明o1等于o2；

如果该方法返回负整数，则表明o1小于o2。

事例

以自然顺序排序，并且元素不重复

public class TreeSetDemo {

    public static void main(String[] args) {

        TreeSet<String> treeSet = new TreeSet<>();

        for (int i = 0; i < 5; i++) {

            treeSet.add("item" + i);

        }

        for (int i = 0; i < 5; i++) {

            treeSet.add("item" + i);

        }

        treeSet.forEach(item -> {

            System.err.println(item);

        });

    }

}

输出结果：

item0

item1

item2

item3

item4

按比较器排序

指定一个比较器，倒置集合中的元素

public class TreeSetDemo {

    public static void main(String[] args) {

        //指定一个比较器，倒置元素顺序

        TreeSet<String> treeSet = new TreeSet<>(Comparator.reverseOrder());

        for (int i = 0; i < 5; i++) {

            treeSet.add("item" + i);

        }

        for (int i = 0; i < 5; i++) {

            treeSet.add("item" + i);

        }

        treeSet.forEach(item -> {

            System.err.println(item);

        });

    }

}