【Java入门提高篇】Day31 Java容器类详解（十三）TreeSet详解

上一篇很水的介绍完了TreeMap，这一篇来看看更水的TreeSet。

本文将从以下几个角度进行展开：

1、TreeSet简介和使用栗子

2、TreeSet源码分析

本篇大约需食用10分钟，各位看官请随意享用。

一、TreeSet简介
　　TreeSet是Set家族中的又一名懒将，跟其他两位一样，与对应的Map关系密不可分

我们先来回顾一下其他两个Set类，HashSet借助于HashMap拥有快速元素插入和查找的特性，LinkedHashSet借助于LinkedHashMap拥有快速插入查找以及使元素保持插入顺序的特性，TreeSet则是借助于TreeMap拥有使内部元素保持有序的特性，当然，所有的Set集合类都有元素去重的特性。当然，要区别一下的是，TreeSet中的有序是指可以按照内部比较器或者外部比较器的顺序对插入的元素进行排序，也就是每次插入后都会调整顺序以保持内部元素整体有序，而LinkedHashSet只能保持元素的插入顺序。

Talk is cheap，show me your code. 嗯，还是来看代码吧：

public class TreeSetTest {

    public static void main(String[] args){
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("Frank");
        treeSet.add("Alice");
        treeSet.add("Bob");
        treeSet.add("Allen");
        treeSet.add("Ada");
        treeSet.add("Adora");
        System.out.println(treeSet);

        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("Frank");
        linkedHashSet.add("Alice");
        linkedHashSet.add("Bob");
        linkedHashSet.add("Allen");
        linkedHashSet.add("Ada");
        linkedHashSet.add("Adora");
        System.out.println(linkedHashSet);

    }
    
}

输出如下：

[Ada, Adora, Alice, Allen, Bob, Frank]
[Frank, Alice, Bob, Allen, Ada, Adora]

可以看到TreeSet给插入的元素自动排序了。那么可不可以放入我们自定义的类元素呢？当然是可以的，不然要它何用

public class TreeSetTest {

    public static void main(String[] args){
        List<Goods> goods = new ArrayList<>();
        goods.add(new Goods("Iphone4S",500.00));
        goods.add(new Goods("Iphone5",800.00));
        goods.add(new Goods("Iphone6S",2500.00));
        goods.add(new Goods("Iphone7S",4500.00));
        goods.add(new Goods("Iphone8",6500.00));
        goods.add(new Goods("IphoneX",8500.00));
        System.out.println(goods);

        TreeSet<Goods> treeSet = new TreeSet<>();
        treeSet.addAll(goods);
        System.out.println(treeSet);

        LinkedHashSet<Goods> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.addAll(goods);
        System.out.println(linkedHashSet);
    }

    public static class Goods{
        private String name;
        private Double price;

        public Goods(String name, Double price) {
            this.name = name;
            this.price = price;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Double getPrice() {
            return price;
        }

        public void setPrice(Double price) {
            this.price = price;
        }

        @Override
        public String toString() {
            return "Goods{" +
                    "name='" + name + ''' +
                    ", price=" + price +
                    '}';
        }
    }

}

输出如下：

Exception in thread "main" java.lang.ClassCastException: com.frank.chapter22.TreeSetTest$Goods cannot be cast to java.lang.Comparable
[Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='IphoneX', price=8500.0}]
    at java.util.TreeMap.compare(TreeMap.java:1294)
    at java.util.TreeMap.put(TreeMap.java:538)
    at java.util.TreeSet.add(TreeSet.java:255)
    at java.util.AbstractCollection.addAll(AbstractCollection.java:344)
    at java.util.TreeSet.addAll(TreeSet.java:312)
    at com.frank.chapter22.TreeSetTest.main(TreeSetTest.java:25)

欢迎来到大型翻车现场。。。

别慌别慌，问题不大。TreeSet与TreeMap一样，是需要元素实现Comparable接口或者传入一个外部比较器的。为什么String可以不用？看看String的实现吧，人家可是实现了Comparable接口的。

所以有两种方式解决，一种是让Goods类实现Comparable接口，另一种是传入一个外部比较器，我们先来看第一种：

public class TreeSetTest {

    public static void main(String[] args){
        List<Goods> goods = new ArrayList<>();
        goods.add(new Goods("Iphone7S",4500.00));
        goods.add(new Goods("Iphone4S",500.00));
        goods.add(new Goods("Iphone5",800.00));
        goods.add(new Goods("IphoneX",8500.00));
        goods.add(new Goods("Iphone6S",2500.00));
        goods.add(new Goods("Iphone8",6500.00));
        goods.add(new Goods("Iphone8",6500.00));
        System.out.println(goods);

        TreeSet<Goods> treeSet = new TreeSet<>();
        treeSet.addAll(goods);
        System.out.println(treeSet);

        LinkedHashSet<Goods> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.addAll(goods);
        System.out.println(linkedHashSet);
    }

    public static class Goods implements Comparable{
        private String name;
        private Double price;

        public Goods(String name, Double price) {
            this.name = name;
            this.price = price;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Double getPrice() {
            return price;
        }

        public void setPrice(Double price) {
            this.price = price;
        }

        @Override
        public String toString() {
            return "Goods{" +
                    "name='" + name + ''' +
                    ", price=" + price +
                    '}';
        }

        @Override
        public int compareTo(Object o) {
            if (!(o instanceof Goods)){
                return -1;
            }
            Goods goods = (Goods) o;
            return this.price.compareTo(goods.getPrice());
        }
    }

}

为了看出效果，把几个商品的顺序调整了一下，输出如下：

[Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}]
[Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='IphoneX', price=8500.0}]
[Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}]

