大厂Java初级开发工程师!!!面试必问项之Set实现类:TreeSet

Java架构没有996 等级 844 1 0

大厂Java初级开发工程师!!!面试必问项之Set实现类:TreeSet

一、TreeSet 概述

  • 1、TreeSetSortedSet 接口的实现类, TreeSet 可以确保集合元素处于排序状态。

  • 2、TreeSet顾名思义他内部维护的是一个TreeMap,底层是红黑二叉树,他使得集合内都是有序的序列。  

  • 3、Tree可以按照添加对象的指定属性,进行排序,所以向TreeSet中添加的数据,要求是相同类的对象。

  • 4、两种排序方式:自然排序(实现Comparable接口) 和 定制排序(Comparator);

  • 5、自然排序中,比较两个对象是否相同的标准为:compareTo()返回0.不再是equals()

  • 6、定制排序中,比较两个对象是否相同的标准为:compare()返回0.不再是equals()

  • 7、对 TreeSet进行遍历的时候,默认是使用自然排序的规则来排序的;

  • 8、TreeSet 添加自定义类的对象时候,必须要有自然排序或定制排序,否则抛出异常:cannot cast to java.lang.Comparable;

二、TreeSet 结构

1、TreeSet 声明

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

2、TreeSet 类继承结构

大厂Java初级开发工程师!!!面试必问项之Set实现类:TreeSet

3、红黑树大厂Java初级开发工程师!!!面试必问项之Set实现类:TreeSet

TreeSet和后要的TreeMap采用红黑树的存储结构

特点:有序,查询速度比List快

三、TreeSet 创建

1、构造器

TreeSet是基于红黑树结构实现的,会对元素进行排序,TreeSet 提供了五种构造器:

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

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
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);
}

里面的 m 属性是什么:


/**
     * The backing map.
     */
    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    //加入Java开发交流君样:593142328一起吹水聊天

可以看到里面是维护了一个 NavigableMap。

2、通过 Comparator 实例创建 TreeSet

上面的四个构造函数中着重要介绍第三个,它通过Comparator实例来创建TreeMap,那么Comparator到底是何方神圣呢?

通过阅读Comparator的源码发现,这是一个用于集合类排序的辅助接口,用户需要实现compare方法。

如果用户用了这种方式创建TreeSet,那么集合元素就不需要做额外处理,否则集合元素都需要实现Comparable接口,因为Tree在排序的时候会调用compare或者compareTo方法(介绍TreeMap的时候会具体讲解)。

下面来看看写的一个样例代码:


public class MyComparator implements Comparator<Person> {
        @Override
        public int compare(Person o1, Person o2) {
            return o1.age - o2.age;
        }
    }
public class Person {
    public Integer age;
    public Person(Integer value) {
        this.age = value;
    }
}
public static void TreeSetTest() {
    // TreeMap在底层put元素的时候会判断是否存在Comparator实例,如果存在,则每次添加元素排序比较的时候会调用compare接口。
    TreeSet<Person> set = new TreeSet<Person>(new MyComparator());
    Person p1 = new Person(1);
    Person p2 = new Person(1);
    Person p3 = new Person(5);
    Person p4 = new Person(9);
    Person p5 = new Person(10);
    set.add(p1);
    set.add(p2);
    set.add(p3);
    set.add(p4);
    set.add(p5);
    Iterator<Person> i = set.iterator();
    while (i.hasNext()) {
        Person p = (Person) i.next();
        System.out.println(p.age);
    }//加入Java开发交流君样:593142328一起吹水聊天
}
打印结果:
1
5
9
10

四、TreeSet 方法

大厂Java初级开发工程师!!!面试必问项之Set实现类:TreeSet

五、NavigableSet接口介绍

常用方法:

// 返回比当前元素小的最近的一个元素
public E lower(E e) {
    return m.lowerKey(e);
}
// 返回小于等于当前元素的最近一个元素
public E floor(E e) {
    return m.floorKey(e);
}
// 返回大于等于当前元素的最近一个元素
public E ceiling(E e) {
    return m.ceilingKey(e);
}//加入Java开发交流君样:593142328一起吹水聊天
// 返回大于当前元素的最近一个元素
public E higher(E e) {
    return m.higherKey(e);
}

六、TreeSet 与 比较器

