java treemap源碼解析詳解
在介紹treemap之前，我們來了解一種數據結構：排序二叉樹。相信學過數據結構的同學知道，這種結構的數據存儲形式在查找的時候效率非常高。
如圖所示，這種數據結構是以二叉樹為基礎的，所有的左孩子的value值都是小于根結點的value值的，所有右孩子的value值都是大于根結點的。這樣做的好處在于：如果需要按照鍵值查找數據元素，只要比較當前結點的value值即可（小于當前結點value值的，往左走，否則往右走），這種方式，每次可以減少一半的操作，所以效率比較高。在實現我們的treemap中，使用的是紅黑樹（一種優化了的二叉排序樹）。
一、treemap的超接口
treemap主要繼承了類abstractmap（一個對map接口的實現類）和 navigablemap（主要提供了對treemap的一些高級操作例如：返回第一個鍵或者返回小于某個鍵的視圖等）。主要的一些操作有：put添加元素到集合中，remove根據鍵值或者value刪除指定元素，get根據指定鍵值獲取某個元素，containsvalue查看是否包含某個指定的值，containskey 查看是否包含某個指定的key數值等。
二、構造函數
treemap 的構造函數主要有以下幾種：
|
1
2
3
4
5
6
7
|
private final comparator<? super k> comparator; public treemap() {comparator = null;} public treemap(comparator<? super k> comparator) { this.comparator = comparator; } |
因為在我們的內部存儲結構中，是需要對兩個節點的元素的鍵值進行比較的，所以就必須要實現comparable接口來具有比較功能。第一個構造函數默認無參，內部將我們的比較器賦值為null，表明：在內部集合中不需要接受來自外部傳入的比較器，默認使用key的比較器（例如：key是integer類型就會默認使用它的比較器）。第二種構造函數就是從外部傳入指定的比較器，指定treemap內部在對鍵進行比較的時候使用我們從外部傳入的比較器。
三、內部存儲的基本原理
從源碼中摘取部分代碼，能說明內部結構即可。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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; entry<k,v> right; entry<k,v> parent; boolean color = black; ......... } |
從代碼中，我們可以很容易的看出來，內部包含一個 comparator 比較器（或值被置為key的比較器，或是被置為外部傳入的比較器），根結點 root （指向紅黑樹的跟結點），記錄修改次數 modcount （用于對集合結構性的檢查和前面文章說的一樣），還有一個靜態內部類（其實可以理解為一個樹結點），其中有存儲鍵和值的key和value，還有指向左孩子和右孩子的“指針”，還有指向父結點的“指針”，最后還包括一個標志 color（這個暫時不用知道）。也就是說，一個root指向樹的跟結點，而這個跟根結點又鏈接為一棵樹，最后通過這個root可以遍歷整個樹。
四、put添加元素到集合中
在了解了treemap的內部結構之后，我們可以看看他是怎么將一個元素結點掛到整棵樹上的。由于put方法的源碼比較多，請大家慢慢看。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
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(); @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); } 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; } |
首先判斷根結點是否是空的，如果是空的直接創建一個結點并將parent賦null，將其作為該樹的跟結點，返回null跳過余下代碼。如果跟結點不是空的，就去判斷 comparator 是否為null（也就是判斷comparator的值是默認key的比較器還是外部傳入的比較器），如果comparator的值是外部傳入的，通過循環比較key的值計算將要添加的結點的位置（過程中如果發現有某個結點的key值和將要添加的key的值相等，說明這是修改操作，修改其value值返回舊value值）。
如果在創建對象的時候并沒有從外部傳入比較器，首先判斷key的值是否為null（如果是就拋出空指針異常），那有人說：為什么要對key是否為空做判斷呢？上面不是也沒有做判斷么？ 答案是：如果 comparator 是外部傳入的，那么沒問題，但是如果是key的默認比較器，那如果key為null 還要調用比價器 必然拋空指針異常。接下來做的事情和上面一樣的。
程序執行到最后了，我們要知道一點的是：parent指向的是最后一個結點也就是我們將要添加的結點的父結點。最后根據key和value和parent創建一個幾點（父結點是parent），然后根據上面的判斷確定此結點是parent的左孩子還是右孩子。
這個方法中有一個 fixafterinsertion(e); 是用于紅黑樹的構造的，調用這個函數可以將我們剛剛創建完成之后的樹通過挪動重新構建成紅黑樹。
最后總結一下整個put方法的執行過程：
- 判斷此樹是否是空的，空樹的操作就很簡單了
- 判斷比較器的來源做不同的操作（比較value值確定位置）
- 構建新結點掛上樹
- 調用方法重構紅黑樹
其中，我們要區分一點的是，為什么有時候返回的null，有時候返回的是舊結點的value，主要區別還是在于，put方法作為添加元素和修改元素的兩種功能，添加元素的時候統一返回的是null，修改元素的時候統一返回的是別修改之前的元素的value。
五、根據鍵的值刪除結點元素
添加元素直到是怎么回事了之后，我們來看看刪除元素是怎么被實現的，首先看remove方法：
|
1
2
3
4
5
6
7
8
9
|
public v remove(object key) { entry<k,v> p = getentry(key); if (p == null) return null; v oldvalue = p.value; deleteentry(p); return oldvalue; } |
從代碼中可以看出來，刪除的操作主要還是兩個操作的結合，一個是獲取指定元素，一個是刪除指定元素。我們先看如何獲取指定元素。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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
第二種情況，跳過該結點將其父結點指向這個孩子結點
第三種情況，找到待刪結點的后繼結點將后繼結點替換到待刪結點并刪除后繼結點（將問題轉換為刪除后繼結點，通過前面兩種可以解決）
找到后繼結點
替換待刪結點
刪除后繼結點
下面我們看代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
/*代碼雖多，我們一點一點看*/ 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返回后繼結點，并且替換待刪結點。對于這條語句：entry>k,v< replacement = (p.left != null ? p.left : p.right); ，我們上述的三種情況下replacement的取值值得研究，如果是第一種情況（葉子結點），那么replacement取值為null，進入下面的判斷，第一個if過，第二個判斷待刪結點是否是根結點（只有根結點的父結點為null），如果是說明整個樹只有一個結點，那么直接刪除即可，如果不是根結點就說明是葉子結點，此時將父結點賦值為null然后刪除即可。
對于第二種情況下（只有一個孩子結點時候），最上面的if語句是不做的，如果那一個結點是左孩子 replacement為該結點，然后將此結點跳過父結點掛在待刪結點的下面，如果那一個孩子是右孩子，replacement為該結點，同樣操作。
第三種情況（待刪結點具有兩個孩子結點），那肯定執行最最上面的if語句中代碼，找到后繼結點替換待刪結點（后繼結點一定沒有左孩子），成功的將問題轉換為刪除后繼結點，又因為后繼結點一定沒有左孩子，整個問題已經被轉換成上述兩種情況了，（假如后繼結點沒有右孩子就是第一種，假如有就是第二種）所以replacement = p.right，下面分情況處理。刪除方法結束。
小結一下，刪除結點難點在于刪除指定鍵值的結點，主要分為三種情況，葉子結點，一個孩子結點，兩個孩子結點。而對于不同的情況，jdk編寫者將最難的兩個孩子結點轉換為前兩種較為簡單的方式，可見大神之作。欽佩。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://blog.csdn.net/qq_35326718/article/details/59638560
