面試必問(wèn)項(xiàng)之Set實(shí)現(xiàn)類:TreeSet
一、TreeSet 概述
1、TreeSet是 SortedSet 接口的實(shí)現(xiàn)類， TreeSet 可以確保集合元素處于排序狀態(tài)。
2、TreeSet顧名思義他內(nèi)部維護(hù)的是一個(gè)TreeMap，底層是紅黑二叉樹(shù)，他使得集合內(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、紅黑樹(shù)
TreeSet和后要的TreeMap采用紅黑樹(shù)的存儲(chǔ)結(jié)構(gòu)
特點(diǎn)：有序，查詢速度比List快
三、TreeSet 創(chuàng)建
1、構(gòu)造器
TreeSet是基于紅黑樹(shù)結(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開(kāi)發(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)看看寫(xiě)的一個(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開(kāi)發(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開(kāi)發(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中，重寫(xiě)該對(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接口，如果元素所屬的類沒(méi)有實(shí)現(xiàn)Comparable接口，或不希望按照升序(默認(rèn)情況)的方式排列元素或希望按照其它屬性大小進(jìn)行排序，則考慮使用定制排序。定制排序，通過(guò)Comparator接口來(lái)實(shí)現(xiàn)。需要重寫(xiě)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開(kāi)發(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());
}
}
注意：如果在自然比較器中并沒(méi)有對(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)容！
相關(guān)文章
在Java中,方法參數(shù)的傳遞方式實(shí)際上是按值傳遞,接下來(lái)通過(guò)本文給大家介紹了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接口實(shí)現(xiàn)自動(dòng)任務(wù)加載功能
這篇文章主要介紹了springboot CommandLineRunner接口實(shí)現(xiàn)自動(dòng)任務(wù)加載功能，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-05-05
SpringBoot實(shí)現(xiàn)釘釘機(jī)器人消息推送的示例代碼
這篇文章主要介紹了SpringBoot實(shí)現(xiàn)釘釘機(jī)器人消息推送的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
這篇文章主要為大家詳細(xì)介紹了Java設(shè)計(jì)模式之抽象工廠模式的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-03-03
通過(guò)pipeline配置sonar自動(dòng)化實(shí)現(xiàn)過(guò)程解析
這篇文章主要介紹了通過(guò)pipeline配置sonar自動(dòng)化實(shí)現(xiàn)過(guò)程解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11
Java面試題沖刺第六天--網(wǎng)絡(luò)編程1
這篇文章主要為大家分享了最有價(jià)值的三道網(wǎng)絡(luò)編程面試題，涵蓋內(nèi)容全面，包括數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的題目、經(jīng)典面試編程題等，感興趣的小伙伴們可以參考一下2021-07-07
springboot通用分支處理超級(jí)管理員權(quán)限邏輯
這篇文章主要為大家介紹了springboot通用分支處理超級(jí)管理員的權(quán)限邏輯，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
java大數(shù)乘法的簡(jiǎn)單實(shí)現(xiàn) 浮點(diǎn)數(shù)乘法運(yùn)算
大數(shù)乘法可以進(jìn)行任意大小和精度的整數(shù)和浮點(diǎn)數(shù)的乘法運(yùn)算, 精確度很高, 可以用作經(jīng)融等領(lǐng)域的計(jì)算，這個(gè)是我看了一些資料, 然后自己整理實(shí)現(xiàn)的，簡(jiǎn)單測(cè)試了一下2014-01-01