TreeSet
TreeSet是一個有序的集合，它的作用是提供有序的Set集合谎脯。它繼承了AbstractSet抽象類枫振，實現(xiàn)了NavigableSet<E>，Cloneable郁竟，Serializable接口。TreeSet是基于TreeMap實現(xiàn)的由境，TreeSet的元素支持2種排序方式：自然排序或者根據(jù)提供的Comparator進(jìn)行排序。
（1）TreeSet繼承于AbstractSet蓖议，并且實現(xiàn)了NavigableSet接口虏杰。
（2）TreeSet是一個包含有序的且沒有重復(fù)元素的集合，通過TreeMap實現(xiàn)勒虾。TreeSet中含有一個"NavigableMap類型的成員變量"m纺阔，而m實際上是"TreeMap的實例"。
TreeSet用法
public static void demoOne() {
TreeSet<Person> ts = new TreeSet<>();
ts.add(new Person("張三", 11));
ts.add(new Person("李四", 12));
ts.add(new Person("王五", 15));
ts.add(new Person("趙六", 21));
System.out.println(ts);
}
執(zhí)行結(jié)果：會拋出一個 異常：java.lang.ClassCastException
顯然是出現(xiàn)了類型轉(zhuǎn)換異常修然。原因在于我們需要告訴TreeSet如何來進(jìn)行比較元素笛钝，如果不指定，就會拋出這個異常
如何解決：
如何指定比較的規(guī)則愕宋，需要在自定義類(Person)中實現(xiàn)Comparable接口玻靡，并重寫接口中的compareTo方法
public class Person implements Comparable<Person> {
private String name;
private int age;
...
public int compareTo(Person o) {
return 0; //當(dāng)compareTo方法返回0的時候集合中只有一個元素
return 1; //當(dāng)compareTo方法返回正數(shù)的時候集合會怎么存就怎么取
return -1; //當(dāng)compareTo方法返回負(fù)數(shù)的時候集合會倒序存儲
}
}
為什么返回0，只會存一個元素中贝，返回-1會倒序存儲囤捻，返回1會怎么存就怎么取呢？原因在于TreeSet底層其實是一個二叉樹機(jī)構(gòu)邻寿，且每插入一個新元素(第一個除外)都會調(diào)用compareTo()方法去和上一個插入的元素作比較蝎土，并按二叉樹的結(jié)構(gòu)進(jìn)行排列。
- 如果將
compareTo()返回值寫死為0绣否，元素值每次比較誊涯，都認(rèn)為是相同的元素，這時就不再向TreeSet中插入除第一個外的新元素蒜撮。所以TreeSet中就只存在插入的第一個元素暴构。 - 如果將
compareTo()返回值寫死為1，元素值每次比較淀弹，都認(rèn)為新插入的元素比上一個元素大丹壕，于是二叉樹存儲時，會存在根的右側(cè)薇溃，讀取時就是正序排列的菌赖。 - 如果將
compareTo()返回值寫死為-1，元素值每次比較沐序，都認(rèn)為新插入的元素比上一個元素小琉用，于是二叉樹存儲時堕绩，會存在根的左側(cè)，讀取時就是倒序序排列的邑时。
示例代碼奴紧，需求：現(xiàn)在要制定TreeSet中按照String長度比較String。
//定義一個類晶丘，實現(xiàn)Comparator接口黍氮，并重寫compare()方法，
class CompareByLength implements Comparator<String> {
@Override
public int compare(String s1, String s2) { //按照字符串的長度比較
int num = s1.length() - s2.length(); //長度為主要條件
return num == 0 ? s1.compareTo(s2) : num; //內(nèi)容為次要條件
}
}
public static void demoTwo() {
//需求:將字符串按照長度排序
TreeSet<String> ts = new TreeSet<>(new CompareByLen()); //Comparator c = new CompareByLen();
ts.add("aaaaaaaa");
ts.add("z");
ts.add("wc");
ts.add("nba");
ts.add("cba");
System.out.println(ts);
}
TreeSet的部分源碼:
package java.util;
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
// 使用NavigableMap對象的key來保存Set集合的元素
private transient NavigableMap<E,Object> m;
//使用PRESENT作為Map集合中的value
private static final Object PRESENT = new Object();
// 不帶參數(shù)的構(gòu)造函數(shù)浅浮。創(chuàng)建一個空的TreeMap
//以自然排序方法創(chuàng)建一個新的TreeMap沫浆，再根據(jù)該TreeMap創(chuàng)建一個TreeSet
//使用該TreeMap的key來保存Set集合的元素
public TreeSet() {
this(new TreeMap<E,Object>());
}
// 將TreeMap賦值給 "NavigableMap對象m"
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
//以定制排序的方式創(chuàng)建一個新的TreeMap。根據(jù)該TreeMap創(chuàng)建一個TreeSet
//使用該TreeMap的key來保存set集合的元素
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<E,Object>(comparator));
}
// 創(chuàng)建TreeSet滚秩，并將集合c中的全部元素都添加到TreeSet中
public TreeSet(Collection<? extends E> c) {
this();
// 將集合c中的元素全部添加到TreeSet中
addAll(c);
}
// 創(chuàng)建TreeSet专执，并將s中的全部元素都添加到TreeSet中
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
// 返回TreeSet的順序排列的迭代器。
// 因為TreeSet時TreeMap實現(xiàn)的郁油，所以這里實際上時返回TreeMap的“鍵集”對應(yīng)的迭代器
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
// 返回TreeSet的逆序排列的迭代器本股。
// 因為TreeSet時TreeMap實現(xiàn)的，所以這里實際上時返回TreeMap的“鍵集”對應(yīng)的迭代器
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
// 返回TreeSet的大小
public int size() {
return m.size();
}
// 返回TreeSet是否為空
public boolean isEmpty() {
return m.isEmpty();
}
// 返回TreeSet是否包含對象(o)
public boolean contains(Object o) {
return m.containsKey(o);
}
// 添加e到TreeSet中
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
// 刪除TreeSet中的對象o
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
// 清空TreeSet
public void clear() {
m.clear();
}
// 將集合c中的全部元素添加到TreeSet中
public boolean addAll(Collection<? extends E> c) {
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
//把C集合強制轉(zhuǎn)換為SortedSet集合
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
//把m集合強制轉(zhuǎn)換為TreeMap集合
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
Comparator<? super E> mc = map.comparator();
//如果cc和mc兩個Comparator相等
if (cc==mc || (cc != null && cc.equals(mc))) {
//把Collection中所有元素添加成TreeMap集合的key
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
return super.addAll(c);
}
// 返回子Set桐腌，實際上是通過TreeMap的subMap()實現(xiàn)的拄显。
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
// 返回Set的頭部，范圍是：從頭部到toElement哩掺。
// inclusive是是否包含toElement的標(biāo)志
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<E>(m.headMap(toElement, inclusive));
}
// 返回Set的尾部凿叠，范圍是：從fromElement到結(jié)尾。
// inclusive是是否包含fromElement的標(biāo)志
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<E>(m.tailMap(fromElement, inclusive));
}
// 返回子Set嚼吞。范圍是：從fromElement(包括)到toElement(不包括)盒件。
public SortedSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
// 返回Set的頭部，范圍是：從頭部到toElement(不包括)舱禽。
public SortedSet<E> headSet(E toElement) {
return headSet(toElement, false);
}
// 返回Set的尾部炒刁，范圍是：從fromElement到結(jié)尾(不包括)。
public SortedSet<E> tailSet(E fromElement) {
return tailSet(fromElement, true);
}
// 返回Set的比較器
public Comparator<? super E> comparator() {
return m.comparator();
}
// 返回Set的第一個元素
public E first() {
return m.firstKey();
}
// 返回Set的最后一個元素
public E first() {
public E last() {
return m.lastKey();
}
// 返回Set中小于e的最大元素
public E lower(E e) {
return m.lowerKey(e);
}
// 返回Set中小于/等于e的最大元素
public E floor(E e) {
return m.floorKey(e);
}
// 返回Set中大于/等于e的最小元素
public E ceiling(E e) {
return m.ceilingKey(e);
}
// 返回Set中大于e的最小元素
public E higher(E e) {
return m.higherKey(e);
}
// 獲取第一個元素誊稚，并將該元素從TreeMap中刪除翔始。
public E pollFirst() {
Map.Entry<E,?> e = m.pollFirstEntry();
return (e == null)? null : e.getKey();
}
// 獲取最后一個元素，并將該元素從TreeMap中刪除里伯。
public E pollLast() {
Map.Entry<E,?> e = m.pollLastEntry();
return (e == null)? null : e.getKey();
}
// 克隆一個TreeSet城瞎，并返回Object對象
public Object clone() {
TreeSet<E> clone = null;
try {
clone = (TreeSet<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
clone.m = new TreeMap<E,Object>(m);
return clone;
}
// java.io.Serializable的寫入函數(shù)
// 將TreeSet的“比較器、容量疾瓮，所有的元素值”都寫入到輸出流中
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
s.defaultWriteObject();
// 寫入比較器
s.writeObject(m.comparator());
// 寫入容量
s.writeInt(m.size());
// 寫入“TreeSet中的每一個元素”
for (Iterator i=m.keySet().iterator(); i.hasNext(); )
s.writeObject(i.next());
}
// java.io.Serializable的讀取函數(shù)：根據(jù)寫入方式讀出
// 先將TreeSet的“比較器脖镀、容量、所有的元素值”依次讀出
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden stuff
s.defaultReadObject();
// 從輸入流中讀取TreeSet的“比較器”
Comparator<? super E> c = (Comparator<? super E>) s.readObject();
TreeMap<E,Object> tm;
if (c==null)
tm = new TreeMap<E,Object>();
else
tm = new TreeMap<E,Object>(c);
m = tm;
// 從輸入流中讀取TreeSet的“容量”
int size = s.readInt();
// 從輸入流中讀取TreeSet的“全部元素”
tm.readTreeSet(size, s, PRESENT);
}
// TreeSet的序列版本號
private static final long serialVersionUID = -2479143000061671589L;
}
從上述可以看出狼电，TreeSet的構(gòu)造函數(shù)都是通過新建一個TreeMap作為實際存儲Set元素的容器蜒灰。因此得出結(jié)論: TreeSet的底層實際使用的存儲容器就是TreeMap弦蹂。
對于TreeMap而言，它采用一種被稱為”紅黑樹”的排序二叉樹來保存Map中每個Entry强窖。每個Entry被當(dāng)成”紅黑樹”的一個節(jié)點來對待凸椿。
對于如下代碼:
TreeMap<String,Double> map = new TreeMap<String,Double>();
map.put("ccc",89.0);
map.put("aaa",80.0);
map.put("bbb",89.0);
map.put("bbb",89.0);
如上代碼所示，程序向TreeMap放入四個值翅溺。根據(jù)”紅黑樹”的定義脑漫，程序會把”ccc,89.0”這個Entry做為該”紅黑數(shù)”的根節(jié)點，然后執(zhí)行put(“aaa”,”80.0”)時會將其作為新的節(jié)點添加到已存在的紅黑樹中未巫。也就是說窿撬，以后每次向TreeMap中放入一個key-value對，系統(tǒng)都需要將Entry當(dāng)成一個新的節(jié)點叙凡，添加到存在的”紅黑樹”中，通過這種方式就可以保證TreeMap中所有的key都是按一定順序地排列的密末。
由于TreeMap底層采用一顆”紅黑樹”來保存集合中的Entry握爷。所以TreeMap添加元素，取出元素的性能都比HashMap低。當(dāng)TreeMap添加元素時，需要通過循環(huán)找到新增的Entry的插入位置有巧，因為比較耗性能渡冻。當(dāng)取出元素時，也需要通過循環(huán)才能找到合適的Entry一樣比較耗性能酝惧。但并不是說TreeMap性能低于HashMap就一無是處，TreeMap中的所有Entry總是按key根據(jù)指定的排序規(guī)則保持有序狀態(tài)。
備注:紅黑樹是一種自平衡二叉查找樹 , 它們當(dāng)中每一個節(jié)點的比較值都必須大于或等于在它的左子樹中的所有節(jié)點物舒，并且小于或等于在它的右子樹中的所有節(jié)點。這確保紅黑樹運作時能夠快速的在樹中查找給定的值戏锹。
現(xiàn)在我們來觀察TreeMap的put(K key,V value)方法冠胯，該方法將Entry放入TreeMap的Entry鏈，并維護(hù)該Entry鏈的有序狀態(tài)锦针。下面列出源碼:
public V put(K key, V value) {
//定義一個t來保存根元素
Entry<K,V> t = root;
//如果t==null荠察，表明是一個空鏈表
if (t == null) {
//如果根節(jié)點為null，將傳入的鍵值對構(gòu)造成根節(jié)點（根節(jié)點沒有父節(jié)點奈搜，所以傳入的父節(jié)點為null）
root = new Entry<K,V>(key, value, null);
//設(shè)置該集合的size為1
size = 1;
//修改此時+1
modCount++;
return null;
}
// 記錄比較結(jié)果
int cmp;
Entry<K,V> parent;
// 分割比較器和可比較接口的處理
Comparator<? super K> cpr = comparator;
// 有比較器的處理悉盆，即采用定制排序
if (cpr != null) {
// do while實現(xiàn)在root為根節(jié)點移動尋找傳入鍵值對需要插入的位置
do {
//使用parent上次循環(huán)后的t所引用的Entry
// 記錄將要被摻入新的鍵值對將要節(jié)點(即新節(jié)點的父節(jié)點)
parent = t;
// 使用比較器比較父節(jié)點和插入鍵值對的key值的大小
cmp = cpr.compare(key, t.key);
// 插入的key較大
if (cmp < 0)
t = t.left;
// 插入的key較小
else if (cmp > 0)
t = t.right;
// key值相等，替換并返回t節(jié)點的value(put方法結(jié)束)
else
return t.setValue(value);
} while (t != null);
}
// 沒有比較器的處理
else {
// key為null拋出NullPointerException異常
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
// 與if中的do while類似馋吗，只是比較的方式不同
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 沒有找到key相同的節(jié)點才會有下面的操作
// 根據(jù)傳入的鍵值對和找到的“父節(jié)點”創(chuàng)建新節(jié)點
Entry<K,V> e = new Entry<K,V>(key, value, parent);
// 根據(jù)最后一次的判斷結(jié)果確認(rèn)新節(jié)點是“父節(jié)點”的左孩子還是又孩子
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 對加入新節(jié)點的樹進(jìn)行調(diào)整
fixAfterInsertion(e);
// 記錄size和modCount
size++;
modCount++;
// 因為是插入新節(jié)點焕盟，所以返回的是null
return null;
}
上面程序中的兩個do…while就是實現(xiàn)”排序二叉樹”的關(guān)鍵算法。每當(dāng)程序希望添加新節(jié)點時耗美，總是從樹的根節(jié)點開始比較京髓，即將根節(jié)點當(dāng)成當(dāng)前節(jié)點航缀。
- 如果新增節(jié)點大于當(dāng)前節(jié)點且當(dāng)前節(jié)點的右子節(jié)點存在，則以右子節(jié)點作為當(dāng)前節(jié)點堰怨。并繼續(xù)循環(huán)
- 如果新增節(jié)點小于當(dāng)前節(jié)點且當(dāng)前節(jié)點的左子節(jié)點存在芥玉，則以左子節(jié)點作為當(dāng)前節(jié)點。并繼續(xù)循環(huán)
- 如果新增節(jié)點等于當(dāng)前節(jié)點备图，則新增節(jié)點覆蓋當(dāng)前節(jié)點灿巧，并結(jié)束循環(huán)。
當(dāng)TreeMap根據(jù)key來取出value時揽涮，TreeMap對應(yīng)的方法如下:
public V get(Object key) {
//根據(jù)key取出Entry
Entry<K,V> p = getEntry(key);
//取出Entry所包含的value
return (p==null ? null : p.value);
}
現(xiàn)在我們可以知道抠藕，其實get(Object key)方法實質(zhì)上是由getEntry()方法實現(xiàn)的。現(xiàn)在我們來看getEntry(Object key)的源碼:
final Entry<K,V> getEntry(Object key) {
// 如果有比較器蒋困，返回getEntryUsingComparator(Object key)的結(jié)果
if (comparator != null)
return getEntryUsingComparator(key);
// 查找的key為null盾似，拋出NullPointerException
if (key == null)
throw new NullPointerException();
// 如果沒有比較器，而是實現(xiàn)了可比較接口
//將key強制轉(zhuǎn)換為Comparable接口
Comparable<? super K> k = (Comparable<? super K>) key;
// 獲取根節(jié)點
Entry<K,V> p = root;
// 從根節(jié)點開始對樹進(jìn)行遍歷查找節(jié)點
while (p != null) {
// 把key和當(dāng)前節(jié)點的key進(jìn)行比較
int cmp = k.compareTo(p.key);
// key小于當(dāng)前節(jié)點的key
if (cmp < 0)
// p “移動”到左節(jié)點上
p = p.left;
// key大于當(dāng)前節(jié)點的key
else if (cmp > 0)
// p “移動”到右節(jié)點上
p = p.right;
// key值相等則當(dāng)前節(jié)點就是要找的節(jié)點
else
// 返回找到的節(jié)點
return p;
}
// 沒找到則返回null
return null;
}
getEntry(Object obj)方法也是充分利用排序二叉樹的特性來搜索目標(biāo)Entry雪标。程序依然從二叉數(shù)的根節(jié)點開始零院，如果被搜索節(jié)點大于當(dāng)前節(jié)點，程序向”右子樹”搜索村刨，如果小于告抄，則向”左子樹”搜索。如果相等則說明找到了指定節(jié)點嵌牺。
我們觀察到當(dāng)該TreeMap采用了定制排序打洼。在采用定制排序的方式下，TreeMap采用getEntryUsingComparator(key)方法來根據(jù)key獲取Entry逆粹。
final Entry<K,V> getEntryUsingComparator(Object key) {
K k = (K) key;
// 獲取比較器
Comparator<? super K> cpr = comparator;
// 其實在調(diào)用此方法的get(Object key)中已經(jīng)對比較器為null的情況進(jìn)行判斷募疮，這里是防御性的判斷
if (cpr != null) {
// 獲取根節(jié)點
Entry<K,V> p = root;
// 遍歷樹
while (p != null) {
// 獲取key和當(dāng)前節(jié)點的key的比較結(jié)果
int cmp = cpr.compare(k, p.key);
// 查找的key值較小
if (cmp < 0)
// p“移動”到左孩子
p = p.left;
// 查找的key值較大
else if (cmp > 0)
// p“移動”到右節(jié)點
p = p.right;
// key值相等
else
// 返回找到的節(jié)點
return p;
}
}
// 沒找到key值對應(yīng)的節(jié)點，返回null
return null;
}
其實getEntry()和getEntryUsingComparator()這兩個方法實現(xiàn)思路幾乎完全類似枯饿。只是前者對自然排序的TreeMap獲取有效酝锅，后者對定制排序的TreeMap有效。
通過上述源碼其實不難看出奢方，TreeMap這個工具類的實現(xiàn)其實很簡單搔扁。或者說蟋字，從本質(zhì)上來說TreeMap就是一棵”紅黑樹”稿蹲，每個Entry就是一個節(jié)點。
總結(jié)
1鹊奖、不能有重復(fù)的元素苛聘；
2、具有排序功能；
3设哗、TreeSet中的元素必須實現(xiàn)Comparable接口并重寫compareTo()方法唱捣，TreeSet判斷元素是否重復(fù) 、以及確定元素的順序 靠的都是這個方法网梢；
①對于Java類庫中定義的類震缭，TreeSet可以直接對其進(jìn)行存儲，如String战虏，Integer等,因為這些類已經(jīng)實現(xiàn)了Comparable接口);
②對于自定義類拣宰，如果不做適當(dāng)?shù)奶幚恚琓reeSet中只能存儲一個該類型的對象實例烦感，否則無法判斷是否重復(fù)巡社。
4、依賴TreeMap手趣。
5晌该、相對HashSet,TreeSet的優(yōu)勢是有序，劣勢是相對讀取慢绿渣。根據(jù)不同的場景選擇不同的集合气笙。
