【0】README

0.1） 本文描述轉(zhuǎn)自 core java volume 1， 源代碼為原創(chuàng)，旨在理解 java集合——樹集（TreeSet）+對(duì)象的比較 的相關(guān)知識(shí)；
0.2） for full source code, please visit https://github.com/pacosonTang/core-java-volume/blob/master/chapter13/TreeSetTest.java
0.3） for java.lang.Comparable 和 java.util.Comparator 的區(qū)別和聯(lián)系：
http://blog.csdn.net/pacosonswjtu/article/details/50320775　＋　http://blog.csdn.net/pacosonswjtu/article/details/50320887

---

【1】樹集（TreeSet）（用到了紅黑樹）

1.1）樹集是一個(gè)有序集合。可以以任意順序?qū)⒃夭迦氲郊现?#xff0c; 在對(duì)集合進(jìn)行遍歷時(shí)，每個(gè)值將自動(dòng)地按照排序后的順序呈現(xiàn)；

• 1.1.1）看個(gè)荔枝：

SortedSet<String> sorter = new TreeSet<>(); // TreeSet implements SortedSet sorter.add("bob"); sorter.add("car"); sorter.add("amy"); for(String s: sorter)System.println(s);

1.1.2）將元素添加到 樹（TreeSet）中要比添加到散列表（HashSet）中慢， 但是，與將元素添加到數(shù)組或鏈表的正確位置上相比還是快很多的；


Attention） TreeSet 的排序功能用到了紅黑樹， 因此迭代器總是以排好序的順序訪問(wèn)每個(gè)元素）

API java.util.TreeSet<E> 1.2 TreeSet（）:構(gòu)造一個(gè)空樹集； TreeSet（Collection<? extends E> elements）：構(gòu)造一個(gè)樹集， 并將集合中所有元素添加到樹集中；

---

【2】對(duì)象的比較

2.1） TreeSet如何知道希望元素怎樣排列呢？ 在默認(rèn)情況下， 樹集假定插入的元素實(shí)現(xiàn)了 Comparable 接口， 這個(gè)接口定義了一個(gè)方法：

public interface Comparable<T> {in compareTo(T other); }

• 2.1.1）排序后，a在b的前面，后面或相等，分別返回 負(fù)值，正值，0；
• 2.1.2）有些標(biāo)準(zhǔn)的 java 平臺(tái)類實(shí)現(xiàn)了 Comparable接口，如， String類， 這個(gè)類的compareTo() 方法依據(jù)字典順序?qū)ψ址M(jìn)行比較；

2.2）如果要插入自定義對(duì)象， 就必須通過(guò)實(shí)現(xiàn) Comparable接口自定義排列順序。

• Attention）在 Object類中， 沒(méi)有提供任何 compareTo 接口的默認(rèn)實(shí)現(xiàn) （干貨）；
• 2.2.1）看個(gè)荔枝：（展示了如何用部件編號(hào)對(duì) Item 對(duì)象進(jìn)行排序）

class Item implements Comparable<Item> {public int compareTo(Item other){return partNumber - other.partNumber;} }

• Warning）只有整數(shù)在一個(gè)足夠小的范圍內(nèi)，才可以使用這個(gè)技巧。 如果x是一個(gè)較大的正整數(shù)， y是一個(gè)較大的負(fù)整數(shù)， x-y 有可能會(huì)溢出；

2.3）出現(xiàn)的問(wèn)題+解決方法

• 2.3.1）出現(xiàn)的問(wèn)題：使用 Comparable接口定義排列排序顯然有其局限性。對(duì)于一個(gè)給定的類， 只能實(shí)現(xiàn)這個(gè)接口一次。如果在一個(gè)集合中需要按照部件編號(hào)進(jìn)行排序， 在另一個(gè)集合中 卻要按照描述信息進(jìn)行排序， 該怎么辦呢？還有，如果需要對(duì)一個(gè)類的對(duì)象進(jìn)行排序， 而這個(gè)類的創(chuàng)建者又沒(méi)有實(shí)現(xiàn) Comparable接口， 又該怎么辦呢？
• 2.3.2）解決方法： 通過(guò)將 Comparator 對(duì)象傳遞給TreeSet構(gòu)造器來(lái)告訴樹集使用不同的比較方法。 Comparator接口聲明了一個(gè)帶有兩個(gè)顯式參數(shù)的compare 方法:

public interface Comparator<T> {int compare(T a, T b); }

• （即， 當(dāng)兩個(gè)不同集合中的元素的排序規(guī)則不同， 就要引入Comparator）
• 2.3.2.1）與 compareTo（） 方法一樣，a在b之前，之后，或相等， 分別返回 正值， 負(fù)值和零；所以，我們直接定義一個(gè) 實(shí)現(xiàn) Comparator 接口的類：

class ItemComparator implements Comparator<Item> {public int compare(Item a, Item b){String desrcA = a.getDescription();String desrcB = b.getDescription();String desrcA.compareTo(desrcB);} }

• 2.3.2.2）然后將這個(gè)類對(duì)象傳遞給樹集的構(gòu)造器：

ItemComparator comp = new ItemComparator(); SortedSort<Item> sort = new TreeSet<>(comp)；

