java treemap源碼解析詳解
在介紹treemap之前，我們來(lái)了解一種數(shù)據(jù)結(jié)構(gòu)：排序二叉樹(shù)。相信學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的同學(xué)知道，這種結(jié)構(gòu)的數(shù)據(jù)存儲(chǔ)形式在查找的時(shí)候效率非常高。
如圖所示，這種數(shù)據(jù)結(jié)構(gòu)是以二叉樹(shù)為基礎(chǔ)的，所有的左孩子的value值都是小于根結(jié)點(diǎn)的value值的，所有右孩子的value值都是大于根結(jié)點(diǎn)的。這樣做的好處在于：如果需要按照鍵值查找數(shù)據(jù)元素，只要比較當(dāng)前結(jié)點(diǎn)的value值即可（小于當(dāng)前結(jié)點(diǎn)value值的，往左走，否則往右走），這種方式，每次可以減少一半的操作，所以效率比較高。在實(shí)現(xiàn)我們的treemap中，使用的是紅黑樹(shù)（一種優(yōu)化了的二叉排序樹(shù)）。
一、treemap的超接口
treemap主要繼承了類(lèi)abstractmap（一個(gè)對(duì)map接口的實(shí)現(xiàn)類(lèi)）和 navigablemap（主要提供了對(duì)treemap的一些高級(jí)操作例如：返回第一個(gè)鍵或者返回小于某個(gè)鍵的視圖等）。主要的一些操作有：put添加元素到集合中，remove根據(jù)鍵值或者value刪除指定元素，get根據(jù)指定鍵值獲取某個(gè)元素，containsvalue查看是否包含某個(gè)指定的值，containskey 查看是否包含某個(gè)指定的key數(shù)值等。
二、構(gòu)造函數(shù)
treemap 的構(gòu)造函數(shù)主要有以下幾種：
|
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; } |
因?yàn)樵谖覀兊膬?nèi)部存儲(chǔ)結(jié)構(gòu)中，是需要對(duì)兩個(gè)節(jié)點(diǎn)的元素的鍵值進(jìn)行比較的，所以就必須要實(shí)現(xiàn)comparable接口來(lái)具有比較功能。第一個(gè)構(gòu)造函數(shù)默認(rèn)無(wú)參，內(nèi)部將我們的比較器賦值為null，表明：在內(nèi)部集合中不需要接受來(lái)自外部傳入的比較器，默認(rèn)使用key的比較器（例如：key是integer類(lèi)型就會(huì)默認(rèn)使用它的比較器）。第二種構(gòu)造函數(shù)就是從外部傳入指定的比較器，指定treemap內(nèi)部在對(duì)鍵進(jìn)行比較的時(shí)候使用我們從外部傳入的比較器。
三、內(nèi)部存儲(chǔ)的基本原理
從源碼中摘取部分代碼，能說(shuō)明內(nèi)部結(jié)構(gòu)即可。
|
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;//靜態(tài)成員內(nèi)部類(lèi)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; ......... } |
從代碼中，我們可以很容易的看出來(lái)，內(nèi)部包含一個(gè) comparator 比較器（或值被置為key的比較器，或是被置為外部傳入的比較器），根結(jié)點(diǎn) root （指向紅黑樹(shù)的跟結(jié)點(diǎn)），記錄修改次數(shù) modcount （用于對(duì)集合結(jié)構(gòu)性的檢查和前面文章說(shuō)的一樣），還有一個(gè)靜態(tài)內(nèi)部類(lèi)（其實(shí)可以理解為一個(gè)樹(shù)結(jié)點(diǎn)），其中有存儲(chǔ)鍵和值的key和value，還有指向左孩子和右孩子的“指針”，還有指向父結(jié)點(diǎn)的“指針”，最后還包括一個(gè)標(biāo)志 color（這個(gè)暫時(shí)不用知道）。也就是說(shuō)，一個(gè)root指向樹(shù)的跟結(jié)點(diǎn)，而這個(gè)跟根結(jié)點(diǎn)又鏈接為一棵樹(shù)，最后通過(guò)這個(gè)root可以遍歷整個(gè)樹(shù)。
四、put添加元素到集合中
在了解了treemap的內(nèi)部結(jié)構(gòu)之后，我們可以看看他是怎么將一個(gè)元素結(jié)點(diǎn)掛到整棵樹(shù)上的。由于put方法的源碼比較多，請(qǐng)大家慢慢看。
|
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; } |
首先判斷根結(jié)點(diǎn)是否是空的，如果是空的直接創(chuàng)建一個(gè)結(jié)點(diǎn)并將parent賦null，將其作為該樹(shù)的跟結(jié)點(diǎn)，返回null跳過(guò)余下代碼。如果跟結(jié)點(diǎn)不是空的，就去判斷 comparator 是否為null（也就是判斷comparator的值是默認(rèn)key的比較器還是外部傳入的比較器），如果comparator的值是外部傳入的，通過(guò)循環(huán)比較key的值計(jì)算將要添加的結(jié)點(diǎn)的位置（過(guò)程中如果發(fā)現(xiàn)有某個(gè)結(jié)點(diǎn)的key值和將要添加的key的值相等，說(shuō)明這是修改操作，修改其value值返回舊value值）。
如果在創(chuàng)建對(duì)象的時(shí)候并沒(méi)有從外部傳入比較器，首先判斷key的值是否為null（如果是就拋出空指針異常），那有人說(shuō)：為什么要對(duì)key是否為空做判斷呢？上面不是也沒(méi)有做判斷么？ 答案是：如果 comparator 是外部傳入的，那么沒(méi)問(wèn)題，但是如果是key的默認(rèn)比較器，那如果key為null 還要調(diào)用比價(jià)器 必然拋空指針異常。接下來(lái)做的事情和上面一樣的。
程序執(zhí)行到最后了，我們要知道一點(diǎn)的是：parent指向的是最后一個(gè)結(jié)點(diǎn)也就是我們將要添加的結(jié)點(diǎn)的父結(jié)點(diǎn)。最后根據(jù)key和value和parent創(chuàng)建一個(gè)幾點(diǎn)（父結(jié)點(diǎn)是parent），然后根據(jù)上面的判斷確定此結(jié)點(diǎn)是parent的左孩子還是右孩子。
這個(gè)方法中有一個(gè) fixafterinsertion(e); 是用于紅黑樹(shù)的構(gòu)造的，調(diào)用這個(gè)函數(shù)可以將我們剛剛創(chuàng)建完成之后的樹(shù)通過(guò)挪動(dòng)重新構(gòu)建成紅黑樹(shù)。
最后總結(jié)一下整個(gè)put方法的執(zhí)行過(guò)程：
- 判斷此樹(shù)是否是空的，空樹(shù)的操作就很簡(jiǎn)單了
- 判斷比較器的來(lái)源做不同的操作（比較value值確定位置）
- 構(gòu)建新結(jié)點(diǎn)掛上樹(shù)
- 調(diào)用方法重構(gòu)紅黑樹(shù)
其中，我們要區(qū)分一點(diǎn)的是，為什么有時(shí)候返回的null，有時(shí)候返回的是舊結(jié)點(diǎn)的value，主要區(qū)別還是在于，put方法作為添加元素和修改元素的兩種功能，添加元素的時(shí)候統(tǒng)一返回的是null，修改元素的時(shí)候統(tǒng)一返回的是別修改之前的元素的value。
五、根據(jù)鍵的值刪除結(jié)點(diǎn)元素
添加元素直到是怎么回事了之后，我們來(lái)看看刪除元素是怎么被實(shí)現(xiàn)的，首先看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; } |
從代碼中可以看出來(lái)，刪除的操作主要還是兩個(gè)操作的結(jié)合，一個(gè)是獲取指定元素，一個(gè)是刪除指定元素。我們先看如何獲取指定元素。
|
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; } |
這段代碼不難理解，依然是分兩種情況比較器的來(lái)源（由于兩種情況下的處理方式類(lèi)似，此處指具體說(shuō)其中一種），p指向根結(jié)點(diǎn)root，循環(huán)遍歷，比較key和當(dāng)前循環(huán)到的key是否相等，不相等就根據(jù)大小向左或者向右，如果相等執(zhí)行return p; 返回此結(jié)點(diǎn)。如果整棵樹(shù)遍歷完成之后，沒(méi)有找到指定鍵值的結(jié)點(diǎn)就會(huì)返回null表示未找到該結(jié)點(diǎn)。這就是查找方法，下面我們看看刪除指定結(jié)點(diǎn)的方法。
在看代碼之前我們先了解一下整體的思路，將要?jiǎng)h除的結(jié)點(diǎn)可能有以下三種情況：
- 該結(jié)點(diǎn)為葉子結(jié)點(diǎn)，即無(wú)左孩子和右孩子
- 該結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn)
- 該結(jié)點(diǎn)有兩個(gè)孩子結(jié)點(diǎn)
第一種情況，直接將該結(jié)點(diǎn)刪除，并將父結(jié)點(diǎn)的對(duì)應(yīng)引用賦值為null
第二種情況，跳過(guò)該結(jié)點(diǎn)將其父結(jié)點(diǎn)指向這個(gè)孩子結(jié)點(diǎn)
第三種情況，找到待刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)將后繼結(jié)點(diǎn)替換到待刪結(jié)點(diǎn)并刪除后繼結(jié)點(diǎn)（將問(wèn)題轉(zhuǎn)換為刪除后繼結(jié)點(diǎn)，通過(guò)前面兩種可以解決）
找到后繼結(jié)點(diǎn)
替換待刪結(jié)點(diǎn)
刪除后繼結(jié)點(diǎn)
下面我們看代碼：
|
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
|
/*代碼雖多，我們一點(diǎn)一點(diǎn)看*/ 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; } } } |
首先，判斷待刪結(jié)點(diǎn)是否具有兩個(gè)孩子，如果有調(diào)用函數(shù) successor返回后繼結(jié)點(diǎn)，并且替換待刪結(jié)點(diǎn)。對(duì)于這條語(yǔ)句：entry>k,v< replacement = (p.left != null ? p.left : p.right); ，我們上述的三種情況下replacement的取值值得研究，如果是第一種情況（葉子結(jié)點(diǎn)），那么replacement取值為null，進(jìn)入下面的判斷，第一個(gè)if過(guò)，第二個(gè)判斷待刪結(jié)點(diǎn)是否是根結(jié)點(diǎn)（只有根結(jié)點(diǎn)的父結(jié)點(diǎn)為null），如果是說(shuō)明整個(gè)樹(shù)只有一個(gè)結(jié)點(diǎn)，那么直接刪除即可，如果不是根結(jié)點(diǎn)就說(shuō)明是葉子結(jié)點(diǎn)，此時(shí)將父結(jié)點(diǎn)賦值為null然后刪除即可。
對(duì)于第二種情況下（只有一個(gè)孩子結(jié)點(diǎn)時(shí)候），最上面的if語(yǔ)句是不做的，如果那一個(gè)結(jié)點(diǎn)是左孩子 replacement為該結(jié)點(diǎn)，然后將此結(jié)點(diǎn)跳過(guò)父結(jié)點(diǎn)掛在待刪結(jié)點(diǎn)的下面，如果那一個(gè)孩子是右孩子，replacement為該結(jié)點(diǎn)，同樣操作。
第三種情況（待刪結(jié)點(diǎn)具有兩個(gè)孩子結(jié)點(diǎn)），那肯定執(zhí)行最最上面的if語(yǔ)句中代碼，找到后繼結(jié)點(diǎn)替換待刪結(jié)點(diǎn)（后繼結(jié)點(diǎn)一定沒(méi)有左孩子），成功的將問(wèn)題轉(zhuǎn)換為刪除后繼結(jié)點(diǎn)，又因?yàn)楹罄^結(jié)點(diǎn)一定沒(méi)有左孩子，整個(gè)問(wèn)題已經(jīng)被轉(zhuǎn)換成上述兩種情況了，（假如后繼結(jié)點(diǎn)沒(méi)有右孩子就是第一種，假如有就是第二種）所以replacement = p.right，下面分情況處理。刪除方法結(jié)束。
小結(jié)一下，刪除結(jié)點(diǎn)難點(diǎn)在于刪除指定鍵值的結(jié)點(diǎn)，主要分為三種情況，葉子結(jié)點(diǎn)，一個(gè)孩子結(jié)點(diǎn)，兩個(gè)孩子結(jié)點(diǎn)。而對(duì)于不同的情況，jdk編寫(xiě)者將最難的兩個(gè)孩子結(jié)點(diǎn)轉(zhuǎn)換為前兩種較為簡(jiǎn)單的方式，可見(jiàn)大神之作。欽佩。
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
原文鏈接：http://blog.csdn.net/qq_35326718/article/details/59638560
