上期回顧

上期我從樹型結(jié)構(gòu)談到了紅黑樹的概念以及自平衡的各種變化（指路上期←戳），本期我將會對TreeMap結(jié)合紅黑樹理論進行解讀。

首先，我們先來回憶一下紅黑樹的5條基本規(guī)則。

1.結(jié)點是紅色或者黑色，

2.根結(jié)點為黑色，

3.每個葉子結(jié)點都是黑色的空結(jié)點，

4.每個紅色結(jié)點的兩個子結(jié)點都是黑色，

5.從任何一個結(jié)點到葉子結(jié)點的所有路徑的黑色結(jié)點的個數(shù)相同。

?

TreeMap的基本結(jié)構(gòu)

我們先來看一下TreeMap的成員屬性，

1 private final Comparator<? super K> comparator; 2 private transient Entry<K,V> root; 3 private transient int size = 0; 4 private transient int modCount = 0;

第1行，比較器，主要是用來維持樹結(jié)構(gòu)的有序，可以為空，如果為空，那按照key的自然規(guī)則進行排序，

第2行，Entry的引用root，是樹型結(jié)構(gòu)的根，

第3行，記錄map中數(shù)據(jù)元素的個數(shù)，

第4行，記錄map中數(shù)據(jù)更新的次數(shù)，

?

Entry是TreeMap的一個靜態(tài)內(nèi)部類，一個Entry對應(yīng)一個樹型結(jié)構(gòu)中的結(jié)點，下面我們來看一下Entry的成員屬性和構(gòu)造函數(shù)，

1 static final class Entry<K,V> implements Map.Entry<K,V> { 2 K key; 3 V value; 4 Entry<K,V> left; 5 Entry<K,V> right; 6 Entry<K,V> parent; 7 boolean color = BLACK; 8 9 Entry(K key, V value, Entry<K,V> parent) { 10 this.key = key; 11 this.value = value; 12 this.parent = parent; 13 }

第2行，鍵

第3行，值

第4行，左結(jié)點的引用

第5行，右結(jié)點的引用

第6行，父結(jié)點的引用

第7行，當(dāng)前結(jié)點默認為黑色結(jié)點

第9行，構(gòu)造函數(shù)。初始化鍵、值、父結(jié)點引用

?

紅黑樹中的第1條規(guī)則是結(jié)點是紅色或者黑色，在TreeMap中聲明了兩個常量表示

1 private static final boolean RED = false; 2 private static final boolean BLACK = true;

false表示紅色，true表示黑色，根結(jié)點是黑色，因此是true。

?

TreeMap的put方法解讀

下面我們解讀一下map在新增元素時發(fā)生哪些動作？我們以一個public修飾的靜態(tài)方法，返回值為void，參數(shù)為String數(shù)組的main方法

作為程序的切入口，如下一段代碼，

1 public static void main(String[] args) { 2 TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); 3 map.put(50,3001); 4 map.put(30,3002); 5 map.put(70,3003); 6 }

第2行，new TreeMap<Integer, Integer>()，是一個無參的構(gòu)造函數(shù)，初始化比較器為null，

第3行，新增一個鍵為50，值為3001的元素，

我們來跟一下put方法，源代碼如下，

