面試必問項(xiàng)之Set實(shí)現(xiàn)類:TreeSet

更新時(shí)間：2021年07月17日 11:15:23 作者：蛋撻學(xué)姐

這篇文章主要介紹了Java TreeSet類的簡(jiǎn)單理解和使用,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下

一、TreeSet 概述

1、TreeSet是 SortedSet 接口的實(shí)現(xiàn)類， TreeSet 可以確保集合元素處于排序狀態(tài)。

2、TreeSet顧名思義他內(nèi)部維護(hù)的是一個(gè)TreeMap，底層是紅黑二叉樹，他使得集合內(nèi)都是有序的序列。

3、Tree可以按照添加對(duì)象的指定屬性，進(jìn)行排序，所以向TreeSet中添加的數(shù)據(jù)，要求是相同類的對(duì)象。

4、兩種排序方式：自然排序（實(shí)現(xiàn)Comparable接口）和定制排序（Comparator）；

5、自然排序中，比較兩個(gè)對(duì)象是否相同的標(biāo)準(zhǔn)為：compareTo()返回0.不再是equals()；

6、定制排序中，比較兩個(gè)對(duì)象是否相同的標(biāo)準(zhǔn)為：compare()返回0.不再是equals()；

7、對(duì) TreeSet進(jìn)行遍歷的時(shí)候，默認(rèn)是使用自然排序的規(guī)則來(lái)排序的；

8、TreeSet 添加自定義類的對(duì)象時(shí)候，必須要有自然排序或定制排序，否則拋出異常：cannot cast to java.lang.Comparable;

二、TreeSet 結(jié)構(gòu)

1、TreeSet 聲明

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

2、TreeSet 類繼承結(jié)構(gòu)

3、紅黑樹

TreeSet和后要的TreeMap采用紅黑樹的存儲(chǔ)結(jié)構(gòu)

特點(diǎn)：有序，查詢速度比List快

三、TreeSet 創(chuàng)建

1、構(gòu)造器

TreeSet是基于紅黑樹結(jié)構(gòu)實(shí)現(xiàn)的，會(huì)對(duì)元素進(jìn)行排序，TreeSet 提供了五種構(gòu)造器：

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開發(fā)交流君樣：593142328一起吹水聊天

可以看到里面是維護(hù)了一個(gè) NavigableMap。

2、通過(guò) Comparator 實(shí)例創(chuàng)建 TreeSet

上面的四個(gè)構(gòu)造函數(shù)中著重要介紹第三個(gè)，它通過(guò)Comparator實(shí)例來(lái)創(chuàng)建TreeMap，那么Comparator到底是何方神圣呢？

通過(guò)閱讀Comparator的源碼發(fā)現(xiàn)，這是一個(gè)用于集合類排序的輔助接口，用戶需要實(shí)現(xiàn)compare方法。

如果用戶用了這種方式創(chuàng)建TreeSet，那么集合元素就不需要做額外處理，否則集合元素都需要實(shí)現(xiàn)Comparable接口，因?yàn)門ree在排序的時(shí)候會(huì)調(diào)用compare或者compareTo方法（介紹TreeMap的時(shí)候會(huì)具體講解）。

下面來(lái)看看寫的一個(gè)樣例代碼：

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元素的時(shí)候會(huì)判斷是否存在Comparator實(shí)例，如果存在，則每次添加元素排序比較的時(shí)候會(huì)調(diào)用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開發(fā)交流君樣：593142328一起吹水聊天
}

打印結(jié)果：

1 5 9 10

四、TreeSet 方法

五、NavigableSet接口介紹

常用方法：

// 返回比當(dāng)前元素小的最近的一個(gè)元素
public E lower(E e) {
    return m.lowerKey(e);
}
// 返回小于等于當(dāng)前元素的最近一個(gè)元素
public E floor(E e) {
    return m.floorKey(e);
}
//　返回大于等于當(dāng)前元素的最近一個(gè)元素
public E ceiling(E e) {
    return m.ceilingKey(e);
}//加入Java開發(fā)交流君樣：593142328一起吹水聊天
// 返回大于當(dāng)前元素的最近一個(gè)元素
public E higher(E e) {
    return m.higherKey(e);
}

六、TreeSet 與比較器

1、自然排序

（1）自然排序：TreeSet會(huì)調(diào)用集合元素的 compareTo(Object obj) 方法來(lái)比較元素之間的大小關(guān)系，然后將集合元素按升序(默認(rèn)情況)排列。

（2）如果試圖把一個(gè)對(duì)象添加到TreeSet時(shí)，則該對(duì)象的類必須實(shí)現(xiàn) Comparable接口?！　　　　　?/p>

實(shí)現(xiàn)Comparable 的類必須實(shí)現(xiàn)compareTo(Object obj)方法，兩個(gè)對(duì)象即通過(guò)compareTo(Object obj)方法的返回值來(lái)比較大小。

（3）Comparable 的典型實(shí)現(xiàn)：　　　　　　

① BigDecimal、BigInteger 以及所有的數(shù)值型對(duì)應(yīng)的包裝類：按它們對(duì)應(yīng)的數(shù)值大小進(jìn)行比較；
② Character：按字符的 unicode值來(lái)進(jìn)行比較；
③ Boolean：true 對(duì)應(yīng)的包裝類實(shí)例大于 false 對(duì)應(yīng)的包裝類實(shí)例；
④String：按字符串中字符的 unicode 值進(jìn)行比較
⑤ Date、Time：后邊的時(shí)間、日期比前面的時(shí)間、日期大