1、自然排序

  • (1)自然排序:TreeSet会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系,然后将集合元素按升序(默认情况)排列。

  • (2)如果试图把一个对象添加到TreeSet时,则该对象的类必须实现 Comparable接口。       实现Comparable 的类必须实现compareTo(Object obj)方法,两个对象即通过compareTo(Object obj)方法的返回值来比较大小。

  • (3)Comparable 的典型实现:       ① BigDecimalBigInteger 以及所有的数值型对应的包装类:按它们对应的数值大小进行比较;       ② Character:按字符的 unicode值来进行比较;       ③ Boolean:true 对应的包装类实例大于 false 对应的包装类实例;       ④String:按字符串中字符的 unicode 值进行比较       ⑤ DateTime:后边的时间、日期比前面的时间、日期大

  • (4)向 TreeSet 中添加元素时,只有第一个元素无须比较compareTo()方法,后面添加的所有元素都会调用compareTo()方法进行比较。

  • (5)因为只有相同类的两个实例才会比较大小,所以向 TreeSet 中添加的应该是同一个类的对象。

  • (6)对于 TreeSet 集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过 compareTo(Object obj)方法比较返回值。

  • (7)当需要把一个对象放入 TreeSet中,重写该对象对应的 equals()方法时,应保证该方法与 compareTo(Object obj) 方法有一致的结果:如果两个对象通过 equals() 方法比较返回 true,则通过 compareTo(Object obj)方法比较应返回 0。否则,让人难以理解。

2、定制排序


(1)TreeSet的自然排序要求元素所属的类实现Comparable接口,如果元素所属的类没有实现Comparable接口,或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序,则考虑使用定制排序。定制排序,通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。     (2)利用int compare(T o1,T o2)方法,比较o1和o2的大小:如果方法返回正整数,则表示o1大于o2;如果返回0,表示相等;返回负整数,表示o1小于o2。【面试资料】     (3)要实现定制排序,需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。     (4)此时,仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。     (5)使用定制排序判断两个元素相等的标准是:通过Comparator比较两个元素返回了0。


七、案例

1、自定义类的自然排序

案例:

public class User implements Comparable{
    private String name;
    private int age;

    public User() {
    }

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

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

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("User equals()....");
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        User user = (User) o;

        if (age != user.age) return false;
        return name != null ? name.equals(user.name) : user.name == null;
    }

    @Override
    public int hashCode() { //return name.hashCode() + age;
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }

    //按照姓名从大到小排列,年龄从小到大排列
    @Override
    public int compareTo(Object o) {
        if(o instanceof User){
            User user = (User)o;
//            return -this.name.compareTo(user.name);
            int compare = -this.name.compareTo(user.name);
            if(compare != 0){
                return compare;
            }else{
                return Integer.compare(this.age,user.age);
            }
        }else{//加入Java开发交流君样:593142328一起吹水聊天
            throw new RuntimeException("输入的类型不匹配");
        }

    }
}

 使用TreeSet保存:

@Test
    public void test1(){
        TreeSet set = new TreeSet();
        set.add(new User("Tom",12));
        set.add(new User("Jerry",32));
        set.add(new User("Jim",2));
        set.add(new User("Mike",65));
        set.add(new User("Jack",33));
        set.add(new User("Jack",56));


        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

    }

注意:如果在自然比较器中并没有对年龄进行比较,当姓名一样时,就会认为这两个对象一样,不会再次存放;

如果在比较器中对两个属性都进行了比较,当有一个属性不一样就会放入 TreeSet中。面试资料

可以发现,这里对两个对象的比较并不是使用 equals() 方法,而是使用比较器来进行比较的。

2、自定义类的定制排序

定制排序:

@Test
    public void test2(){
        Comparator com = new Comparator() {
            //按照年龄从小到大排列
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof User && o2 instanceof User){
                    User u1 = (User)o1;
                    User u2 = (User)o2;
                    return Integer.compare(u1.getAge(),u2.getAge());
                }else{
                    throw new RuntimeException("输入的数据类型不匹配");
                }
            }
        };

        TreeSet set = new TreeSet(com);  //按照给定的比较器进行排序
        set.add(new User("Tom",12));
        set.add(new User("Jerry",32));
        set.add(new User("Jim",2));
        set.add(new User("Mike",65));
        set.add(new User("Mary",33));
        set.add(new User("Jack",33));
        set.add(new User("Jack",56));


        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

最后,祝大家早日学有所成,拿到满意offer,快速升职加薪,走上人生巅峰。

可以的话请给我一个三连支持一下我哟??????【白嫖资料】

大厂Java初级开发工程师!!!面试必问项之Set实现类:TreeSet

收藏
评论区

相关推荐

