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

ゞ浴缸里的玫瑰 2022-10-19 08:50 109阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70][]

## 一、TreeSet 概述 ##

*  1、`TreeSet`是 `SortedSet` 接口的实现类， `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 类继承结构 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 1][]

### 3、红黑树![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 2][] ###

`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);
        }
    }
    打印结果：
    1
    5
    9
    10

## 四、TreeSet 方法 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 3][]

## 五、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);
    }
    // 返回大于当前元素的最近一个元素
    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` 的典型实现：  
    　　　　　　① `BigDecimal`、`BigInteger` 以及所有的数值型对应的包装类：按它们对应的数值大小进行比较；  
    　　　　　　② `Character`：按字符的 `unicode`值来进行比较；  
    　　　　　　③ `Boolean：true` 对应的包装类实例大于 `false` 对应的包装类实例；  
    　　　　　　④`String`：按字符串中字符的 `unicode` 值进行比较  
    　　　　　　⑤ `Date`、`Time`：后边的时间、日期比前面的时间、日期大
 *  （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{
        
                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**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70]: /images/20221005/897dcc96618a4683bb1d762ae4319cb8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 1]: /images/20221005/2cf828de2f43431593fe293a0dbd643d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 2]: /images/20221005/4e30c1ae763a496a913d9765055b2647.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70 3]: /images/20221005/1a58a78eac08467f8dde0295314d3820.png