（4）向 TreeSet 中添加元素時(shí)，只有第一個(gè)元素?zé)o須比較compareTo()方法，后面添加的所有元素都會(huì)調(diào)用compareTo()方法進(jìn)行比較。

（5）因?yàn)橹挥邢嗤惖膬蓚€(gè)實(shí)例才會(huì)比較大小，所以向 TreeSet 中添加的應(yīng)該是同一個(gè)類的對(duì)象。

（6）對(duì)于 TreeSet 集合而言，它判斷兩個(gè)對(duì)象是否相等的唯一標(biāo)準(zhǔn)是：兩個(gè)對(duì)象通過(guò) compareTo(Object obj)方法比較返回值。

（7）當(dāng)需要把一個(gè)對(duì)象放入 TreeSet中，重寫該對(duì)象對(duì)應(yīng)的 equals()方法時(shí)，應(yīng)保證該方法與 compareTo(Object obj) 方法有一致的結(jié)果：如果兩個(gè)對(duì)象通過(guò) equals() 方法比較返回 true，則通過(guò) compareTo(Object obj)方法比較應(yīng)返回 0。否則，讓人難以理解。

2、定制排序

（1）TreeSet的自然排序要求元素所屬的類實(shí)現(xiàn)Comparable接口，如果元素所屬的類沒有實(shí)現(xiàn)Comparable接口，或不希望按照升序(默認(rèn)情況)的方式排列元素或希望按照其它屬性大小進(jìn)行排序，則考慮使用定制排序。定制排序，通過(guò)Comparator接口來(lái)實(shí)現(xiàn)。需要重寫compare(T o1,T o2)方法。

（2）利用int compare(T o1,T o2)方法，比較o1和o2的大?。喝绻椒ǚ祷卣麛?shù)，則表示o1大于o2；如果返回0，表示相等；返回負(fù)整數(shù)，表示o1小于o2?！久嬖囐Y料】

（3）要實(shí)現(xiàn)定制排序，需要將實(shí)現(xiàn)Comparator接口的實(shí)例作為形參傳遞給TreeSet的構(gòu)造器。

（4）此時(shí)，仍然只能向TreeSet中添加類型相同的對(duì)象。否則發(fā)生ClassCastException異常。

（5）使用定制排序判斷兩個(gè)元素相等的標(biāo)準(zhǔn)是：通過(guò)Comparator比較兩個(gè)元素返回了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開發(fā)交流君樣：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());
        }
    }

注意：如果在自然比較器中并沒有對(duì)年齡進(jìn)行比較，當(dāng)姓名一樣時(shí)，就會(huì)認(rèn)為這兩個(gè)對(duì)象一樣，不會(huì)再次存放；

如果在比較器中對(duì)兩個(gè)屬性都進(jìn)行了比較，當(dāng)有一個(gè)屬性不一樣就會(huì)放入 TreeSet中。

可以發(fā)現(xiàn)，這里對(duì)兩個(gè)對(duì)象的比較并不是使用 equals() 方法，而是使用比較器來(lái)進(jìn)行比較的。

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("輸入的數(shù)據(jù)類型不匹配");
                }
            }
        };
        TreeSet set = new TreeSet(com);  //按照給定的比較器進(jìn)行排序
        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());
        }
    }

總結(jié)

本篇文章就到這里了，希望能給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

您可能感興趣的文章:

Set
TreeSet

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

面試必問項(xiàng)之Set實(shí)現(xiàn)類:TreeSet

目錄

一、TreeSet 概述

二、TreeSet 結(jié)構(gòu)

1、TreeSet 聲明

2、TreeSet 類繼承結(jié)構(gòu)

3、紅黑樹

三、TreeSet 創(chuàng)建

1、構(gòu)造器

2、通過(guò) Comparator 實(shí)例創(chuàng)建 TreeSet

四、TreeSet 方法

五、NavigableSet接口介紹

六、TreeSet 與比較器

1、自然排序

2、定制排序

七、案例

1、自定義類的自然排序

2、自定義類的定制排序

總結(jié)

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

面試必問項(xiàng)之Set實(shí)現(xiàn)類:TreeSet

目錄

一、TreeSet 概述

二、TreeSet 結(jié)構(gòu)

1、TreeSet 聲明

2、TreeSet 類繼承結(jié)構(gòu)

3、紅黑樹

三、TreeSet 創(chuàng)建

1、構(gòu)造器

2、通過(guò) Comparator 實(shí)例創(chuàng)建 TreeSet

四、TreeSet 方法

五、NavigableSet接口介紹

六、TreeSet 與 比較器

1、自然排序

2、定制排序

七、案例

1、自定義類的自然排序

2、自定義類的定制排序

總結(jié)

相關(guān)文章

最新評(píng)論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

一、TreeSet 概述

二、TreeSet 結(jié)構(gòu)

1、TreeSet 聲明

2、TreeSet 類繼承結(jié)構(gòu)

3、紅黑樹

1、構(gòu)造器

2、通過(guò) Comparator 實(shí)例創(chuàng)建 TreeSet

四、TreeSet 方法

六、TreeSet 與比較器

1、自然排序

2、定制排序

1、自定義類的自然排序

2、自定義類的定制排序