• Attention）

  • A1） 注意， 這個(gè)比較器沒(méi)有任何數(shù)據(jù)， 它只是比較方法的持有器。有時(shí)將這種對(duì)象稱為函數(shù)對(duì)象。
  • A2）函數(shù)對(duì)象通常動(dòng)態(tài)定義， 即定義為匿名內(nèi)部類的實(shí)例：

SortedSet<Item> set = new TreeSet<>(new Comparable<Item>(){ //匿名 內(nèi)部類；public int compare(Item a, Item b) // 匿名內(nèi)部類中的方法；{String desrcA = a.getDescription();String desrcB = b.getDescription();String desrcA.compareTo(desrcB);} });

Annotation）

• A1）實(shí)際上， Comparator 接口聲明了兩個(gè)方法：compare 和 equals；
• A2）當(dāng)然，每個(gè)類都有一個(gè) equals 方法， 因此， 為這個(gè)接口聲明再添加一個(gè) equals 方法似乎沒(méi)有太大的好處；
• A3） API文檔說(shuō)， 不需要覆蓋equals 方法， 但這樣做可能會(huì)在某些情況下 提高性能；

2.4）下面的圖是否給了我們的疑慮：是否總應(yīng)該用 樹集（TreeSet）取代散列集（HashSet）？

• 2.4.1）因?yàn)樘砑右粋€(gè)元素所花費(fèi)的時(shí)間看上去并不很長(zhǎng)， 而且元素時(shí)自動(dòng)排序的；
• 2.4.2）到底應(yīng)該怎樣做將取決于 所要收集的數(shù)據(jù)。如果不需要對(duì)數(shù)據(jù)進(jìn)行排序，就沒(méi)有必要付出排序開(kāi)銷 （干貨，如何選擇集類型， 是樹集TreeSet 還是 散列集 HashSet）。
• 2.4.3）更重要的是， 對(duì)其排序要比 散列函數(shù)更加困難， 因?yàn)樯⒘泻瘮?shù)只是將對(duì)象適
  

2.5）收集矩形集（just for coarse understanding）：想具體了解樹集和散列集間的差異， 還需要研究一個(gè)收集矩形集的任務(wù)。如果使用 TreeSet， 就需要提供 Comparator；

• 2.5.1）如何比較兩個(gè)矩形呢？ 比較面積嗎。這行不通。可能會(huì)有兩個(gè)不同的矩形， 它們的坐標(biāo)不同， 但面積卻相同。 樹的排序必須是全序的。也就是說(shuō)， 任意兩個(gè)元素是可比的，并且只有在兩個(gè)元素相等時(shí)才return 0；
• 2.5.2）確實(shí)， 有一種矩形的排序方式， （按照坐標(biāo)的字典順序排序）， 但它的計(jì)算很牽強(qiáng)且很繁瑣。 相反地， Rectangle 類已經(jīng)定義了散列函數(shù)， 它直接對(duì)坐標(biāo)進(jìn)行散列；

Annotation） 從 Java SE 6 開(kāi)始， TreeSet 類實(shí)現(xiàn)了 NavigableSet 接口。 這個(gè)接口增加了幾個(gè)便于定位元素以及反向遍歷的方法；

2.6）看個(gè)荔枝：（下面的程序創(chuàng)建了兩個(gè) Item 對(duì)象的樹集， 第一個(gè)按照部件編號(hào)排序， 這是Item對(duì)象的默認(rèn)順序。第二個(gè)通過(guò)使用一個(gè)定制的比較器來(lái)按照描述信息排序-）

---

Complementary）我們給出 Integer 源碼 的 Comparatable 實(shí)現(xiàn)：

---

java.lang.Comparable<T> 1.2 int compareTo(T other) ：將this 和 other 進(jìn)行比較， 返回　正值、負(fù)值和０；java.util.Comparator<T> 1.2 int compare(T a, T b)： 將a 和 b進(jìn)行比較， 返回　正值、負(fù)值和０；java.util.SortedSet<T> 1.2 Comparator<? super E> comparator() ：返回用于對(duì)元素進(jìn)行排序的比較器， 如果元素用 Comparable 接口的compareTo 方法比較則返回 null； E first(); E last(); 返回有序集中的最小最大元素；java.util.NavigableSet<E> 6 E higher(E value) E lower(E value) 返回大于 value 的最小元素或小于 value 的最大元素，否則返回 null；E ceiling(E value) E floor(E value) 返回大于等于 value 的最小元素或小于等于 value 的最大元素，否則返回 null；E pollFirst(E value) E pollLast(E value) 刪除并返回這個(gè)集中的最大元素或最小元素， 這個(gè)集為空時(shí)返回 null；Iterator<E> descendingIterator()：返回一個(gè)按照 遞減順序遍歷集合中元素的迭代器；java.util.TreeSet<E> 1.2 TreeSet（） ：構(gòu)造一個(gè)用于 排列 Comparable 對(duì)象的樹集； TreeSet(Comparator<? super E > c )：構(gòu)造一個(gè)樹集， 并使用指定的比較器對(duì)其中的元素進(jìn)行排序； TreeSet(SortedSet<? extends E> elements)：構(gòu)造一個(gè)樹集， 將有序集中的所有元素添加到這個(gè)樹集中， 并使用與給定集合相同的元素比較器；

總結(jié)

以上是生活随笔為你收集整理的java集合——树集（TreeSet）+对象的比较的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。