1 public V put(K key, V value) { 2 Entry<K,V> t = root; 3 if (t == null) { 4 compare(key, key); // type (and possibly null) check 5 6 root = new Entry<>(key, value, null); 7 size = 1; 8 modCount++; 9 return null; 10 } 11 int cmp; 12 Entry<K,V> parent; 13 // split comparator and comparable paths 14 Comparator<? super K> cpr = comparator; 15 if (cpr != null) { 16 do { 17 parent = t; 18 cmp = cpr.compare(key, t.key); 19 if (cmp < 0) 20 t = t.left; 21 else if (cmp > 0) 22 t = t.right; 23 else 24 return t.setValue(value); 25 } while (t != null); 26 } 27 else { 28 if (key == null) 29 throw new NullPointerException(); 30 @SuppressWarnings("unchecked") 31 Comparable<? super K> k = (Comparable<? super K>) key; 32 do { 33 parent = t; 34 cmp = k.compareTo(t.key); 35 if (cmp < 0) 36 t = t.left; 37 else if (cmp > 0) 38 t = t.right; 39 else 40 return t.setValue(value); 41 } while (t != null); 42 } 43 Entry<K,V> e = new Entry<>(key, value, parent); 44 if (cmp < 0) 45 parent.left = e; 46 else 47 parent.right = e; 48 fixAfterInsertion(e); 49 size++; 50 modCount++; 51 return null; 52 }

第2行，把變量t指向根結(jié)點的引用，

第3行，判斷根結(jié)點是否為空，如果為空說明，當(dāng)前數(shù)據(jù)元素時首次新增，

第4行，調(diào)用自定義的比較器或者自然比較器，自身與自身做比較，旨在判斷key是否是null，如果為空，則拋出NPE，

因此，TreeMap中的Key不允許為空。

第6-9行，把root引用指向當(dāng)前元素，并且樹結(jié)構(gòu)的數(shù)量size更新為1，modCount自增，結(jié)束，返回值為null，

?

第11行，聲明一個int類型的cmp，用來記錄比較器的返回值

第12行，聲明一個Entry類型的parent，用來記錄待存儲元素的父結(jié)點。上面Entry的構(gòu)造函數(shù)中，其中一個數(shù)據(jù)項就是父結(jié)點，

?

第15行-26行，當(dāng)比較器不為空時，找出待存儲元素的父結(jié)點，下面我們來逐行閱讀

第18行，根據(jù)我們自定義的比較規(guī)則，待存儲元素的鍵和當(dāng)前結(jié)點比較大小，

第19行，如果小于當(dāng)前結(jié)點的鍵，那么下一個比較的目標(biāo)應(yīng)在在左子樹上，

第21行，如果大于當(dāng)前結(jié)點的鍵，那么下一個比較的目標(biāo)應(yīng)該在右子樹上，

第24行，如果待存儲的鍵等于當(dāng)前結(jié)點的鍵，那么將新值更新，同時返回舊值。

?

第27行-42行，當(dāng)比較器為空時，采用默認的自然比較規(guī)則，找出父結(jié)點上述基本相似，

注意：第28行，對key是否為空校驗，因此：TreeMap中的Key不允許為空。

?

第43行，賦值，

第44行-47行，確定新增元素時父結(jié)點的左結(jié)點還是右結(jié)點。

第49行-50行，size和modCount分別自增，

?

接下來我們著來分析第48行，fixAfterInsertion(e)，跟一下代碼，

1 private void fixAfterInsertion(Entry<K,V> x) { 2 x.color = RED; 3 4 while (x != null && x != root && x.parent.color == RED) { 5 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { 6 Entry<K,V> y = rightOf(parentOf(parentOf(x))); 7 if (colorOf(y) == RED) { 8 setColor(parentOf(x), BLACK); 9 setColor(y, BLACK); 10 setColor(parentOf(parentOf(x)), RED); 11 x = parentOf(parentOf(x)); 12 } else { 13 if (x == rightOf(parentOf(x))) { 14 x = parentOf(x); 15 rotateLeft(x); 16 } 17 setColor(parentOf(x), BLACK); 18 setColor(parentOf(parentOf(x)), RED); 19 rotateRight(parentOf(parentOf(x))); 20 } 21 } else { 22 Entry<K,V> y = leftOf(parentOf(parentOf(x))); 23 if (colorOf(y) == RED) { 24 setColor(parentOf(x), BLACK); 25 setColor(y, BLACK); 26 setColor(parentOf(parentOf(x)), RED); 27 x = parentOf(parentOf(x)); 28 } else { 29 if (x == leftOf(parentOf(x))) { 30 x = parentOf(x); 31 rotateRight(x); 32 } 33 setColor(parentOf(x), BLACK); 34 setColor(parentOf(parentOf(x)), RED); 35 rotateLeft(parentOf(parentOf(x))); 36 } 37 } 38 } 39 root.color = BLACK; 40 }

fixAfterInsertion，方法名直譯過來就是插入之后做調(diào)整之意，
第2行，將新元素的結(jié)點置為紅色，
第4行-38行，調(diào)整的過程。
第39行，將調(diào)整后的樹結(jié)構(gòu)的根置為黑色

下面我們著重來分析第4-38行代碼，
第5行→①x的父結(jié)點等于x的父結(jié)點的父結(jié)點的左結(jié)點 → x的父結(jié)點 是 x父結(jié)點的父結(jié)點的左結(jié)點，

?

以上3張圖都符合，x的父結(jié)點是a，a的父結(jié)點是b，所以parentOf(x) == leftOf(parentOf(parentOf(x)))

用一句話來描述就是，x的父結(jié)點a是a的父結(jié)點的左孩子。

第6行，rightOf(parentOf(parentOf(x)))，x的父結(jié)點的父結(jié)點的右結(jié)點，記作y，

第7行，如果y為紅色，把y變成黑色，把a變成黑色，把b變?yōu)榧t色（如下圖所示），同時把x引用指向x的父結(jié)點的父結(jié)點也就是b結(jié)點，本次循環(huán)結(jié)束，繼續(xù)下一輪的循環(huán)調(diào)整。

第7行，如果y是黑色，

如果x是結(jié)點的右結(jié)點，左旋轉(zhuǎn)a（第13行-15行）此時x的引用指向了a，

?

?第33行-35行，x（圖中的a，因為x引用指向了a）的父結(jié)點（圖中的x）變?yōu)楹谏?#xff0c;x父結(jié)點(圖中的a)的父結(jié)點變?yōu)榧t色，對x的父結(jié)點的父結(jié)點(圖中的b)進行右旋

第7行，如果y是黑色，