大厂Java初级开发工程师!!!面试必问项之Set实现类:TreeSet
一、TreeSet 概述 1、TreeSet 是 SortedSet 接口的实现类, TreeSet 可以确保集合元素处于排序状态。 2、TreeSet顾名思义他内部维护的是一个TreeMap,底层是红黑二叉树,他使得集合内都是有序的序列。   3、Tree 可以按照添加对象的指定属性,进行排序,所以向TreeSet中添加的数据,要求是相同类的对象。 4、两
Java中如何克隆集合——ArrayList和HashSet深拷贝
编程人员经常误用各个集合类提供的拷贝构造函数作为克隆`List`,`Set`,`ArrayList`,`HashSet`或者其他集合实现的方法。需要记住的是,Java集合的拷贝构造函数只提供浅拷贝而不是深拷贝,这意味着存储在原始List和克隆List中的对象是相同的,指向Java堆内存中相同的位置。增加了这个误解的原因之一是对于[不可变对象](https:/
Java中的集合
Java Collections Framework是Java编程语言的核心部分之一。集合几乎用于任何编程语言中。大多数编程语言都支持各种类型的集合,例如List, Set, Queue, Stack等。 ### 1.什么是Java Collections Framework? 集合就像容器一样,将多个项目组合在一个单元中。例如,一罐巧克力,一组名称等。
Java入门第五篇:Java集合框架的Collection、List、Set、Map接口
【java的集合框架】  Collection:       1.List         ①ArrayList         ②LinkedList       2.set         ①HashSet         ②LinkedHashSet         ③TreeSet Map:        1.HashMap  
Java复习 之容器
小生快要准备找工作了 现在开始复习一下Java基础之容器 ![](https://oscimg.oschina.net/oscnet/1ee6944852619f96dd0e7e7566ab140c474.png) Set和List是一个个往里面存 Map是两个两个往里面装 所谓重复指的是他们互相equals Collection 接口定义了存取一组
Java方面技术点小整理
### Java中的集合吗? java 中的集合分为value、key-valueg两种 存储值有分为list 和 set List 有序的,可以重复 Set 是序的,不可以重复的 根据equals 和 hashCode判断如果一个对象要存储在set中,必须重写equals和hashCode的方法;存储key-value的为map
Java集合框架一览笔录
1、集合概念 ====== 集合类主要负责保存、盛装其他数据,因此集合类也被称为容器类。所以的集合类都位于java.util包下,后来为了处理多线程环境下的并发安全问题,java5还在java.util.concurrent包下提供了一些多线程支持的集合类。 集合分为两大类:Collection、Map。 Collection(集合),每个元素存储单个
Java面试之容器
#### 18\. Java 容器都有哪些? Java 容器分为 Collection 和 Map 两大类,其下又有很多子类,如下所示: * Collection * List * ArrayList * LinkedList * Vector * Stack * Set * Has
java 集合类Array、List、Map区别和联系
java集合类主要分为以下三类: **第一类:Array、Arrays** **第二类:Collection** :List、Set **第三类:Map** :HashMap、HashTable **一、Array , Arrays** Java所有“存储及随机访问一连串对象”的做法,array是最有效率的一种。 1、 效率高,但容量固定且
java基础(五)集合
![](https://images2015.cnblogs.com/blog/875181/201609/875181-20160921100733106-1187286566.png) Collection接口是集合类的根接口,Java中没有提供这个接口的直接的实现类。但是却让其被继承产生了两个接口,就是Set和List。Set中不能包含重复的元素。L
java程序员面试应该具备的一些基本技能
这里列举一些Java程序员面试应该要具备的一些基本技能,仅当参考。 1.基本语法 包括static、final、transient等关键字的作用,foreach循环的原理等等。越简单的问题越能看出一个人的水平,别人对你技术的考量绝大多数都是以深度优先、广度次之为标准的,切记。 2.集合 非常重要,也是必问的内容。基本上就是List、Map、Set,问
Guava Lists.transform的一个小坑
    最近在修改项目中bug的时候遇到一个问题,需要修改一个list里的值,但是不管怎么set值,最后序列化的结果都是原来的值。百思不得其解,最后点开返回list的代码,看到里面用了Guava的Lists.transform做了类型转换,才恍然大悟。因为之前听说过Guava的Lists.transform方法有个坑,于是趁机研究下源码。 publ
HashSet和TreeSet
  Set是java中一个不包含重复元素的collection。更正式地说,set 不包含满足 `e1.equals(e2)` 的元素对 `e1` 和 `e2`,并且最多包含一个 null 元素。正如其名称所暗示的,此接口模仿了数学上的 _set_ 抽象。 HashSet与TreeSet都是基于Set接口的实现类。其中TreeSet是Set的子接口Sor
Redis学习笔记
这篇是接着上篇来的,所以标号就继续了~~~~ **四、set** 介绍: set集合元素是不重复的无序的。set类型与list类型有相似之处,如图: ![](http://static.oschina.net/uploads/space/2015/1212/170939_JldH_780876.png) 命令: ①sa
Redis常用命令
**Redis****常用命令** Redis支持五种数据类型:string(字符串),hash(哈希),list(列表),set(集合)及zset(sorted set:有序集合)等 [https://gitee.com/nmwork/RedisUtil](https://gitee.com/nmwork/RedisUtil) 1.   Redis数