面試必問項之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接口?！ ?/p>
實現(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)文章
SpringBoot使用MockMvc測試get和post接口的示例代碼
Spring Boot MockMvc是一個用于單元測試的模塊,它是Spring框架的一部分,專注于簡化Web應(yīng)用程序的測試,MockMvc主要用來模擬一個完整的HTTP請求-響應(yīng)生命周期,本文給大家介紹了SpringBoot使用MockMvc測試get和post接口,需要的朋友可以參考下2024-06-06
本系統(tǒng)模擬銀行用戶使用ATM機開戶、查詢、存款、取款功能，要求使用java語言編程實現(xiàn)。這篇文章主要介紹了Java 模擬銀行自助終端系統(tǒng)的相關(guān)資料,需要的朋友可以參考下2016-10-10
Java 基礎(chǔ)全面講解StringBuffer類的使用
當(dāng)對字符串進行修改的時候，需要使用 StringBuffer 和 StringBuilder類，和String類不同的是，StringBuffer和 StringBuilder類的對象能夠被多次的修改，并且不產(chǎn)生新的未使用對象2022-01-01
Springboot集成百度地圖實現(xiàn)定位打卡的示例代碼
本文主要介紹了Springboot集成百度地圖實現(xiàn)定位打卡的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-02-02
這篇文章主要介紹了Java判斷字符串中是否包含中文方法,使用Matcher類解決了這個問題,需要的朋友可以參考下2014-06-06
下面小編就為大家分享一篇尋找二叉樹最遠的葉子結(jié)點的實例講解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2017-12-12
這篇文章主要介紹了Java內(nèi)存模型JMM詳解，涉及volatile和監(jiān)視器鎖，final字段，內(nèi)存屏障等相關(guān)內(nèi)容，具有一定參考價值，需要的朋友可以了解下。2017-11-11
java 解決異常 2 字節(jié)的 UTF-8 序列的字節(jié)2 無效的問題
這篇文章主要介紹了java 解決異常 2 字節(jié)的 UTF-8 序列的字節(jié) 2 無效的問題的相關(guān)資料,需要的朋友可以參考下2016-12-12
這篇文章主要介紹了Mybatis的三種批量插入方式，幫助大家更好的理解和學(xué)習(xí)使用Java，感興趣的朋友可以了解下2021-04-04
這篇文章主要介紹了Java二維數(shù)組簡單定義與使用方法,結(jié)合實例形式簡單分析了java二維數(shù)組的定義、使用方法及相關(guān)注意事項,需要的朋友可以參考下2017-10-10