大家好，今天我們來學習一下Map家族中的另一個成員：TreeMap。
一、基本概念
在介紹TreeMap之前，我們來了解一種資料結構：二叉樹。相信學過資料結構的同學知道，這種結構的資料存儲形式在查找的時候效率非常高。
二叉樹結構（源自百度百科）
二叉樹結構又可再細分為二叉查找樹 叉平衡樹
二叉查找樹
二叉查找樹是一種有序的樹，所有的左孩子的value值都是小于葉子結點的value值的，所有右孩子的value值都是大于葉子結點的。這樣做的好處在于：如果需要按照鍵值查找資料元素，隻要比較目前結點的value值即可（小于目前結點value值的，往左走，否則往右走），這種方式，每次可以減少一半的操作，是以效率比較高。
比二叉查找樹更進一步的是二叉平衡樹，二叉平衡樹除了保證有序外，還能夠保持每個節點左右子樹的高度相差不超過1。常見的平衡樹有AVL樹，Treap，紅黑樹，伸展樹，等等。
紅黑樹是在每個節點上增加一個存儲位表示節點的顔色，可以是RED或BLACK。通過對任何一條從根到葉子的路徑上各個節點着色方式的限制，紅黑樹確定沒有一條路徑會比其他路徑長出兩倍，因而是接近平衡的。
在TreeMap中，即是使用了紅黑樹。(上篇文章的末尾，我們提到了HashMap在一個數組槽位裡連結清單長度過長時，也會把連結清單轉為紅黑樹來存儲資料）
二、構造函數
先來看下TreeMap的構造方法。TreeMap一共有4個構造方法。
1、無參構造方法
public TreeMap() {comparator = null;}
采用無參構造方法，不指定比較器，這時候，排序的實作要依賴key.compareTo()方法，是以key必須實作Comparable接口，并覆寫其中的compareTo方法。
2、帶有比較器的構造方法
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
采用帶比較器的構造方法，這時候，排序依賴該比較器，key可以不用實作Comparable接口。
3、帶Map的構造方法
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
該構造方法同樣不指定比較器，調用putAll方法将Map中的所有元素加入到TreeMap中。putAll的源碼如下：
// 将map中的全部節點添加到TreeMap中
public void putAll(Map<? extends K, ? extends V> map) {
// 擷取map的大小
int mapSize = map.size();
// 如果TreeMap的大小是0,且map的大小不是0,且map是已排序的“key-value對”
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator c = ((SortedMap)map).comparator();
// 如果TreeMap和map的比較器相等；
// 則将map的元素全部拷貝到TreeMap中，然後傳回！
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
// 調用AbstractMap中的putAll();
// AbstractMap中的putAll()又會調用到TreeMap的put()
super.putAll(map);
}
顯然，如果Map裡的元素是排好序的，就調用buildFromSorted方法來拷貝Map中的元素，這在下一個構造方法中會重點提及，而如果Map中的元素不是排好序的，就調用AbstractMap的putAll(map)方法，該方法源碼如下：
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
很明顯它是将Map中的元素一個個put（插入）到TreeMap中的，主要因為Map中的元素是無序存放的，是以要一個個插入到紅黑樹中，使其有序存放，并滿足紅黑樹的性質。
4、帶有SortedMap的構造方法
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) {
}
}
首先将比較器指定為m的比較器，這取決于生成m時調用構造方法是否傳入了指定的構造器，而後調用buildFromSorted方法，将SortedMap中的元素插入到TreeMap中，由于SortedMap中的元素師有序的，實際上它是根據SortedMap建立的TreeMap，将SortedMap中對應的元素添加到TreeMap中。
三、内部存儲的基本原理
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int modCount = 0;
//靜态成員内部類 從源碼中摘取部分代碼，能說明内部結構即可
static final class Entry<K,V> implements Map.Entry<K,V> {
// 鍵
K key;
// 值
V value;
// 左孩子
Entry<K,V> left = null;
// 右孩子
Entry<K,V> right = null;
// 父節點
Entry<K,V> parent;
// 目前節點顔色
boolean color = BLACK;
// 構造函數
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
從代碼中，我們可以很容易的看出來，内部包含一個 comparator 比較器（或值被置為Key的比較器，或是被置為外部傳入的比較器），根結點 root （指向紅黑樹的根節點），記錄修改次數 modCount （用于對集合結構性的檢查），還有一個靜态内部類（其實可以了解為一個樹結點），其中有存儲鍵和值的key和value，還有指向左孩子和右孩子的“指針”，還有指向父結點的“指針”，最後還包括一個标志 color。也就是說，一個root指向樹的根節點，而這個根結點又連結為一棵樹，最後通過這個root可以周遊整個樹。
四、put添加元素到集合中
在了解了TreeMap的内部結構之後，我們可以看看他是怎麼将一個元素結點挂到整棵樹上的。
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;
// 找出(key, value)在二叉排序樹中的插入位置。
// 紅黑樹是以key來進行排序的，是以這裡以key來進行查找。
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();
@SuppressWarnings("unchecked")
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);
}
// 為（key-value）建立節點
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 插入新的節點後，調用fixAfterInsertion調整紅黑樹。
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
首先判斷根結點是否是空的，如果是空的直接建立一個結點并将parent賦null，将其作為該樹的根節點，傳回null跳過餘下代碼。如果跟結點不是空的，就去判斷 comparator 是否為null（也就是判斷comparator的值是預設key的比較器還是外部傳入的比較器），如果comparator的值是外部傳入的，通過循環比較key的值計算将要添加的結點的位置（過程中如果發現有某個結點的key值和将要添加的key的值相等，說明這是修改操作，修改其value值傳回舊value值）。
如果在建立對象的時候并沒有從外部傳入比較器，首先判斷key的值是否為null（如果是就抛出空指針異常），那有人說：為什麼要對key是否為空做判斷呢？上面不是也沒有做判斷麼？ 答案是：如果 comparator 是外部傳入的，那麼沒問題，但是如果是key的預設比較器，那如果key為null 還要調用比價器 必然抛空指針異常。接下來做的事情和上面一樣的。
程式執行到最後了，我們要知道一點的是：parent指向的是最後一個結點也就是我們将要添加的結點的父結點。最後根據key和value和parent建立一個節點，然後根據上面的判斷确定此結點是左孩子還是右孩子。
這個方法中有一個 fixAfterInsertion(e); 調用這個函數可以将我們剛剛建立完成之後的樹通過挪動重新建構成紅黑樹。
最後總結一下整個put方法的執行過程：
- 判斷此樹是否是空的，空樹的操作就很簡單了
- 判斷比較器的來源做不同的操作（比較value值确定位置）
- 建構新結點挂上樹
- 調用方法重構紅黑樹
其中，我們要區分一點的是，為什麼有時候傳回的null，有時候傳回的是舊結點的value，主要差別還是在于，put方法作為添加元素和修改元素的兩種功能，添加元素的時候統一傳回的是null，修改元素的時候統一傳回的是别修改之前的元素的value。
五、根據鍵的值删除結點元素
了解完put操作的實作後，我們再來看删除操作的實作。首先看remove方法：
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
删除的操作主要是兩個操作的結合，一是擷取指定元素getEntry(key)，一個是删除指定元素deleteEntry(p)。我們先看如何擷取指定元素。
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();
@SuppressWarnings("unchecked")
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;
}
這段代碼不難了解，依然是根據比較器的來源分兩種情況（由于兩種情況下的處理方式類似，此處指具體說其中一種），p指向根結點root，循環周遊，比較key和目前循環到的key是否相等，不相等就根據大小向左或者向右，如果相等執行return p; 傳回此結點。如果整棵樹周遊完成之後，沒有找到指定鍵值的結點就會傳回null表示未找到該結點。這就是查找方法。
下面我們看看删除指定結點的方法。
在看代碼之前我們先了解一下整體的思路，将要删除的結點可能有以下三種情況：
- 該結點為葉子結點，即無左孩子和右孩子
- 該結點隻有一個孩子結點
- 該結點有兩個孩子結點
第一種情況，直接将該結點删除，并将父結點的對應引用指派為null
第二種情況，跳過該結點将其父結點指向這個孩子結點
情況二
第三種情況，找到待删結點的後繼結點将後繼結點替換到待删結點并删除後繼結點（删除方式和第二種情況一樣）
情況三
下面我們看代碼：
/*代碼雖多，我們一點一點看*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
首先，判斷待删結點是否具有兩個孩子，如果有，調用函數 successor傳回後繼結點，就是大于待删除節點中最小的那個節點
源碼如下：
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
對于這條語句：Entry>K,V< replacement = (p.left != null ? p.left : p.right); ，我們上述的三種情況下replacement的取值值得研究，如果是第一種情況（葉子結點），那麼replacement取值為null，進入下面的判斷，第一個if過，第二個判斷待删結點是否是根結點（隻有根結點的父結點為null），如果是說明整個樹隻有一個結點，那麼直接删除即可，如果不是根結點就說明是葉子結點，此時将父結點指派為null然後删除即可。
對于第二種情況下（隻有一個孩子結點時候），最上面的if語句是不做的，如果那一個結點是左孩子 replacement為該結點，然後将此結點跳過父結點挂在待删結點的下面，如果那一個孩子是右孩子，replacement為該結點，同樣操作。
第三種情況（待删結點具有兩個孩子結點），那肯定執行最最上面的if語句中代碼，找到後繼結點替換待删結點（後繼結點一定沒有左孩子），成功的将問題轉換為删除後繼結點，又因為後繼結點一定沒有左孩子，整個問題已經被轉換成上述兩種情況了，（假如後繼結點沒有右孩子就是第一種，假如有就是第二種）是以replacement = p.right，下面分情況處理。删除方法結束。
本文對TreeMap的分析淺嘗辄止，TreeMap用的沒有HashMap那麼多，我們有個宏觀上的把握和比較即可。
1、TreeMap是根據key進行排序的，它的排序和定位需要依賴比較器或覆寫Comparable接口，也是以不需要key覆寫hashCode方法和equals方法，就可以排除掉重複的key，而HashMap的key則需要通過覆寫hashCode方法和equals方法來確定沒有重複的key。
2、TreeMap的查詢、插入、删除效率均沒有HashMap高，一般隻有要對key排序時才使用TreeMap。
3、TreeMap的key不能為null，而HashMap的key可以為null。
注：對TreeSet和HashSet的源碼不再進行剖析，二者分别是基于TreeMap和HashMap實作的，隻是對應的節點中隻有key，而沒有value，是以對TreeMap和HashMap比較了解的話，對TreeSet和HashSet的了解就會非常容易。