TreeMap定義
- 1 以jdk7為準(zhǔn)進行說明
package java.util;
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
}
public interface NavigableMap<K,V> extends SortedMap<K,V>{}
TreeMap繼承AbstractMap狐援，實現(xiàn)NavigableMap、Cloneable、Serializable三個接口武学。其中AbstractMap表明TreeMap為一個Map即支持key-value的集合， NavigableMap則意味著它支持一系列的導(dǎo)航方法伦意，具備針對給定搜索目標(biāo)返回最接近匹配項的導(dǎo)航方法火窒。
- 2 成員屬性
private final Comparator<? super K> comparator; //比較器
private transient Entry<K,V> root = null; //TreeMap紅-黑節(jié)點，為TreeMap的內(nèi)部類
private transient int size = 0; //容器大小
private transient int modCount = 0; //TreeMap修改次數(shù)
private static final boolean RED = false; //紅黑樹的節(jié)點顏色–紅色
private static final boolean BLACK = true; //紅黑樹的節(jié)點顏色–黑色
對于實體節(jié)點Entry是TreeMap的內(nèi)部類驮肉，是通過紅黑樹實現(xiàn)的熏矿。
紅黑樹顧名思義就是節(jié)點是紅色或者黑色的平衡二叉樹，它通過顏色的約束來維持著二叉樹的平衡离钝。對于一棵有效的紅黑樹二叉樹而言我們必須增加如下規(guī)則：
1）每個節(jié)點都只能是紅色或者黑色
2）根節(jié)點是黑色
3）每個葉節(jié)點（NIL節(jié)點票编，空節(jié)點）是黑色的。
4）如果一個結(jié)點是紅的卵渴，則它兩個子節(jié)點都是黑的慧域。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個紅色結(jié)點。
5）從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點浪读。
- 3 這些約束強制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長昔榴。
- 4 結(jié)果是這棵樹大致上是平衡的。因為操作比如插入碘橘、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例互订，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹痘拆。所以紅黑樹它是復(fù)雜而高效的仰禽，其檢索效率O(log n)。
TreeMap特點
- 1 TreeMap是非線程安全的错负。
可以采用這種方式將TreeMap設(shè)置為同步的：
Map m = Collections.synchronizedSortedMap(new TreeMap(…));
- 2 TreeMap是用鍵來進行升序順序來排序的坟瓢。通過Comparable 或 Comparator來排序。
public class Person1 implements Comparable<Person1>
{
private int age;
private String name;
public Person1(String name, int age)
{
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person1 o)
{
return this.age-o.age;
}
@Override
public String toString()
{
return name+":"+age;
}
}
測試代碼
Map<Person1,Integer> map = new TreeMap<>();
Person1 person1 = new Person1("zzh",18);
Person1 person2 = new Person1("jj",17);
Person1 person3 = new Person1("qq",19);
map.put(person1, 1);
map.put(person2, 2);
map.put(person3, 3);
for(Entry<Person1, Integer> entry:map.entrySet())
{
System.out.println(entry.getKey()+":"+entry.getValue());
}
運行結(jié)果
jj:17:2
zzh:18:1
qq:19:3
- 3 TreeMap是SortedMap接口的基于紅黑樹的實現(xiàn)犹撒。此類保證了映射按照升序順序排列關(guān)鍵字折联， 根據(jù)使用的構(gòu)造方法不同，可能會按照鍵的類的自然順序進行排序识颊，或者按照創(chuàng)建時所提供的比較器（自定義）進行排序诚镰。
public final class Person2
{
private int age;
private String name;
public Person2(String name, int age)
{
this.name = name;
this.age = age;
}
@Override
public String toString()
{
return name+":"+age;
}
//getter and setter方法省略....
}
測試代碼
Map<Person2,Integer> map2 = new TreeMap<>(new Comparator<Person2>(){
@Override
public int compare(Person2 o1, Person2 o2)
{
if(o1 == null || o2 == null)
return 0;
return o1.getAge()-o2.getAge();
}
});
Person2 p1 = new Person2("zzh",18);
Person2 p2 = new Person2("jj",17);
Person2 p3 = new Person2("qq",19);
map2.put(p1, 1);
map2.put(p2, 2);
map2.put(p3, 3);
for(Entry<Person2, Integer> entry:map2.entrySet())
{
System.out.println(entry.getKey()+":"+entry.getValue());
}
運行結(jié)果：
jj:17:2
zzh:18:1
qq:19:3
- 4 返回的迭代器都是快速失敗的
這點和HashMap一樣奕坟，所謂快速失敗就是在并發(fā)集合中，其進行迭代操作時清笨，若有其他線程對其結(jié)構(gòu)性的修改月杉，這是迭代器會立馬感知到，并且立刻拋出ConcurrentModificationException異常抠艾，而不是等待迭代完成之后才告訴你已經(jīng)出錯苛萎。 - 5 和HashMap一樣，如果插入重復(fù)的元素检号，后面的元素會覆蓋前面的腌歉。
- 6 鍵不可以為null（如果比較器對null做了處理，就可以為null）,但是值可以為null齐苛。
- 7 TreeMap提供了很多方法方便大小使用翘盖，譬如containsKey, get, put,remove，entrySet等Map通用的方法凹蜂，也包括fisrtEntry, firstKey, cellingKey, lowerKey等方法馍驯。
HashMap與TreeMap的區(qū)別
- 1 實現(xiàn)方式
HashMap:基于哈希表實現(xiàn)。使用HashMap要求添加的鍵類明確定義了hashCode（）和equals（）[可以重寫hashCode（）和equals（）],為了優(yōu)化HashMap空間的使用玛痊，您可以調(diào)優(yōu)初始容量和負(fù)載因子汰瘫。
1）HashMap（）： 構(gòu)建一個空的哈希映像
2）HashMap（Map m）： 構(gòu)建一個哈希映像，并且添加映像m的所有映射
3）HashMap（int initialCapacity）： 構(gòu)建一個擁有特定容量的空的哈希映像
4）HashMap（int initialCapacity, float loadFactor）： 構(gòu)建一個擁有特定容量和加載因子的空的哈希映像
TreeMap:基于紅黑樹實現(xiàn)卿啡。TreeMap沒有調(diào)優(yōu)選項吟吝，因為該樹總處于平衡狀態(tài)。
1）TreeMap（）：構(gòu)建一個空的映像樹
2）TreeMap（Map m）： 構(gòu)建一個映像樹颈娜，并且添加映像m中所有元素
3）TreeMap（Comparator c）： 構(gòu)建一個映像樹，并且使用特定的比較器對關(guān)鍵字進行排序
4）TreeMap（SortedMap s）： 構(gòu)建一個映像樹浙宜，添加映像樹s中所有映射官辽，并且使用與有序映像s相同的比較器排序 - 2 用途
1）HashMap：適用于在Map中插入、刪除和定位元素粟瞬。
2）TreeMap：適用于按自然順序或自定義順序遍歷鍵（key)同仆。
3）HashMap通常比TreeMap快一點（樹和哈希表的數(shù)據(jù)結(jié)構(gòu)使然），建議多使用HashMap,在需要排序的Map時候才用TreeMap.
