【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本身也没有太多东西。当然,了解它的内部结构目的是为了更好的使用它。在遇到问题时,每个知识点就是你手中的一张牌,能不能打好这手牌,先要看你这牌好不好,牌不好的话,再聪明也难翻盘。

.  

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mySoul

线性表

源文件 https://gitlab.com/melovemingming/code/blob/practice/practice/C/2018/10/01/u...

851
来自专栏计算机视觉与深度学习基础

Leetcode 258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the resul...

1965
来自专栏Java爬坑系列

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

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

903
来自专栏计算机视觉与深度学习基础

Leetcode 173 Binary Search Tree Iterator

mplement an iterator over a binary search tree (BST). Your iterator will be ini...

2156
来自专栏猿人谷

顺序线性表

线性表的顺序表示和实现 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的第一个数据元素a1的存储位置,通常称作线性表的起始位置...

2225
来自专栏猿人谷

双向链表

双向链表       在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表...

2645
来自专栏架构之路

离线Tarjan算法-最近公共祖先问题

转载自Tarjan算法 LCA问题(Least Common Ancestors,最近公共祖先问题),是指给定一棵有根树T,给出若干个查询LCA(u, v)(通...

3735
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

1101
来自专栏数据处理

leetcode222求完全二叉树节点个数

3684
来自专栏小狼的世界

Aptana的破解

最近写JS比较多,常常苦恼与没有一个顺手的IDE。Editplus虽然用的熟,不过那个的效率太低而且代码看起来也很不方便,经过一个多月的试用,发现了一款好用的编...

1012

扫码关注云+社区

领取腾讯云代金券