閱讀優(yōu)秀的源碼是提升編程技巧的重要手段之一家夺。
如有不對(duì)的地方，歡迎指正~
轉(zhuǎn)載請(qǐng)注明出處https://blog.lzoro.com佣蓉。
前言
開(kāi)門(mén)見(jiàn)山，山外有山亲雪，山外有山...
先簡(jiǎn)單介紹下TreeMap勇凭，來(lái)看下類(lèi)關(guān)系圖。
image
怎么說(shuō)呢义辕，TreeMap就是一個(gè)有序的鍵值對(duì)集合（這介紹有夠簡(jiǎn)單的）虾标。
TreeMap實(shí)現(xiàn)了NavigableMap接口， 而NavigableMap則是通過(guò)sortedMap間接繼承了Map接口灌砖，它定義了一系列導(dǎo)航方法璧函，這些Map之外的方法算是和HashMap的不同，另外的不同點(diǎn)還在于順序性基显。
關(guān)于TreeMap和HashMap的異同點(diǎn)柳譬，在接下來(lái)的每個(gè)章節(jié)都可能會(huì)提到。
如果還未了解過(guò)HashMap的续镇，可以移步這里Java源碼閱讀之HashMap - JDK1.8和這里Java源碼閱讀之紅黑樹(shù)在HashMap中的應(yīng)用 - JDK1.8。
接下來(lái)销部，請(qǐng)坐好摸航，準(zhǔn)備發(fā)車(chē)了。
基礎(chǔ)
老規(guī)矩舅桩，不想上來(lái)就整一大堆復(fù)雜晦澀的方法酱虎，還是先從變量了解起。
成員變量
/**
* comparator用來(lái)保持treemap的順序性
* 如果是null擂涛，則采取自然順序
*
* @serial
*/
private final Comparator<? super K> comparator;
/**
* 紅黑樹(shù)根節(jié)點(diǎn)
*/
private transient Entry<K,V> root;
/**
* 鍵值對(duì)數(shù)量
*/
private transient int size = 0;
/**
* 結(jié)構(gòu)修改次數(shù)
*/
private transient int modCount = 0;
從變量可以簡(jiǎn)單看出treemap跟HashMap有點(diǎn)類(lèi)似读串，而不同點(diǎn)在于
- HashMap
1、基于哈希桶+鏈表/紅黑樹(shù)實(shí)現(xiàn)
2、無(wú)序的 - TreeMap
1恢暖、基于紅黑樹(shù)實(shí)現(xiàn)
2排监、有序的，通過(guò)指定的comparator或者自然順序
接下來(lái)看下構(gòu)造函數(shù)
構(gòu)造函數(shù)
/**
* 空參構(gòu)造杰捂，利用自然排序構(gòu)造一個(gè)空的tree map
* 所有的key舆床，必須實(shí)現(xiàn)Comparable接口
* 與此同時(shí)，所以的key必須具備可比性嫁佳，{@code k1.compareTo(k2)}不能拋出{@code ClassCastException}
* 假如你試圖放一個(gè)違反約束的key到map里面挨队，如：放一個(gè)string類(lèi)型的key到原先存儲(chǔ)interger類(lèi)型key的map里面，將會(huì)拋出{@code
*/
public TreeMap() {
comparator = null;
}
/**
* 根據(jù)給定的comparator構(gòu)造一個(gè)空的/新的map
* 所有插入到map的key通過(guò)comparator比較器必須具備可比性
*（因?yàn)樘峁┝薱omparator比較器蒿往，所以key可以不用實(shí)現(xiàn)Comparable接口）
*
*
* @param comparator comparator如果為null,則使用自然順序
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* 根據(jù)給定個(gè)的map和key的自然順序構(gòu)造一個(gè)空的treemap
*
* 關(guān)于key的約束同上盛垦。
*
* 方法的時(shí)間復(fù)雜度為n*log(n)
*
* @param m 要放到treemap中的map
* @throws ClassCastException key不具備可比/排序性則拋此異常
* @throws NullPointerException 指定的map是null則拋NPE
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
//調(diào)用putAll存放m，后續(xù)分析
putAll(m);
}
/**
* 根據(jù)給定是sortedMap瓤漏，利用相同的排序方式構(gòu)造一個(gè)新的treemap
*
* 方法以限行時(shí)間運(yùn)行
*
* @param m sortedmap
* @throws NullPointerException 指定的map是null則拋NPE
*/
public TreeMap(SortedMap<K, ? extends V> m) {
//獲取sortedmap的comparator
comparator = m.comparator();
try {
//調(diào)用buildFromSorted來(lái)存放m
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
看完了上面幾個(gè)構(gòu)造函數(shù)腾夯，讓人印象比較深刻的是對(duì)于key的約束說(shuō)明
不指定comparator時(shí)，存放到map里的key必須實(shí)現(xiàn)Comparable接口
這里約束目的就是為了利用可比性來(lái)維護(hù)treemap的順序性赌蔑。
上面構(gòu)造函數(shù)中putAll和buildFromSorted沒(méi)有跟進(jìn)做具體分析俯在，放置在功能方法里一并介紹。
紅黑樹(shù)
看完變量和構(gòu)造函數(shù)娃惯，本來(lái)想直接分析功能方法跷乐，但是仔細(xì)一看，雖然TreeMap里紅黑樹(shù)的代碼跟HashMap本質(zhì)上是一樣的趾浅，但是代碼的結(jié)構(gòu)還是有較大區(qū)別愕提，所以先拿來(lái)來(lái)賞析。（我覺(jué)得TreeMap的紅黑樹(shù)代碼可讀性比HashMap來(lái)的高多了）
節(jié)點(diǎn)定義
依然是利用一個(gè)靜態(tài)內(nèi)部類(lèi)來(lái)定義樹(shù)節(jié)點(diǎn)皿哨，這里跟HashMap中的定義類(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;
/**
* 根據(jù)給定的key/value/parent創(chuàng)建一個(gè)新的單元節(jié)點(diǎn)（黑）
* 子樹(shù)為null
*
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* 返回key
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* 返回跟key關(guān)聯(lián)的value
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* 替換跟key關(guān)聯(lián)的value
*
* @return 返回舊值
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
/**
* 比較
*/
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
/**
* hashcode
*/
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
/**
* toString
*/
public String toString() {
return key + "=" + value;
}
}
左旋
這里的左旋跟HashMap還是比較相近的如输，不同點(diǎn)在于HashMap的入?yún)⒍嗔艘粋€(gè)root來(lái)用以指向根節(jié)點(diǎn)，而在TreeMap中央勒，root是一個(gè)成員變量不见。
private void rotateLeft(Entry<K,V> p) {
//null節(jié)點(diǎn)忽略
if (p != null) {
//取出p的右子樹(shù)
Entry<K,V> r = p.right;
//用r的左子樹(shù)替換p的右子樹(shù)
p.right = r.left;
//如果r的左子樹(shù)存在的話
//則將r的左子樹(shù)的父節(jié)點(diǎn)指向p
if (r.left != null)
r.left.parent = p;
//r的父節(jié)點(diǎn)指向p的父節(jié)點(diǎn)
//實(shí)質(zhì)上，就是r替換了p的位置
r.parent = p.parent;
//如果p節(jié)點(diǎn)不存在父節(jié)點(diǎn)
if (p.parent == null)
//那么替換了p節(jié)點(diǎn)后的r就是根節(jié)點(diǎn)
root = r;
else if (p.parent.left == p)
//如果p的父節(jié)點(diǎn)存在且p是左子樹(shù)
//則將替換p后的r設(shè)置為左子樹(shù)
p.parent.left = r;
else
//否則設(shè)置為右子樹(shù)
p.parent.right = r;
//p變成r的左子樹(shù)
r.left = p;
//修改引用
p.parent = r;
}
}
右旋
private void rotateRight(Entry<K,V> p) {
//null節(jié)點(diǎn)忽略
if (p != null) {
//取出p的左子樹(shù)l
Entry<K,V> l = p.left;
//用l的右子樹(shù)替換p的左子樹(shù)
p.left = l.right;
//如果l人右子樹(shù)存在
//則將l的右子樹(shù)的父節(jié)點(diǎn)指向p
if (l.right != null) l.right.parent = p;
//交換l和p的位置
l.parent = p.parent;
//如果p的父節(jié)點(diǎn)不存在
if (p.parent == null)
//那么替換了p節(jié)點(diǎn)后的l就是根節(jié)點(diǎn)
root = l;
else if (p.parent.right == p)
//如果p的父節(jié)點(diǎn)存在崔步，且p是原右子樹(shù)
//則將替換p后的l設(shè)置為右子樹(shù)
p.parent.right = l;
//否則設(shè)置為左子樹(shù)
else p.parent.left = l;
//修改引用
l.right = p;
p.parent = l;
}
}
插入平衡
插入平衡方法的實(shí)現(xiàn)就是我所說(shuō)的稳吮，我覺(jué)得比HashMap可讀性強(qiáng)的方法。TreeMap把節(jié)點(diǎn)的關(guān)系操作封裝成獨(dú)立方法了井濒，比如獲取父節(jié)點(diǎn)灶似、左子樹(shù)列林、右子樹(shù)等，會(huì)讓含義很清晰酪惭，如果類(lèi)似于HashMap是通過(guò)引用方式的話希痴，很容易源碼看著看著就暈乎乎了。
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
//新節(jié)點(diǎn)都為紅色
x.color = RED;
//x存在且c不是根節(jié)點(diǎn)且x的父節(jié)點(diǎn)為紅色
while (x != null && x != root && x.parent.color == RED) {
//如果x的父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左子樹(shù)的話
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//取出祖父節(jié)點(diǎn)的右子樹(shù)
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//判斷祖父節(jié)點(diǎn)右子樹(shù)是否為紅色
if (colorOf(y) == RED) {
//紅色
//將父節(jié)點(diǎn)變成黑色
setColor(parentOf(x), BLACK);
//祖父節(jié)點(diǎn)的右子樹(shù)變成黑色
setColor(y, BLACK);
//祖父節(jié)點(diǎn)變成紅色
setColor(parentOf(parentOf(x)), RED);
//將x的引用指向祖父節(jié)點(diǎn)
x = parentOf(parentOf(x));
} else {
//祖父節(jié)點(diǎn)右子樹(shù)為黑色
//x節(jié)點(diǎn)是父節(jié)點(diǎn)的右子樹(shù)
if (x == rightOf(parentOf(x))) {
//x引用指向父節(jié)點(diǎn)
x = parentOf(x);
//左旋
rotateLeft(x);
}
//將x的父節(jié)點(diǎn)變成黑色
setColor(parentOf(x), BLACK);
//x的祖父節(jié)點(diǎn)變成紅色
setColor(parentOf(parentOf(x)), RED);
//右旋
rotateRight(parentOf(parentOf(x)));
}
} else {
//如果x的父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右子樹(shù)的話
//取出祖父節(jié)點(diǎn)的左子樹(shù)
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//祖父節(jié)點(diǎn)左子樹(shù)為紅色
if (colorOf(y) == RED) {
//相關(guān)變色操作
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//祖父節(jié)點(diǎn)左子樹(shù)為紅色
//入股x是父節(jié)點(diǎn)的左子樹(shù)
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
//右旋
rotateRight(x);
}
//相關(guān)變色操作
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
//左旋
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
刪除平衡
刪除平衡也是類(lèi)似的撞蚕，代碼書(shū)寫(xiě)比較規(guī)范润梯，為了凸顯我懶，就不添加注釋了甥厦，把代碼貼出來(lái)纺铭，有緣人自行參悟。
/** From CLR */
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
羅列TreeMap的紅黑樹(shù)相關(guān)代碼刀疙，是想說(shuō)明TreeMap里面的實(shí)現(xiàn)比起HashMap可讀性更為強(qiáng)一些舶赔，但是其實(shí)質(zhì)都是一樣的，所以上面關(guān)于插入平衡和刪除平衡的過(guò)程這里不再細(xì)說(shuō)谦秧，之前格子的Java源碼閱讀之紅黑樹(shù)在HashMap中的應(yīng)用 - JDK1.8這篇博客里面有過(guò)步驟的相關(guān)描述竟纳，也有一些圖解，有興趣的可以了解一下疚鲤。
功能方法
接下來(lái)看下相關(guān)功能方法锥累，看下我們平時(shí)所使用的方法內(nèi)部是怎么實(shí)現(xiàn)的。
put
將指定的鍵值對(duì)存放到TreeMap集歇，不同于HashMap將元素通過(guò)HashCode分散到哈希桶里面桶略，TreeMap是通過(guò)比較器/自然順序的形式將元素存放到紅黑樹(shù)中來(lái)保證有序性。
下面開(kāi)始分析put方法诲宇。
/**
* 存放指定的鍵值對(duì)
* 如果指定的key存在际歼，舊的value將會(huì)被新的替換
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
*
* @return 舊的value值{@code key}, 如果之前不存在，則返回null
* (返回null也有可能key對(duì)應(yīng)的值是null)
* @throws ClassCastException 指定的key不具備可比性的話則拋此異常
* @throws NullPointerException 使用自然排序時(shí)指定的key為null/comparator不允許null的key姑蓝，則拋NPE
*
*/
public V put(K key, V value) {
//根節(jié)點(diǎn)
Entry<K,V> t = root;
//如果根節(jié)點(diǎn)還不存在(TreeMap是空的)
if (t == null) {
//這里的比較做一個(gè)類(lèi)型檢查
//可能null
compare(key, key); // type (and possibly null) check
//初始化一個(gè)節(jié)點(diǎn)
root = new Entry<>(key, value, null);
//size + 1
size = 1;
//修改計(jì)數(shù) + 1
modCount++;
//返回null
return null;
}
//如果TreeMap不為空
//定義比較值
int cmp;
//定義父節(jié)點(diǎn)
Entry<K,V> parent;
// 分離Comparator和比較路徑
Comparator<? super K> cpr = comparator;
//如果存在Comparator
if (cpr != null) {
//通過(guò)循環(huán)找到合適的節(jié)點(diǎn)
//通過(guò)二叉查找樹(shù)的性質(zhì)進(jìn)行查找
//知道找到合適的節(jié)點(diǎn)
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
//如果找到相同的key鹅心，則替換值后返回
return t.setValue(value);
} while (t != null);
}
//不存在比較器，則采用自然順序比較
else {
//自然順序比較不允許key為null
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
//同樣采用循環(huán)來(lái)查找插入位置
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);
}
//新建節(jié)點(diǎn)
Entry<K,V> e = new Entry<>(key, value, parent);
//根據(jù)比較結(jié)果纺荧，來(lái)決定將節(jié)點(diǎn)放置在左邊還是右邊
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//插入平衡
fixAfterInsertion(e);
//size + 1
size++;
//修改計(jì)數(shù) + 1
modCount++;
//返回null（執(zhí)行到這一步旭愧，證明未找到相同的key，如果有宙暇，則在上面就return了）
return null;
}
看完了put的输枯，再把之前構(gòu)造函數(shù)中的未加分析的putAll一并閱讀（完全無(wú)違和感）。
/**
* 將指定map中的元素都存放到當(dāng)前treemap
*
* @param map map
* @throws ClassCastException key不合法(參照構(gòu)造函數(shù)章節(jié))
* @throws NullPointerException 指定的map為null/或者存在null的key且treemap不允許null-key的情況下拋出NPE
*/
public void putAll(Map<? extends K, ? extends V> map) {
//獲取大小
int mapSize = map.size();
//treemap為空且指定的map不為空并且map是可排序的map
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
//獲取Comparator
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
//判斷Comparator是否跟當(dāng)前的一致
if (c == comparator || (c != null && c.equals(comparator))) {
//操作計(jì)數(shù) + 1
++modCount;
try {
//調(diào)用buildFromSorted進(jìn)行處理
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
//調(diào)用父類(lèi)的putAll
super.putAll(map);
}
通過(guò)分析以上的代碼客给，可以看出putAll里面的邏輯還是比較簡(jiǎn)單的，一是判斷當(dāng)前treemap是否為空肢簿，且給定map的大小合法靶剑，并且是給定的map是SortedMap的實(shí)例if (size==0 && mapSize!=0 && map instanceof SortedMap)蜻拨。
如果是，則取出比較器判斷后調(diào)用buildFromSorted進(jìn)行處理
如果不是桩引，則調(diào)用父類(lèi)的putAll進(jìn)行處理缎讼。
這里留有兩個(gè)疑問(wèn)，buildFromSorted和父類(lèi)的putAll究竟做了哪些處理來(lái)完成集合元素的存放呢坑匠？
下面一步步分析血崭，先從父類(lèi)的putAll看起 。
/**
* {@inheritDoc}
* 嗯厘灼，懶得翻譯了夹纫，反正我翻譯水平也比較差。
*
* @implSpec
* This implementation iterates over the specified map's
* <tt>entrySet()</tt> collection, and calls this map's <tt>put</tt>
* operation once for each entry returned by the iteration.
*
* <p>Note that this implementation throws an
* <tt>UnsupportedOperationException</tt> if this map does not support
* the <tt>put</tt> operation and the specified map is nonempty.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
是不是一目了然了设凹。如果上面提到的判斷if (size==0 && mapSize!=0 && map instanceof SortedMap)不成立舰讹，則調(diào)用父類(lèi)的putAll方法：通過(guò)循環(huán)，將元素一個(gè)個(gè)放到treemap當(dāng)中闪朱，這里的放置put就是在本章節(jié)開(kāi)頭分析的put方法月匣。
那么，還剩下一個(gè)疑問(wèn)奋姿，如果上面的判斷成立锄开，buildFromSorted又做了哪些操作呢？
/**
*
* 線性時(shí)間的樹(shù)構(gòu)造算法(根據(jù)排序數(shù)據(jù))
* 可以從迭代器/流當(dāng)中接受鍵值對(duì)
* 有很多方法入?yún)⒊剖撬坪踹€是比其他選擇更好（PS:我也不知道其他選擇是什么）
*
* 該方法接受的4種格式說(shuō)明：
*
* 1) Map.Entries迭代器. (it != null, defaultVal == null).
* 2) key的迭代器. (it != null, defaultVal != null).
* 3) 交替序列化的鍵值對(duì)流.(it == null, defaultVal == null).
* 4) 序列化的鍵流. (it == null, defaultVal != null).
*
* 假設(shè)調(diào)用此方法前comparator已經(jīng)被設(shè)置
*
* @param size 鍵/或者鍵值對(duì)的數(shù)量
* @param it 不為null的話, 新的entries通過(guò)這個(gè)迭代器創(chuàng)建
* @param str 不為null的話, 新的entries通過(guò)序列化流來(lái)創(chuàng)建
* 準(zhǔn)確點(diǎn)說(shuō)萍悴，it和str必須一個(gè)不為null
* @param defaultVal 不為null的話, 會(huì)作為默認(rèn)值
* @throws java.io.IOException 讀取流時(shí)可能會(huì)拋出NPE，如果str為null則不會(huì)發(fā)生這種情況
* @throws ClassNotFoundException 讀取對(duì)象是可能拋此異常.如果str為null則不會(huì)發(fā)生這種情況
*/
private void buildFromSorted(int size, Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
//設(shè)置size
this.size = size;
//調(diào)用buildFromSorted來(lái)確定root
//分割線之后繼續(xù)分析
//這里有個(gè)小插曲computeRedLevel
//computeRedLevel是根據(jù)節(jié)點(diǎn)數(shù)量來(lái)計(jì)算完全二叉樹(shù)的層級(jí)
//其實(shí)從名字看來(lái)粪狼，可以理解為計(jì)算紅色節(jié)點(diǎn)的層級(jí)
root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
it, str, defaultVal);
}
---------------------------------------------------
/**
* 計(jì)算紅色節(jié)點(diǎn)所在層級(jí)
* (完全二叉樹(shù)的層級(jí))
* 從0開(kāi)始
*
*/
private static int computeRedLevel(int sz) {
int level = 0;
for (int m = sz - 1; m >= 0; m = m / 2 - 1)
level++;
return level;
}
---------------------------------------------------
//個(gè)是buildFromSorted的實(shí)際實(shí)現(xiàn)方法
/**
* 遞歸的退腥、真正的實(shí)現(xiàn)方法(之前是幫助方法).
* 跟之前的方法比較，相同的參數(shù)命名具有相同的意義
* 增加的參數(shù)說(shuō)明在下方
*
* 假定在調(diào)用此方法之前已經(jīng)設(shè)置了樹(shù)圖的比較器和大小字段再榄。（它忽略了這兩個(gè)字段）狡刘。
*
* @param level 當(dāng)前樹(shù)的層級(jí). 初始化調(diào)用應(yīng)該為0.
* @param lo 子樹(shù)的首個(gè)節(jié)點(diǎn)索引. 初始化應(yīng)該為0.
* @param hi 子樹(shù)的尾節(jié)點(diǎn)索引. 初始化應(yīng)該為size - 1
* @param redLevel 節(jié)點(diǎn)該為紅色的層級(jí)，必須以size和computeRedLevel計(jì)算出來(lái)的相等
*/
@SuppressWarnings("unchecked")
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
/*
* 策略: 根節(jié)點(diǎn)是最接近中間節(jié)點(diǎn)的元素. 為了得到它,首先我們必須遞歸構(gòu)建完整的左子樹(shù),以便抓取所有的元素
* 然后我們可以繼續(xù)處理右子樹(shù)
*
* lo和li參數(shù)是為當(dāng)前子樹(shù)提取迭代器/流的最小和最大指標(biāo)困鸥，
* 它們實(shí)際上沒(méi)有索引嗅蔬，我們只是按順序處理，確保items被按相應(yīng)的順序處理疾就。
*
*/
//如果hi小于lo澜术，
if (hi < lo) return null;
//mid=(lo+hi)/2; - 無(wú)符號(hào)右移
int mid = (lo + hi) >>> 1;
//左子樹(shù)
Entry<K,V> left = null;
//如果lo小于mid
//遞歸構(gòu)造左子樹(shù)
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);
// extract key and/or value from iterator or stream
//從迭代器/流中獲取鍵值對(duì)
K key;
V value;
//使用迭代器
if (it != null) {
//沒(méi)有有默認(rèn)值
if (defaultVal==null) {
Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
key = (K)entry.getKey();
value = (V)entry.getValue();
} else {
//有默認(rèn)值
key = (K)it.next();
value = defaultVal;
}
} else { // use stream
//使用流
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
//創(chuàng)建節(jié)點(diǎn)
Entry<K,V> middle = new Entry<>(key, value, null);
// color nodes in non-full bottommost level red
//非null節(jié)點(diǎn)且是紅色層級(jí)的，染色成紅色
if (level == redLevel)
middle.color = RED;
//判斷左子樹(shù)是否為null
if (left != null) {
//指向左子樹(shù)
middle.left = left;
//修改引用
left.parent = middle;
}
//遞歸構(gòu)造右子樹(shù)
if (mid < hi) {
Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
middle.right = right;
right.parent = middle;
}
//到遞歸的最外層的話這里的middle就是最終的根節(jié)點(diǎn)
return middle;
}
到這里猬腰，關(guān)于TreeMap的put相關(guān)方法就分析完畢了鸟废，有幾個(gè)要點(diǎn)梳理一下
- 1、
put方法根據(jù)比較器/自然順序?qū)⒃胤胖玫郊t黑樹(shù)特定位置后姑荷，進(jìn)行插入平衡 - 2盒延、
putAll實(shí)際上有兩種情況缩擂，一個(gè)是迭代取出元素調(diào)用父類(lèi)的put，另外是調(diào)用buildFromSorted完成TreeMap構(gòu)造 - 3添寺、調(diào)用
buildFromSorted的前提是胯盯，入?yún)⒈仨毷?code>SortedMap的實(shí)例(還有其他限制，詳見(jiàn)上面的if條件) - 4计露、buildFromSorted里面有一個(gè)
computeRedLevel博脑，是用來(lái)計(jì)算紅色節(jié)點(diǎn)層級(jí)（也可以理解為計(jì)算完全二叉樹(shù)層級(jí)） - 5、實(shí)際實(shí)現(xiàn)
buildFromSorted的方法票罐，是一個(gè)遞歸調(diào)用的過(guò)程叉趣，通過(guò)middle，遞歸構(gòu)造左右子樹(shù)來(lái)完成整棵樹(shù)的構(gòu)建胶坠。
Go On君账，下面是remove的方法。
remove
/**
* 如果存在的話沈善，根據(jù)指定的key從treemap中移除指定的鍵值對(duì)
*
* @param key 要移除的鍵值對(duì)的key
* @return 和{@code key}相關(guān)聯(lián)的舊值
* 如果{@code key}.沒(méi)有映射的話為{@code null}乡数，返回null的時(shí)候也有可能和key相關(guān)聯(lián)的是null
* @throws ClassCastException 指定的key無(wú)法和map中的key進(jìn)行比較，則拋此異常
* @throws NullPointerException 指定的key是null且該treemap采取自然排序/comparator不允許null的key時(shí)闻牡，拋NPE
*/
public V remove(Object key) {
//根據(jù)key獲取指定元素節(jié)點(diǎn)
Entry<K,V> p = getEntry(key);
//為null則返回
if (p == null)
return null;
//取出舊節(jié)點(diǎn)的值
V oldValue = p.value;
//刪除元素
deleteEntry(p);
//返回舊值
return oldValue;
}
從源碼可以看出净赴，remove方法體里面有兩個(gè)關(guān)鍵調(diào)用，getEntry和deleteEntry罩润，深入了解一下玖翅。
/**
* 根據(jù)給定給定key，返回元素割以，如果沒(méi)存在金度，則返回null
*
* @throws ClassCastException 指定的key無(wú)法與map中的比較時(shí)，拋出此異常
* @throws NullPointerException 指定的key是null且該treemap采取自然排序/comparator不允許null的key時(shí)严沥，拋NPE
*/
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
// 判斷是否存在comparator
if (comparator != null)
//如果comparator存在的話猜极，調(diào)用getEntryUsingComparator
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
//利用二叉樹(shù)性質(zhì)，進(jìn)行循環(huán)搜索
while (p != null) {
//自然比較
int cmp = k.compareTo(p.key);
//根據(jù)比較結(jié)果消玄，決定取左子樹(shù)還是右子樹(shù)
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
//如果比較結(jié)果相等跟伏，則返回該元素
return p;
}
return null;
}
//繼續(xù)看getEntryUsingComparator方法
/**
* 通過(guò)comparator獲取元素的版本.從genEntry分離出來(lái)(整潔美觀性能beautiful~)
* (對(duì)于大多數(shù)方法來(lái)說(shuō)它是不值得的,因?yàn)榇蠖鄶?shù)方法較少依賴(lài)于比較器性能，但是在這里它就是醬紫的呀翩瓜，它是值得的)
*/
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
//取出比較器
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
//從根節(jié)點(diǎn)循環(huán)
while (p != null) {
//通過(guò)比較器獲取比較結(jié)果
int cmp = cpr.compare(k, p.key);
//根據(jù)比較結(jié)果受扳，決定取左子樹(shù)還是右子樹(shù)
//嗯，其他的就跟上面自然順序處理是一樣樣兒的
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
查找元素的方法還是比較簡(jiǎn)單易懂的兔跌，但是不能漏掉deleteEntry這個(gè)查找后刪除的方法勘高，其實(shí)這里的deleteEntry就是紅黑樹(shù)的節(jié)點(diǎn)刪除操作了，之前也貌似也分析過(guò)，這里還是把代碼和注釋貼來(lái)华望，也許你跟我一樣也是小懶蛋呢（科普一下：優(yōu)秀的懶人會(huì)有創(chuàng)新的层亿，因?yàn)椴幌胫貜?fù)勞動(dòng)）
/**
* 刪除p節(jié)點(diǎn)，然后處理刪除平衡
*/
private void deleteEntry(Entry<K,V> p) {
//首先立美，現(xiàn)實(shí)相關(guān)計(jì)數(shù)處理
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
//內(nèi)部嚴(yán)謹(jǐn)?shù)脑挘截恜的后置節(jié)點(diǎn)給p方灾，然后將p指向后置節(jié)點(diǎn)
//左右子樹(shù)都存在的情況
if (p.left != null && p.right != null) {
//獲取后置節(jié)點(diǎn)
Entry<K,V> s = successor(p);
//后置節(jié)點(diǎn)的相關(guān)值賦值給p
p.key = s.key;
p.value = s.value;
//p指向s
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
//開(kāi)始在替換節(jié)點(diǎn)進(jìn)行修正
//如果p的左右子樹(shù)都存在一個(gè)的話建蹄，則p在上面的條件分支里已經(jīng)指向s了
//取出替換節(jié)點(diǎn)
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//判斷替換節(jié)點(diǎn)是否存在
if (replacement != null) {
// Link replacement to parent
//修改父節(jié)點(diǎn)引用
replacement.parent = p.parent;
//如果p不存在父節(jié)點(diǎn)，那么替換p的replacement節(jié)點(diǎn)就是根節(jié)點(diǎn)了
//很好裕偿，登基了（朕一日不死洞慎，你們就都是太子）
if (p.parent == null)
root = replacement;
//如果p是父節(jié)點(diǎn)的左子樹(shù)
else if (p == p.parent.left)
//那么修改父節(jié)點(diǎn)的左子樹(shù)引用為新的替換節(jié)點(diǎn)
p.parent.left = replacement;
else
//否則修改右子樹(shù)引用
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
//p節(jié)點(diǎn)的相關(guān)引用置為null，以便后面的刪除平衡處理
p.left = p.right = p.parent = null;
// Fix replacement
//如果p節(jié)點(diǎn)是黑色節(jié)點(diǎn)的話嘿棘，則進(jìn)行刪除平衡
if (p.color == BLACK)
fixAfterDeletion(replacement);//這個(gè)方法在開(kāi)頭的紅黑樹(shù)說(shuō)明有劲腿，或者可以參考我的另外一篇hashmap紅黑樹(shù)博客
//如果替換節(jié)點(diǎn)不存在，且p的父節(jié)點(diǎn)也不存在
} else if (p.parent == null) { // return if we are the only node.
//則證明p的唯一的節(jié)點(diǎn)鸟妙，返回null
root = null;
} else { // No children. Use self as phantom replacement and unlink.
//p有父節(jié)點(diǎn)焦人，但是沒(méi)有子節(jié)點(diǎn)了
//判斷p的顏色是否為黑
if (p.color == BLACK)
//如果是，進(jìn)行刪除平衡
fixAfterDeletion(p);
//p的父節(jié)點(diǎn)存在
//判斷p是父節(jié)點(diǎn)的左子樹(shù)還是右子樹(shù)
//并進(jìn)行相關(guān)引用修改
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)
/**
* 返回后置節(jié)點(diǎn)如果存在的話重父，如果不存在花椭，返回null
*/
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
//t為null躲胳，則直接返回null
if (t == null)
return null;
//右子樹(shù)存在
else if (t.right != null) {
//取出右子樹(shù)
Entry<K,V> p = t.right;
//循環(huán)购岗，遍歷并循環(huán)取左子樹(shù)淘钟，取出最后一個(gè)
while (p.left != null)
p = p.left;
return p;
} else {
//左子樹(shù)存在
//取出父節(jié)點(diǎn)
Entry<K,V> p = t.parent;
//ch指向t
Entry<K,V> ch = t;
//現(xiàn)在的ch(t)是p的子樹(shù)
//循環(huán)(只要父節(jié)點(diǎn)存在与斤，且ch(t)節(jié)點(diǎn)是父節(jié)點(diǎn)的右子樹(shù)的話)
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
//可以看出來(lái)裳仆，取出后置節(jié)點(diǎn)是這么處理的：
1卸耘、如果t的右子樹(shù)存在的話坦辟，就一路向左下遍歷诅岩，直到null
2折柠、如果t的左子樹(shù)存在的話宾娜，就一路向向上遍歷(t必須是父節(jié)點(diǎn)的右子樹(shù))，直到不符合情況
get
(⊙o⊙)…
如果仔細(xì)看了remove章節(jié)的話液走，其實(shí)這個(gè)章節(jié)可以略過(guò)了碳默。
因?yàn)間et屬于門(mén)面方法，實(shí)際實(shí)現(xiàn)也是由getEntry提供的缘眶。
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
containsKey/containsValue
判斷TreeMap是否存在對(duì)應(yīng)的key或者對(duì)應(yīng)的value嘱根。
判斷key比較簡(jiǎn)單，跟上面get章節(jié)是相同道理的巷懈，根據(jù)key去獲取元素该抒，并判斷元素是否為null。
判斷value跟判斷key不一樣顶燕，但是邏輯也很清晰凑保，首先取出首個(gè)元素冈爹，然后循環(huán)迭代，用指定value和每個(gè)元素的value做比較欧引，相同則返回频伤。
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
--------------------------------------------------
public boolean containsValue(Object value) {
//迭代判斷
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
forEach
循環(huán)迭代，并對(duì)每個(gè)元素做指定的操作(action)芝此。
這里的循環(huán)迭代跟上面的containsValue是一樣的憋肖，不通點(diǎn)在于containsValue是對(duì)每個(gè)元素執(zhí)行判斷，而forEach是對(duì)每個(gè)元素執(zhí)行相應(yīng)的action婚苹。
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
int expectedModCount = modCount;
for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
action.accept(e.key, e.value);
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
entrySet
本來(lái)不打算把這個(gè)拿出來(lái)分析的岸更，因?yàn)橥暾姆治銎鶎?shí)在是太長(zhǎng)了。
但是既然都這么長(zhǎng)了膊升，還在乎差這一截嗎~
這個(gè)方法我們用的也是相對(duì)比較頻繁的怎炊，單看entrySet方法根本沒(méi)什么好看的，很簡(jiǎn)單廓译，內(nèi)部有一個(gè)entrySet變量评肆，如果未初始化，則new一個(gè)非区，如果已初始化糟港，則返回。
public Set<Map.Entry<K,V>> entrySet() {
EntrySet es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
}
來(lái)看一下EntrySet的數(shù)據(jù)結(jié)構(gòu)院仿，它是TreeMap的內(nèi)部類(lèi)秸抚，并且繼承了AbstractSet,并實(shí)現(xiàn)了相關(guān)方法，用過(guò)Set的小伙伴應(yīng)該相熟悉歹垫。
// TreeMap.java 1057行
//Entry定義
class EntrySet extends AbstractSet<Map.Entry<K,V>> {
/**
* 返回迭代器
*/
public Iterator<Map.Entry<K,V>> iterator() {
//這里調(diào)用的getFirstEntry方法剥汤，之前分析過(guò)
//獲取了首節(jié)點(diǎn)元素后，創(chuàng)建一個(gè)EntryIterator
//這里迭代器相關(guān)代碼不貼了排惨，有興趣的可以自行了解
//TreeMap 1238行
return new EntryIterator(getFirstEntry());
}
/**
* 判斷是否包含元素o
*/
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object value = entry.getValue();
Entry<K,V> p = getEntry(entry.getKey());
return p != null && valEquals(p.getValue(), value);
}
/**
* 移除元素o
*/
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object value = entry.getValue();
Entry<K,V> p = getEntry(entry.getKey());
if (p != null && valEquals(p.getValue(), value)) {
deleteEntry(p);
return true;
}
return false;
}
public int size() {
return TreeMap.this.size();
}
public void clear() {
TreeMap.this.clear();
}
public Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
}
}
單從上面的源碼看來(lái)吭敢，entrySet其實(shí)也沒(méi)什么好分析的，不過(guò)Set里面還是有很多方法在平時(shí)會(huì)用到的暮芭，之后找個(gè)時(shí)間鹿驼，專(zhuān)門(mén)開(kāi)一篇分析Set好了。
天色已晚辕宏，各位小伙伴下車(chē)洗洗睡吧畜晰。
總結(jié)
嗯，沒(méi)有總結(jié)瑞筐，都在上面了凄鼻。
image
溜了溜了。給個(gè)贊唄。
