面試必問項之Set實現(xiàn)類:TreeSet
一、TreeSet 概述
1、TreeSet是 SortedSet 接口的實現(xiàn)類， TreeSet 可以確保集合元素處于排序狀態(tài)。
2、TreeSet顧名思義他內(nèi)部維護的是一個TreeMap，底層是紅黑二叉樹，他使得集合內(nèi)都是有序的序列。
3、Tree可以按照添加對象的指定屬性，進行排序，所以向TreeSet中添加的數(shù)據(jù)，要求是相同類的對象。
4、兩種排序方式：自然排序（實現(xiàn)Comparable接口） 和 定制排序（Comparator）；
5、自然排序中，比較兩個對象是否相同的標(biāo)準(zhǔn)為：compareTo()返回0.不再是equals()；
6、定制排序中，比較兩個對象是否相同的標(biāo)準(zhǔn)為：compare()返回0.不再是equals()；
7、對 TreeSet進行遍歷的時候，默認(rèn)是使用自然排序的規(guī)則來排序的；
8、TreeSet 添加自定義類的對象時候，必須要有自然排序或定制排序，否則拋出異常：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采用紅黑樹的存儲結(jié)構(gòu)
特點：有序，查詢速度比List快
三、TreeSet 創(chuàng)建
1、構(gòu)造器
TreeSet是基于紅黑樹結(jié)構(gòu)實現(xià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一起吹水聊天
可以看到里面是維護了一個 NavigableMap。
2、通過 Comparator 實例創(chuàng)建 TreeSet
上面的四個構(gòu)造函數(shù)中著重要介紹第三個，它通過Comparator實例來創(chuàng)建TreeMap，那么Comparator到底是何方神圣呢？
通過閱讀Comparator的源碼發(fā)現(xiàn)，這是一個用于集合類排序的輔助接口，用戶需要實現(xiàn)compare方法。
如果用戶用了這種方式創(chuàng)建TreeSet，那么集合元素就不需要做額外處理，否則集合元素都需要實現(xiàn)Comparable接口，因為Tree在排序的時候會調(diào)用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實例，如果存在，則每次添加元素排序比較的時候會調(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)前元素小的最近的一個元素
public E lower(E e) {
return m.lowerKey(e);
}
// 返回小于等于當(dāng)前元素的最近一個元素
public E floor(E e) {
return m.floorKey(e);
}
// 返回大于等于當(dāng)前元素的最近一個元素
public E ceiling(E e) {
return m.ceilingKey(e);
}//加入Java開發(fā)交流君樣：593142328一起吹水聊天
// 返回大于當(dāng)前元素的最近一個元素
public E higher(E e) {
return m.higherKey(e);
}
六、TreeSet 與 比較器
1、自然排序
（1）自然排序：TreeSet會調(diào)用集合元素的 compareTo(Object obj) 方法來比較元素之間的大小關(guān)系，然后將集合元素按升序(默認(rèn)情況)排列。
（2）如果試圖把一個對象添加到TreeSet時，則該對象的類必須實現(xiàn) Comparable接口。
實現(xiàn)Comparable 的類必須實現(xiàn)compareTo(Object obj)方法，兩個對象即通過compareTo(Object obj)方法的返回值來比較大小。
（3）Comparable 的典型實現(xiàn)：
- ① BigDecimal、BigInteger 以及所有的數(shù)值型對應(yīng)的包裝類：按它們對應(yīng)的數(shù)值大小進行比較；
- ② Character：按字符的 unicode值來進行比較；
- ③ Boolean：true 對應(yīng)的包裝類實例大于 false 對應(yīng)的包裝類實例；
- ④String：按字符串中字符的 unicode 值進行比較
- ⑤ Date、Time：后邊的時間、日期比前面的時間、日期大
（4）向 TreeSet 中添加元素時，只有第一個元素?zé)o須比較compareTo()方法，后面添加的所有元素都會調(diào)用compareTo()方法進行比較。
（5）因為只有相同類的兩個實例才會比較大小，所以向 TreeSet 中添加的應(yīng)該是同一個類的對象。
（6）對于 TreeSet 集合而言，它判斷兩個對象是否相等的唯一標(biāo)準(zhǔn)是：兩個對象通過 compareTo(Object obj)方法比較返回值。
（7）當(dāng)需要把一個對象放入 TreeSet中，重寫該對象對應(yīng)的 equals()方法時，應(yīng)保證該方法與 compareTo(Object obj) 方法有一致的結(jié)果：如果兩個對象通過 equals() 方法比較返回 true，則通過 compareTo(Object obj)方法比較應(yīng)返回 0。否則，讓人難以理解。
2、定制排序
（1）TreeSet的自然排序要求元素所屬的類實現(xiàn)Comparable接口，如果元素所屬的類沒有實現(xiàn)Comparable接口，或不希望按照升序(默認(rèn)情況)的方式排列元素或希望按照其它屬性大小進行排序，則考慮使用定制排序。定制排序，通過Comparator接口來實現(xiàn)。需要重寫compare(T o1,T o2)方法。
（2）利用int compare(T o1,T o2)方法，比較o1和o2的大?。喝绻椒ǚ祷卣麛?shù)，則表示o1大于o2；如果返回0，表示相等；返回負(fù)整數(shù)，表示o1小于o2。【面試資料】
（3）要實現(xiàn)定制排序，需要將實現(xiàn)Comparator接口的實例作為形參傳遞給TreeSet的構(gòu)造器。
（4）此時，仍然只能向TreeSet中添加類型相同的對象。否則發(fā)生ClassCastException異常。
（5）使用定制排序判斷兩個元素相等的標(biāo)準(zhǔn)是：通過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開發(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());
}
}
注意：如果在自然比較器中并沒有對年齡進行比較，當(dāng)姓名一樣時，就會認(rèn)為這兩個對象一樣，不會再次存放；
如果在比較器中對兩個屬性都進行了比較，當(dāng)有一個屬性不一樣就會放入 TreeSet中。
可以發(fā)現(xiàn)，這里對兩個對象的比較并不是使用 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("輸入的數(shù)據(jù)類型不匹配");
}
}
};
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());
}
}
總結(jié)
本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
相關(guān)文章
在Java中,方法參數(shù)的傳遞方式實際上是按值傳遞,接下來通過本文給大家介紹了Java參數(shù)按值傳遞示例演示,需要的朋友可以參考下2023-09-09
Java IO學(xué)習(xí)之緩沖輸入流（BufferedInputStream）
這篇文章主要介紹了Java IO學(xué)習(xí)之緩沖輸入流（BufferedInputStream）的相關(guān)資料,需要的朋友可以參考下2017-02-02
這篇文章主要介紹了springboot下使用mybatis的方法,需要的朋友可以參考下2017-11-11
springboot CommandLineRunner接口實現(xiàn)自動任務(wù)加載功能
這篇文章主要介紹了springboot CommandLineRunner接口實現(xiàn)自動任務(wù)加載功能，本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-05-05
SpringBoot實現(xiàn)釘釘機器人消息推送的示例代碼
這篇文章主要介紹了SpringBoot實現(xiàn)釘釘機器人消息推送的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
這篇文章主要為大家詳細(xì)介紹了Java設(shè)計模式之抽象工廠模式的相關(guān)資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-03-03
通過pipeline配置sonar自動化實現(xiàn)過程解析
這篇文章主要介紹了通過pipeline配置sonar自動化實現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-11-11
Java面試題沖刺第六天--網(wǎng)絡(luò)編程1
這篇文章主要為大家分享了最有價值的三道網(wǎng)絡(luò)編程面試題，涵蓋內(nèi)容全面，包括數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的題目、經(jīng)典面試編程題等，感興趣的小伙伴們可以參考一下2021-07-07
springboot通用分支處理超級管理員權(quán)限邏輯
這篇文章主要為大家介紹了springboot通用分支處理超級管理員的權(quán)限邏輯，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-07-07
java大數(shù)乘法的簡單實現(xiàn) 浮點數(shù)乘法運算
大數(shù)乘法可以進行任意大小和精度的整數(shù)和浮點數(shù)的乘法運算, 精確度很高, 可以用作經(jīng)融等領(lǐng)域的計算，這個是我看了一些資料, 然后自己整理實現(xiàn)的，簡單測試了一下2014-01-01