如果x不是結(jié)點的右結(jié)點，【左旋轉(zhuǎn)a（第13行-15行）此時x的引用指向了a】，把x的父結(jié)點變?yōu)楹谏?#xff0c;把x的父結(jié)點的父結(jié)點變?yōu)榧t色，最后將x的父結(jié)點的父結(jié)點右旋

當(dāng)前分支結(jié)束。

?

下面我們重新回到第5行，

第5行→②x的父結(jié)點 不是 x父結(jié)點的父結(jié)點的左結(jié)點，換一句話說就是，

x的父結(jié)點 是 x父結(jié)點的父結(jié)點的右結(jié)點，和上述情況比較類似，我們來看一組示意圖，

?

?

以上3張圖都符合，x的父結(jié)點是a，a的父結(jié)點是b，所以parentOf(x) == rightOf(parentOf(parentOf(x)))

用一句話來描述就是，x的父結(jié)點a是a的父結(jié)點的右孩子。

第22行，leftOf(parentOf(parentOf(x)))，x的父結(jié)點的父結(jié)點的左結(jié)點，記作y，

第23行，如果y為紅色，把y變成黑色，把a變成黑色，把b變?yōu)榧t色（如下圖所示），同時把x引用指向x的父結(jié)點的父結(jié)點也就是b結(jié)點，本次循環(huán)結(jié)束，繼續(xù)下一輪的循環(huán)調(diào)整。

第23行，如果y是黑色，

如果x是結(jié)點的左結(jié)點，右旋轉(zhuǎn)a（第29行-32行）此時x的引用指向了a，

第33行-35行，x（圖中的a，因為x引用指向了a）的父結(jié)點（圖中的x）變?yōu)楹谏?#xff0c;x父結(jié)點(圖中的a)的父結(jié)點變?yōu)榧t色，對x的父結(jié)點的父結(jié)點(圖中的b)進行右旋

?當(dāng)前分支結(jié)束，進入下一輪循環(huán)。

?

以上是對于TreeMap的put方法的解讀，比較復(fù)雜。下面我簡單總結(jié)一下fixAfterInsertion的過程

第1步，將新增的元素x置為紅色，

第2步，判斷新增元素x不為空，且不是root結(jié)點，且x的父結(jié)點是紅色，如果滿足，進入第3步，如果不滿足跳到第16步，

第3步，判斷x的父結(jié)點a是否是a的父結(jié)點的左結(jié)點，如果是，進入第4步，如果不是進入10步，

?

第4步，取出x父結(jié)點的父結(jié)點的右結(jié)點，記作y，

第5步，判斷y的顏色是否為紅色，如果是，進入第6步，如果不是進入7步，

第6步，x的父結(jié)點置為黑色，x父結(jié)點的父結(jié)點的右結(jié)點，即y置為黑色，x的父結(jié)點的父結(jié)點置為紅色，x的引用指向x的父結(jié)點的父結(jié)點，跳到第2步，

?

第7步，判斷x是否是x父結(jié)點的右結(jié)點，如果是，進入第8步，如果不是，進入第9步，

第8步，x的應(yīng)用指向x的父結(jié)點，x左旋（注意，此時x指向的是原x的父結(jié)點）

第9步，x的父結(jié)點置為黑色，x的父結(jié)點的父結(jié)點置為紅色，x的父結(jié)點的父結(jié)點右旋，跳到第2步，

?

第10步，取出x父結(jié)點的父結(jié)點的左結(jié)點，記作y，

第11步，判斷y的顏色是否為紅色，如果是，進入第12步，如果不是進入13步，

第12步，x的父結(jié)點置為黑色，x父結(jié)點的父結(jié)點的左結(jié)點，即y置為黑色，x的父結(jié)點的父結(jié)點置為紅色，x的引用指向x的父結(jié)點的父結(jié)點，跳到第2步，

?

第13步，判斷x是否是x父結(jié)點的左結(jié)點，如果是，進入第14步，如果不是，進入第15步，

第14步，x的引用指向x的父結(jié)點，x右旋（注意，此時x指向的是原x的父結(jié)點）

第15步，x的父結(jié)點置為黑色，x的父結(jié)點的父結(jié)點置為紅色，x的父結(jié)點的父結(jié)點左旋，跳到第2步，

?

第16步，把根節(jié)點置為黑色。

?

?由于內(nèi)容較多，因此TreeMap源碼解析分為上篇、中篇和下篇3部分，

下期預(yù)告

1 TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); 2 map.put(50,3001); 3 map.put(30,3002); 4 map.put(70,3003);

?

本文提到的簡單例子的樹我們還沒有建立起來，由于內(nèi)容較多，所以打算，把這一部分也放在【java集合之TreeMap源碼解析中篇】來講解。謝謝關(guān)注。

轉(zhuǎn)載于:https://www.cnblogs.com/sunshine798798/p/9118905.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的Java集合之TreeMap源码解析上篇的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。