?????上篇文章我們介紹了HashMap集合茴厉，這是一個鍵值對集合泽台，可以高效的按照鍵查找數(shù)值。但是它有一個缺陷：數(shù)據(jù)如果是無序的可以是很高效的矾缓，但是如果數(shù)據(jù)需要排列有順序就不適合了怀酷。本篇將要介紹的一個集合是樹集鍵值對（TreeMap），它能夠?qū)?shù)據(jù)按照鍵值有序的存儲嗜闻。
?????在介紹TreeMap之前蜕依，我們來了解一種數(shù)據(jù)結(jié)構(gòu)：排序二叉樹。相信學(xué)過數(shù)據(jù)結(jié)構(gòu)的同學(xué)知道琉雳，這種結(jié)構(gòu)的數(shù)據(jù)存儲形式在查找的時候效率非常高样眠。
?????如圖所示，這種數(shù)據(jù)結(jié)構(gòu)是以二叉樹為基礎(chǔ)的翠肘，所有的左孩子的value值都是小于根結(jié)點的value值的檐束，所有右孩子的value值都是大于根結(jié)點的。這樣做的好處在于：如果需要按照鍵值查找數(shù)據(jù)元素束倍，只要比較當(dāng)前結(jié)點的value值即可（小于當(dāng)前結(jié)點value值的被丧，往左走，否則往右走）绪妹，這種方式甥桂，每次可以減少一半的操作，所以效率比較高邮旷。在實現(xiàn)我們的TreeMap中格嘁，使用的是紅黑樹（一種優(yōu)化了的二叉排序樹）。
一廊移、TreeMap的超接口
?????TreeMap主要繼承了類AbstractMap（一個對Map接口的實現(xiàn)類）和 NavigableMap（主要提供了對TreeMap的一些高級操作例如：返回第一個鍵或者返回小于某個鍵的視圖等）糕簿。主要的一些操作有：put添加元素到集合中探入，remove根據(jù)鍵值或者value刪除指定元素，get根據(jù)指定鍵值獲取某個元素懂诗，containsValue查看是否包含某個指定的值蜂嗽，containsKey 查看是否包含某個指定的key數(shù)值等。
二殃恒、構(gòu)造函數(shù)
?????TreeMap 的構(gòu)造函數(shù)主要有以下幾種：
private final Comparator<? super K> comparator;
public TreeMap() {comparator = null;}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
????? 因為在我們的內(nèi)部存儲結(jié)構(gòu)中植旧，是需要對兩個節(jié)點的元素的鍵值進行比較的，所以就必須要實現(xiàn)Comparable接口來具有比較功能离唐。第一個構(gòu)造函數(shù)默認(rèn)無參病附，內(nèi)部將我們的比較器賦值為null，表明：在內(nèi)部集合中不需要接受來自外部傳入的比較器亥鬓，默認(rèn)使用Key的比較器（例如：Key是Integer類型就會默認(rèn)使用它的比較器）完沪。第二種構(gòu)造函數(shù)就是從外部傳入指定的比較器，指定TreeMap內(nèi)部在對鍵進行比較的時候使用我們從外部傳入的比較器嵌戈。
三覆积、內(nèi)部存儲的基本原理
?????從源碼中摘取部分代碼，能說明內(nèi)部結(jié)構(gòu)即可熟呛。
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int modCount = 0;
//靜態(tài)成員內(nè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;
.........
}
?????從代碼中宽档，我們可以很容易的看出來，內(nèi)部包含一個 comparator 比較器（或值被置為Key的比較器庵朝，或是被置為外部傳入的比較器）吗冤，根結(jié)點 root （指向紅黑樹的跟結(jié)點），記錄修改次數(shù) modCount （用于對集合結(jié)構(gòu)性的檢查和前面文章說的一樣）九府，還有一個靜態(tài)內(nèi)部類（其實可以理解為一個樹結(jié)點）椎瘟，其中有存儲鍵和值的key和value，還有指向左孩子和右孩子的“指針”昔逗，還有指向父結(jié)點的“指針”降传，最后還包括一個標(biāo)志 color（這個暫時不用知道）篷朵。也就是說勾怒，一個root指向樹的跟結(jié)點，而這個跟根結(jié)點又鏈接為一棵樹声旺，最后通過這個root可以遍歷整個樹笔链。
四、put添加元素到集合中
?????在了解了TreeMap的內(nèi)部結(jié)構(gòu)之后腮猖，我們可以看看他是怎么將一個元素結(jié)點掛到整棵樹上的鉴扫。由于put方法的源碼比較多，請大家慢慢看澈缺。
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é)點是否是空的坪创，如果是空的直接創(chuàng)建一個結(jié)點并將parent賦null炕婶，將其作為該樹的跟結(jié)點，返回null跳過余下代碼莱预。如果跟結(jié)點不是空的柠掂，就去判斷 comparator 是否為null（也就是判斷comparator的值是默認(rèn)key的比較器還是外部傳入的比較器），如果comparator的值是外部傳入的依沮，通過循環(huán)比較key的值計算將要添加的結(jié)點的位置（過程中如果發(fā)現(xiàn)有某個結(jié)點的key值和將要添加的key的值相等涯贞，說明這是修改操作，修改其value值返回舊value值）危喉。
?????如果在創(chuàng)建對象的時候并沒有從外部傳入比較器宋渔，首先判斷key的值是否為null（如果是就拋出空指針異常），那有人說：為什么要對key是否為空做判斷呢辜限？上面不是也沒有做判斷么皇拣？ 答案是：如果 comparator 是外部傳入的，那么沒問題列粪，但是如果是key的默認(rèn)比較器审磁，那如果key為null 還要調(diào)用比價器 必然拋空指針異常。接下來做的事情和上面一樣的岂座。
?????程序執(zhí)行到最后了态蒂，我們要知道一點的是：parent指向的是最后一個結(jié)點也就是我們將要添加的結(jié)點的父結(jié)點。最后根據(jù)key和value和parent創(chuàng)建一個幾點（父結(jié)點是parent）费什，然后根據(jù)上面的判斷確定此結(jié)點是parent的左孩子還是右孩子钾恢。
?????這個方法中有一個 fixAfterInsertion(e); 是用于紅黑樹的構(gòu)造的，調(diào)用這個函數(shù)可以將我們剛剛創(chuàng)建完成之后的樹通過挪動重新構(gòu)建成紅黑樹鸳址。
?????最后總結(jié)一下整個put方法的執(zhí)行過程：
- 判斷此樹是否是空的瘩蚪，空樹的操作就很簡單了
- 判斷比較器的來源做不同的操作（比較value值確定位置）
- 構(gòu)建新結(jié)點掛上樹
- 調(diào)用方法重構(gòu)紅黑樹
其中，我們要區(qū)分一點的是稿黍，為什么有時候返回的null疹瘦，有時候返回的是舊結(jié)點的value，主要區(qū)別還是在于巡球，put方法作為添加元素和修改元素的兩種功能言沐，添加元素的時候統(tǒng)一返回的是null，修改元素的時候統(tǒng)一返回的是別修改之前的元素的value酣栈。
五险胰、根據(jù)鍵的值刪除結(jié)點元素
?????添加元素直到是怎么回事了之后，我們來看看刪除元素是怎么被實現(xiàn)的矿筝，首先看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;
}
?????從代碼中可以看出來起便，刪除的操作主要還是兩個操作的結(jié)合，一個是獲取指定元素，一個是刪除指定元素榆综。我們先看如何獲取指定元素妙痹。
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指向根結(jié)點root，循環(huán)遍歷陋守，比較key和當(dāng)前循環(huán)到的key是否相等震贵，不相等就根據(jù)大小向左或者向右，如果相等執(zhí)行return p; 返回此結(jié)點水评。如果整棵樹遍歷完成之后猩系，沒有找到指定鍵值的結(jié)點就會返回null表示未找到該結(jié)點。這就是查找方法中燥，下面我們看看刪除指定結(jié)點的方法寇甸。
?????在看代碼之前我們先了解一下整體的思路，將要刪除的結(jié)點可能有以下三種情況：
- 該結(jié)點為葉子結(jié)點疗涉，即無左孩子和右孩子
- 該結(jié)點只有一個孩子結(jié)點
-
該結(jié)點有兩個孩子結(jié)點
?????第一種情況拿霉，直接將該結(jié)點刪除跷叉，并將父結(jié)點的對應(yīng)引用賦值為null
?????第二種情況迎捺，跳過該結(jié)點將其父結(jié)點指向這個孩子結(jié)點
這里寫圖片描述
第三種情況，找到待刪結(jié)點的后繼結(jié)點將后繼結(jié)點替換到待刪結(jié)點并刪除后繼結(jié)點（將問題轉(zhuǎn)換為刪除后繼結(jié)點测萎，通過前面兩種可以解決）
這里寫圖片描述
找到后繼結(jié)點
這里寫圖片描述
替換待刪結(jié)點
這里寫圖片描述
刪除后繼結(jié)點
這里寫圖片描述
下面我們看代碼：
/*代碼雖多闹伪，我們一點一點看*/
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ào)用函數(shù) successor返回后繼結(jié)點偏瓤，并且替換待刪結(jié)點杀怠。對于這條語句：Entry>K,V< replacement = (p.left != null ? p.left : p.right); ，我們上述的三種情況下replacement的取值值得研究厅克，如果是第一種情況（葉子結(jié)點）赔退，那么replacement取值為null，進入下面的判斷证舟，第一個if過硕旗，第二個判斷待刪結(jié)點是否是根結(jié)點（只有根結(jié)點的父結(jié)點為null），如果是說明整個樹只有一個結(jié)點褪储，那么直接刪除即可卵渴，如果不是根結(jié)點就說明是葉子結(jié)點慧域，此時將父結(jié)點賦值為null然后刪除即可鲤竹。
對于第二種情況下（只有一個孩子結(jié)點時候），最上面的if語句是不做的，如果那一個結(jié)點是左孩子 replacement為該結(jié)點辛藻，然后將此結(jié)點跳過父結(jié)點掛在待刪結(jié)點的下面碘橘，如果那一個孩子是右孩子，replacement為該結(jié)點吱肌，同樣操作痘拆。
第三種情況（待刪結(jié)點具有兩個孩子結(jié)點），那肯定執(zhí)行最最上面的if語句中代碼氮墨，找到后繼結(jié)點替換待刪結(jié)點（后繼結(jié)點一定沒有左孩子）纺蛆，成功的將問題轉(zhuǎn)換為刪除后繼結(jié)點，又因為后繼結(jié)點一定沒有左孩子规揪，整個問題已經(jīng)被轉(zhuǎn)換成上述兩種情況了桥氏，（假如后繼結(jié)點沒有右孩子就是第一種，假如有就是第二種）所以replacement = p.right猛铅，下面分情況處理字支。刪除方法結(jié)束。
?????小結(jié)一下奸忽，刪除結(jié)點難點在于刪除指定鍵值的結(jié)點堕伪，主要分為三種情況，葉子結(jié)點栗菜，一個孩子結(jié)點欠雌，兩個孩子結(jié)點。而對于不同的情況疙筹，jdk編寫者將最難的兩個孩子結(jié)點轉(zhuǎn)換為前兩種較為簡單的方式桨昙，可見大神之作。欽佩腌歉。
?????最后還是要說蛙酪，本篇文章為博主反復(fù)研究jdk源碼總結(jié)而來，如果有錯誤翘盖，望指出桂塞。
