摘要：當(dāng)往中放入新的鍵值對(duì)后，可能會(huì)破壞紅黑樹的性質(zhì)。修復(fù)操作要重新使紅黑樹恢復(fù)平衡，修復(fù)操作的源碼分析如下方法分析如下上面對(duì)部分代碼邏輯就行了分析，通過配圖的形式解析了每段代碼邏輯所處理的情況。四總結(jié)本文可以看做是本人紅黑樹詳細(xì)分析一文的延續(xù)。
一、簡(jiǎn)介
TreeMap最早出現(xiàn)在JDK 1.2中，是 Java 集合框架中比較重要一個(gè)的實(shí)現(xiàn)。TreeMap 底層基于紅黑樹實(shí)現(xiàn)，可保證在log(n)時(shí)間復(fù)雜度內(nèi)完成 containsKey、get、put 和 remove 操作，效率很高。另一方面，由于 TreeMap 基于紅黑樹實(shí)現(xiàn)，這為 TreeMap 保持鍵的有序性打下了基礎(chǔ)。總的來說，TreeMap 的核心是紅黑樹，其很多方法也是對(duì)紅黑樹增刪查基礎(chǔ)操作的一個(gè)包裝。所以只要弄懂了紅黑樹，TreeMap 就沒什么秘密了。
二、概覽
TreeMap繼承自AbstractMap，并實(shí)現(xiàn)了 NavigableMap接口。NavigableMap 接口繼承了SortedMap接口，SortedMap 最終繼承自Map接口，同時(shí) AbstractMap 類也實(shí)現(xiàn)了 Map 接口。以上就是 TreeMap 的繼承體系，描述起來有點(diǎn)亂，不如看圖了：
上圖就是 TreeMap 的繼承體系圖，比較直觀。這里來簡(jiǎn)單說一下繼承體系中不常見的接口NavigableMap和SortedMap，這兩個(gè)接口見名知意。先說 NavigableMap 接口，NavigableMap 接口聲明了一些列具有導(dǎo)航功能的方法，比如：
/**
* 返回紅黑樹中最小鍵所對(duì)應(yīng)的 Entry
*/
Map.Entry firstEntry();
/**
* 返回最大的鍵 maxKey，且 maxKey 僅小于參數(shù) key
*/
K lowerKey(K key);
/**
* 返回最小的鍵 minKey，且 minKey 僅大于參數(shù) key
*/
K higherKey(K key);
// 其他略
通過這些導(dǎo)航方法，我們可以快速定位到目標(biāo)的 key 或 Entry。至于 SortedMap 接口，這個(gè)接口提供了一些基于有序鍵的操作，比如
/**
* 返回包含鍵值在 [minKey, toKey) 范圍內(nèi)的 Map
*/
SortedMap headMap(K toKey);();
/**
* 返回包含鍵值在 [fromKey, toKey) 范圍內(nèi)的 Map
*/
SortedMap subMap(K fromKey, K toKey);
// 其他略
以上就是兩個(gè)接口的介紹，很簡(jiǎn)單。至于 AbstractMap 和 Map 這里就不說了，大家有興趣自己去看看 Javadoc 吧。關(guān)于 TreeMap 的繼承體系就這里就說到這，接下來我們進(jìn)入細(xì)節(jié)部分分析。
三、源碼分析
JDK 1.8中的TreeMap源碼有兩千多行，還是比較多的。本文并不打算逐句分析所有的源碼，而是挑選幾個(gè)常用的方法進(jìn)行分析。這些方法實(shí)現(xiàn)的功能分別是查找、遍歷、插入、刪除等，其他的方法小伙伴們有興趣可以自己分析。TreeMap實(shí)現(xiàn)的核心部分是關(guān)于紅黑樹的實(shí)現(xiàn)，其絕大部分的方法基本都是對(duì)底層紅黑樹增、刪、查操作的一個(gè)封裝。如簡(jiǎn)介一節(jié)所說，只要弄懂了紅黑樹原理，TreeMap 就沒什么秘密了。關(guān)于紅黑樹的原理，請(qǐng)參考本人的另一篇文章-紅黑樹詳細(xì)分析，本篇文章不會(huì)對(duì)此展開討論。
3.1 查找
TreeMap基于紅黑樹實(shí)現(xiàn)，而紅黑樹是一種自平衡二叉查找樹，所以 TreeMap 的查找操作流程和二叉查找樹一致。二叉樹的查找流程是這樣的，先將目標(biāo)值和根節(jié)點(diǎn)的值進(jìn)行比較，如果目標(biāo)值小于根節(jié)點(diǎn)的值，則再和根節(jié)點(diǎn)的左孩子進(jìn)行比較。如果目標(biāo)值大于根節(jié)點(diǎn)的值，則繼續(xù)和根節(jié)點(diǎn)的右孩子比較。在查找過程中，如果目標(biāo)值和二叉樹中的某個(gè)節(jié)點(diǎn)值相等，則返回 true，否則返回 false。TreeMap 查找和此類似，只不過在 TreeMap 中，節(jié)點(diǎn)（Entry）存儲(chǔ)的是鍵值對(duì)。在查找過程中，比較的是鍵的大小，返回的是值，如果沒找到，則返回null。TreeMap 中的查找方法是get，具體實(shí)現(xiàn)在getEntry方法中，相關(guān)源碼如下：
public V get(Object key) {
Entry p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry 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 k = (Comparable) key;
Entry p = root;
// 查找操作的核心邏輯就在這個(gè) while 循環(huán)里
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;
}
查找操作的核心邏輯就是getEntry方法中的while循環(huán)，大家對(duì)照上面的說的流程，自己看一下吧，比較簡(jiǎn)單，就不多說了。
3.2 遍歷
遍歷操作也是大家使用頻率較高的一個(gè)操作，對(duì)于TreeMap，使用方式一般如下：
for(Object key : map.keySet()) {
// do something
}
或
for(Map.Entry entry : map.entrySet()) {
// do something
}
從上面代碼片段中可以看出，大家一般都是對(duì) TreeMap 的 key 集合或 Entry 集合進(jìn)行遍歷。上面代碼片段中用 foreach 遍歷 keySet 方法產(chǎn)生的集合，在編譯時(shí)會(huì)轉(zhuǎn)換成用迭代器遍歷，等價(jià)于：
Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
Object key = ite.next();
// do something
}
另一方面，TreeMap 有一個(gè)特性，即可以保證鍵的有序性，默認(rèn)是正序。所以在遍歷過程中，大家會(huì)發(fā)現(xiàn) TreeMap 會(huì)從小到大輸出鍵的值。那么，接下來就來分析一下keySet方法，以及在遍歷 keySet 方法產(chǎn)生的集合時(shí)，TreeMap 是如何保證鍵的有序性的。相關(guān)代碼如下：
public Set keySet() {
return navigableKeySet();
}
public NavigableSet navigableKeySet() {
KeySet nks = navigableKeySet;
return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}
static final class KeySet extends AbstractSet implements NavigableSet {
private final NavigableMap m;
KeySet(NavigableMap map) { m = map; }
public Iterator iterator() {
if (m instanceof TreeMap)
return ((TreeMap)m).keyIterator();
else
return ((TreeMap.NavigableSubMap)m).keyIterator();
}
// 省略非關(guān)鍵代碼
}
Iterator keyIterator() {
return new KeyIterator(getFirstEntry());
}
final class KeyIterator extends PrivateEntryIterator {
KeyIterator(Entry first) {
super(first);
}
public K next() {
return nextEntry().key;
}
}
abstract class PrivateEntryIterator implements Iterator {
Entry next;
Entry lastReturned;
int expectedModCount;
PrivateEntryIterator(Entry first) {
expectedModCount = modCount;
lastReturned = null;
next = first;
}
public final boolean hasNext() {
return next != null;
}
final Entry nextEntry() {
Entry e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// 尋找節(jié)點(diǎn) e 的后繼節(jié)點(diǎn)
next = successor(e);
lastReturned = e;
return e;
}
// 其他方法省略
}
上面的代碼比較多，keySet 涉及的代碼還是比較多的，大家可以從上往下看。從上面源碼可以看出 keySet 方法返回的是KeySet類的對(duì)象。這個(gè)類實(shí)現(xiàn)了Iterable接口，可以返回一個(gè)迭代器。該迭代器的具體實(shí)現(xiàn)是KeyIterator，而 KeyIterator 類的核心邏輯是在PrivateEntryIterator中實(shí)現(xiàn)的。上面的代碼雖多，但核心代碼還是 KeySet 類和 PrivateEntryIterator 類的 nextEntry方法。KeySet 類就是一個(gè)集合，這里不分析了。而 nextEntry 方法比較重要，下面簡(jiǎn)單分析一下。
在初始化 KeyIterator 時(shí)，會(huì)將 TreeMap 中包含最小鍵的 Entry 傳給 PrivateEntryIterator。當(dāng)調(diào)用 nextEntry 方法時(shí)，通過調(diào)用 successor 方法找到當(dāng)前 entry 的后繼，并讓 next 指向后繼，最后返回當(dāng)前的 entry。通過這種方式即可實(shí)現(xiàn)按正序返回鍵值的的邏輯。
好了，TreeMap 的遍歷操作就講到這。遍歷操作本身不難，但講的有點(diǎn)多，略顯啰嗦，大家見怪。
3.3 插入
相對(duì)于前兩個(gè)操作，插入操作明顯要復(fù)雜一些。當(dāng)往 TreeMap 中放入新的鍵值對(duì)后，可能會(huì)破壞紅黑樹的性質(zhì)。這里為了描述方便，把 Entry 稱為節(jié)點(diǎn)。并把新插入的節(jié)點(diǎn)稱為N，N 的父節(jié)點(diǎn)為P。P 的父節(jié)點(diǎn)為G，且 P 是 G 的左孩子。P 的兄弟節(jié)點(diǎn)為U。在往紅黑樹中插入新的節(jié)點(diǎn) N 后（新節(jié)點(diǎn)為紅色），會(huì)產(chǎn)生下面5種情況：
N 是根節(jié)點(diǎn)
N 的父節(jié)點(diǎn)是黑色
N 的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)也是紅色
N 的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且 N 是 P 的右孩子
N 的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且 N 是 P 的左孩子
上面5中情況中，情況2不會(huì)破壞紅黑樹性質(zhì)，所以無需處理。情況1 會(huì)破壞紅黑樹性質(zhì)2（根是黑色），情況3、4、和5會(huì)破壞紅黑樹性質(zhì)4（每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)）。這個(gè)時(shí)候就需要進(jìn)行調(diào)整，以使紅黑樹重新恢復(fù)平衡。至于怎么調(diào)整，可以參考我另一篇關(guān)于紅黑樹的文章（紅黑樹詳細(xì)分析），這里不再重復(fù)說明。接下來分析一下插入操作相關(guān)源碼：
public V put(K key, V value) {
Entry t = root;
// 1.如果根節(jié)點(diǎn)為 null，將新節(jié)點(diǎn)設(shè)為根節(jié)點(diǎn)
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry parent;
// split comparator and comparable paths
Comparator cpr = comparator;
if (cpr != null) {
// 2.為 key 在紅黑樹找到合適的位置
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 {
// 與上面代碼邏輯類似，省略
}
Entry e = new Entry<>(key, value, parent);
// 3.將新節(jié)點(diǎn)鏈入紅黑樹中
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 4.插入新節(jié)點(diǎn)可能會(huì)破壞紅黑樹性質(zhì)，這里修正一下
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
put 方法代碼如上，邏輯和二叉查找樹插入節(jié)點(diǎn)邏輯一致。重要的步驟我已經(jīng)寫了注釋，并不難理解。插入邏輯的復(fù)雜之處在于插入后的修復(fù)操作，對(duì)應(yīng)的方法fixAfterInsertion，該方法的源碼和說明如下：
到這里，插入操作就講完了。接下來，來說說 TreeMap 中最復(fù)雜的部分，也就是刪除操作了。
3.4 刪除
刪除操作是紅黑樹最復(fù)雜的部分，原因是該操作可能會(huì)破壞紅黑樹性質(zhì)5（從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)），修復(fù)性質(zhì)5要比修復(fù)其他性質(zhì)（性質(zhì)2和4需修復(fù)，性質(zhì)1和3不用修復(fù)）復(fù)雜的多。當(dāng)刪除操作導(dǎo)致性質(zhì)5被破壞時(shí)，會(huì)出現(xiàn)8種情況。為了方便表述，這里還是先做一些假設(shè)。我們把最終被刪除的節(jié)點(diǎn)稱為 X，X 的替換節(jié)點(diǎn)稱為 N。N 的父節(jié)點(diǎn)為P，且 N 是 P 的左孩子。N 的兄弟節(jié)點(diǎn)為S，S 的左孩子為 SL，右孩子為 SR。這里特地強(qiáng)調(diào) X 是 最終被刪除 的節(jié)點(diǎn)，是原因二叉查找樹會(huì)把要?jiǎng)h除有兩個(gè)孩子的節(jié)點(diǎn)的情況轉(zhuǎn)化為刪除只有一個(gè)孩子的節(jié)點(diǎn)的情況，該節(jié)點(diǎn)是欲被刪除節(jié)點(diǎn)的前驅(qū)和后繼。
接下來，簡(jiǎn)單列舉一下刪除節(jié)點(diǎn)時(shí)可能會(huì)出現(xiàn)的情況，先列舉較為簡(jiǎn)單的情況：
最終被刪除的節(jié)點(diǎn) X 是紅色節(jié)點(diǎn)
X 是黑色節(jié)點(diǎn)，但該節(jié)點(diǎn)的孩子節(jié)點(diǎn)是紅色
比較復(fù)雜的情況：
替換節(jié)點(diǎn) N 是新的根
N 為黑色，N 的兄弟節(jié)點(diǎn) S 為紅色，其他節(jié)點(diǎn)為黑色。
N 為黑色，N 的父節(jié)點(diǎn) P，兄弟節(jié)點(diǎn) S 和 S 的孩子節(jié)點(diǎn)均為黑色。
N 為黑色，P 是紅色，S 和 S 孩子均為黑色。
N 為黑色，P 可紅可黑，S 為黑色，S 的左孩子 SL 為紅色，右孩子 SR 為黑色
N 為黑色，P 可紅可黑，S 為黑色，SR 為紅色，SL 可紅可黑
上面列舉的8種情況中，前兩種處理起來比較簡(jiǎn)單，后6種情況中情況2~6較為復(fù)雜。接下來我將會(huì)對(duì)情況2~6展開分析，刪除相關(guān)的源碼如下：
public V remove(Object key) {
Entry p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry p) {
modCount++;
size--;
/*
* 1. 如果 p 有兩個(gè)孩子節(jié)點(diǎn)，則找到后繼節(jié)點(diǎn)，
* 并把后繼節(jié)點(diǎn)的值復(fù)制到節(jié)點(diǎn) P 中，并讓 p 指向其后繼節(jié)點(diǎn)
*/
if (p.left != null && p.right != null) {
Entry 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 replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
/*
* 2. 將 replacement parent 引用指向新的父節(jié)點(diǎn)，
* 同時(shí)讓新的父節(jié)點(diǎn)指向 replacement。
*/
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;
// 3. 如果刪除的節(jié)點(diǎn) p 是黑色節(jié)點(diǎn)，則需要進(jìn)行調(diào)整
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // 刪除的是根節(jié)點(diǎn)，且樹中當(dāng)前只有一個(gè)節(jié)點(diǎn)
root = null;
} else { // 刪除的節(jié)點(diǎn)沒有孩子節(jié)點(diǎn)
// p 是黑色，則需要進(jìn)行調(diào)整
if (p.color == BLACK)
fixAfterDeletion(p);
// 將 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;
}
}
}
從源碼中可以看出，remove方法只是一個(gè)簡(jiǎn)單的保證，核心實(shí)現(xiàn)在deleteEntry方法中。deleteEntry 主要做了這么幾件事：
如果待刪除節(jié)點(diǎn) P 有兩個(gè)孩子，則先找到 P 的后繼 S，然后將 S 中的值拷貝到 P 中，并讓 P 指向 S
如果最終被刪除節(jié)點(diǎn) P（P 現(xiàn)在指向最終被刪除節(jié)點(diǎn)）的孩子不為空，則用其孩子節(jié)點(diǎn)替換掉
如果最終被刪除的節(jié)點(diǎn)是黑色的話，調(diào)用 fixAfterDeletion 方法進(jìn)行修復(fù)
上面說了 replacement 不為空時(shí)，deleteEntry 的執(zhí)行邏輯。上面說的略微啰嗦，如果簡(jiǎn)單說的話，7個(gè)字即可總結(jié)：找后繼 -> 替換 -> 修復(fù)。這三步中，最復(fù)雜的是修復(fù)操作。修復(fù)操作要重新使紅黑樹恢復(fù)平衡，修復(fù)操作的源碼分析如下：
fixAfterDeletion 方法分析如下：
上面對(duì) fixAfterDeletion 部分代碼邏輯就行了分析，通過配圖的形式解析了每段代碼邏輯所處理的情況。通過圖解，應(yīng)該還是比較好理解的。好了，TreeMap 源碼先分析到這里。
四、總結(jié)
本文可以看做是本人”紅黑樹詳細(xì)分析”一文的延續(xù)。前一篇文章從理論層面上詳細(xì)分析了紅黑樹插入和刪除操作可能會(huì)導(dǎo)致的問題，以及如何修復(fù)。本文則從實(shí)踐層面是分析了插入和刪除操作在具體的實(shí)現(xiàn)中時(shí)怎樣做的。另外，本文選擇了從集合框架常用方法這一角度進(jìn)行分析，詳細(xì)分析了查找、遍歷、插入和刪除等方法。總體來說，分析的還是比較詳細(xì)的。當(dāng)然限于本人的水平，文中可能會(huì)存在一些錯(cuò)誤的論述。如果大家發(fā)現(xiàn)了，歡迎指出來。如果這些錯(cuò)誤的論述對(duì)你造成了困擾，我這里先說聲抱歉。如果你也在學(xué)習(xí) TreeMap 源碼，希望這篇文章能夠幫到你。
最后感謝大家花時(shí)間的閱讀我的文章，順祝大家寫代碼無BUG，下篇文章見。
本文在知識(shí)共享許可協(xié)議 4.0 下發(fā)布，轉(zhuǎn)載請(qǐng)注明出處
作者：coolblog
為了獲得更好的分類閱讀體驗(yàn)，
請(qǐng)移步至本人的個(gè)人博客：http://www.coolblog.xyz
本作品采用知識(shí)共享署名-非商業(yè)性使用-禁止演繹 4.0 國(guó)際許可協(xié)議進(jìn)行許可。
