本系列文章所描述的所有類或接口都是基于 JDK 1.7的源碼，在其它 JDK 的實現(xiàn)方式中可能會有所不同弹囚。
一、實現(xiàn)方式
TreeMap 是一個支持排序的 Map 實現(xiàn)狼犯，其實現(xiàn)方式和 HashMap 并不相同。
二悯森、創(chuàng)建 TreeMap
在此步 TreeMap 只是將 comparator 屬性賦值為 null，如希望控制 TreeMap 中元素的存儲順序瓢姻，可使用帶 Comparator 參數(shù)的構(gòu)造器祝蝠。
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
三、添加元素 put(Object key, Object value)
當(dāng)調(diào)用 put 時，先要判斷 root 屬性是否為 null绎狭，如是，則創(chuàng)建一個新的 Entry 對象喇聊，并賦值給 root 屬性蹦狂。如不是，則首先判斷是否傳入了指定的 Comparator 實現(xiàn)凯楔，如已傳入，則基于紅黑樹的方式遍歷摆屯，基于 comparator 來比較 key 應(yīng)放在樹的左邊還是右邊，如找到相等的 key准验，則直接替換其 value富弦，并返回結(jié)束 put 操作沟娱，如沒有找到相等的 key腕柜，則一直尋找到左邊或右邊節(jié)點為 null 的元素，如 comparator 實現(xiàn)為 null砰蠢，則判斷 key 是否為 null唉铜，是則拋出 NullPointerException，否則將 key 轉(zhuǎn)化為 Comparable潭流，進(jìn)行與上面同樣的遍歷和比較過程。
通過上面的步驟拆宛，如未找到相同的 key，則進(jìn)入以下過程讼撒，即創(chuàng)建一個新的 Entry 對象股耽，并將其 parent 設(shè)置為上面所尋找到的元素钳幅，并根據(jù)和 parent key 比較的情況來設(shè)置 parent 的 left 或 right 屬性。
綜上所述敢艰，TreeMap 是一個典型的基于紅黑樹的實現(xiàn)，因此它要求一定要有 key 比較的方法丽惭，要么傳入 Comparator 實現(xiàn)辈双，要么 key 對象實現(xiàn) Comparator 接口柜砾。
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
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);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
四、獲取元素 get(Object)
TreeMap 在查找 key 時就是個典型的紅黑樹查找過程证芭，從根對象開始往下比較担映，一直找到相等的 key，并返回其 value蝇完。
和 put 時同樣的處理方式，如未傳入 Comparator 實現(xiàn)氢架，當(dāng)傳入的 Object 為 null 時朋魔，則直接拋出 NullPointerException。
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
五孙援、刪除元素 remove(Object)
remove 首先要做的是 getEntry扇雕，然后則是將此 Entry 從紅黑樹上刪除，并重新調(diào)整樹上的相關(guān)的節(jié)點洼裤。
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
六溪王、判斷元素是否存在 containsKey(Object)
和 get 方法一樣值骇，都通過 getEntry 方法來完成，因此過程和 get 方法一樣道伟，只是 containsKey 直接判斷返回的 Entry 是否為 null使碾，為 null 則返回 false，不為 null 則返回 true票摇。
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
七、遍歷元素 keySet()
調(diào)用 keySet 方法后返回 TreeMap 的內(nèi)部類 KeySet 對象的實例盆色，iterator 的遍歷從根開始祟剔，基于紅黑樹順序完成。
public Set<K> keySet() {
return navigableKeySet();
}
八物延、注意要點
對 TreeMap 而言，最應(yīng)了解的有以下幾點：
- TreeMap 基于紅黑樹實現(xiàn)浑吟，無容量限制案训；
- TreeMap 是非線程安全的。