这里我们按价格进行了升序排列，接下来使用外部比较器的方式进行价格的倒序排列：

public class TreeSetTest {

    public static void main(String[] args){
        List<Goods> goods = new ArrayList<>();
        goods.add(new Goods("Iphone7S",4500.00));
        goods.add(new Goods("Iphone4S",500.00));
        goods.add(new Goods("Iphone5",800.00));
        goods.add(new Goods("IphoneX",8500.00));
        goods.add(new Goods("Iphone6S",2500.00));
        goods.add(new Goods("Iphone8",6500.00));
        goods.add(new Goods("Iphone8",6500.00));
        System.out.println(goods);

        // 1、使用Lamada表达式
        //TreeSet<Goods> treeSet = new TreeSet<>((g1,g2) -> g2.getPrice().compareTo(g1.getPrice()));
        // 2、使用匿名内部类
        TreeSet<Goods> treeSet = new TreeSet<>(new Comparator<Goods>() {
            @Override
            public int compare(Goods o1, Goods o2) {
                return o2.getPrice().compareTo(o1.getPrice());
            }
        });
        
        
        treeSet.addAll(goods);
        System.out.println(treeSet);

        LinkedHashSet<Goods> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.addAll(goods);
        System.out.println(linkedHashSet);
    }

    public static class Goods{
        private String name;
        private Double price;

        public Goods(String name, Double price) {
            this.name = name;
            this.price = price;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Double getPrice() {
            return price;
        }

        public void setPrice(Double price) {
            this.price = price;
        }

        @Override
        public String toString() {
            return "Goods{" +
                    "name='" + name + ''' +
                    ", price=" + price +
                    '}';
        }

    }

}

在传入外部比较器的时候，也有很多种姿势，这里还是选了匿名内部类的方式进行传入，因为这里只需要使用一次，Lamada表达式还没有做介绍，这里就先不讲了，欣赏一下就好，先领略一下它的强大。

[Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}]
[Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='Iphone4S', price=500.0}]
[Goods{name='Iphone7S', price=4500.0}, Goods{name='Iphone4S', price=500.0}, Goods{name='Iphone5', price=800.0}, Goods{name='IphoneX', price=8500.0}, Goods{name='Iphone6S', price=2500.0}, Goods{name='Iphone8', price=6500.0}, Goods{name='Iphone8', price=6500.0}]

这样，就完成了倒序排列了，很简单吧。

二、TreeSet源码分析

先来看看TreeSet的继承关系图：

　　
　　跟TreeMap的继承机构差不多，NavigableSet接口中存在大量的导航方法，可以帮助更快定位想要查找的元素，AbstractSet提供Set的部分默认实现，这样只需要实现其它方法即可。

可以看到，TreeSet中的方法并不是很多，除了导航方法之外，就是几个最常用的方法了，如add，addAll，remove，contains。接下来让我们一起看看这几个方法是如何实现的：

先来看看内部成员和构造函数：

    /**
     * 内部默默无闻工作的Map
     */
    private transient NavigableMap<E,Object> m;

    // map中共用的一个value
    private static final Object PRESENT = new Object();

    //默认构造方法，根据其元素的自然顺序进行排序
        public TreeSet() {
            this(new TreeMap<E,Object>());
        }

        //构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的自然顺序进行排序。
        public TreeSet(Comparator<? super E> comparator) {
                this(new TreeMap<>(comparator));
        }

        //构造一个新的空 TreeSet，它根据指定比较器进行排序。
        public TreeSet(Collection<? extends E> c) {
            this();
            addAll(c);
        }

        //构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。
        public TreeSet(SortedSet<E> s) {
            this(s.comparator());
            addAll(s);
        }

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

add方法，嗯，够简明扼要。

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

addAll：

public  boolean addAll(Collection<? extends E> c) {
        // 先检测集合是否继承了SortedSet接口，内部map是否为TreeMap
        // 并且检测使用的比较器是否与内部Map的比较器一致
        // 如果一致的话则使用TreeMap的addAllForTreeSet方法进行批量插入
        // addAllForTreeSet方法可以在常量时间对有序元素进行插入 
        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<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        // 如果不满足条件，则使用父类的addAll方法进行添加
        return super.addAll(c);
    }

嗯，这里会先激进优化，不行再用笨办法一个个添加，因为如果是将大量元素插入TreeMap中相对而言还是比较耗时耗力的，每次插入一个元素都可能导致整体结构的调整，而如果插入的元素刚好是有序的，那么就可以对这个过程进行一次很不错的优化。

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

remove和contains方法也很简单。而且还带一点粗暴

到此，本篇就结束了，其实也没太多内容，因为TreeSet本身也没有太多东西。当然，了解它的内部结构目的是为了更好的使用它。在遇到问题时，每个知识点就是你手中的一张牌，能不能打好这手牌，先要看你这牌好不好，牌不好的话，再聪明也难翻盘。