本文作者：黃海燕，叩丁狼進階講師。原創文章，轉載請注明出處。
##前言
之前很多小夥伴問我怎麼看源代碼,還有就是越來越多的程式員都想要看源代碼,搞懂底層原理,但是感覺源代碼非常的晦澀難懂,不夠直接和清晰,是以我希望這篇文章能夠快速帶同學們看懂java源碼,更加深入的學習java,幫助小夥伴們節約學習的時間成本.
##1.樹的介紹
- 什麼是樹結構?其實就是一個節點下面有多個子節點,我們稱之為樹結構,如下圖:
- 普通節點：擁有子節點的節點。
- 葉子節點：沒有子節點的節點。
什麼是二叉樹?
- 二叉樹就是一個節點最多隻能有2個子節點,分為左節點和右節點,如下圖:
一起來看源代碼-01TreeMap添加操作
什麼是排序二叉樹?
- 若左子樹不為空，則左子樹所有節點的值小于根節點的值。
-
若右子樹不為空，則右子樹所有節點的值大于根節點的值。
如圖:
一起來看源代碼-01TreeMap添加操作
什麼是紅黑樹?
紅黑樹其實是一個平衡排序二叉樹,屬于查詢高效的樹結構.請看下圖:
查詢元素6普通的二叉樹需要操作6次,紅黑樹隻需要操作4次,是以紅黑樹查詢更加高效.
##1.TreeMap的結構介紹
###1.1 結構關系
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
繼承關系:
- 父類AbstractMap,讓子類擁有基本Map的方法,比如增(put)删(remove)查(get)等方法.
實作關系:
- NavigableMap:父接口為SortedMap,是以NavigableMap為可排序接口,表示TreeMap但是一個排序的Map:
- Cloneable:标記型的接口，内部都沒有方法和屬性，實作 Cloneable來表示該對象能被克隆，能使用Object.clone()方法。如果沒有實作 Cloneable的類對象調用clone()就會抛出CloneNotSupportedException。
- Serializable:标記型的接口，内部都沒有方法和屬性，實作Serializable表示可進行序列化和反序列化,表示能夠使用在ObjectOutputStream.writeObject())和ObjectInputStream.readObject()
###1.2 基本成員組成
/**
* 比較器:類似于一個"裁判",用于比較插入對象和樹節點的内容大小
* 因為TreeMap是一個紅黑樹,紅黑樹是一個排序二叉樹,插入元素的時候需要進行排序,排序可以使用比較器中的方式排序
*/
private final Comparator<? super K> comparator;
/**
* 根節點
*/
private transient Entry<K,V> root;
/**
* 樹的元素個數
*/
private transient int size = 0;
/**
* 操作次數:增加和删除操作數都會加1,用于控制并發修改異常
*/
private transient int modCount = 0;
通過root根節點可以看出一個節點(元素)就是一個Entry對象,是以一個節點(元素)中包含多個資料.結構如下:
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;//顔色
節點表示如下:
###1.3添加操作:
public V put(K key, V value) {
Entry<K, V> t = root;//和插入節點進行比較的樹節點
//根節點為空
if (t == null) {
compare(key, key); //key比key,自己比較自己,目的是想要檢查類型,確定傳入了比較器或者是key實作了可比較接口
//建立了一個沒有父節點的新的節點,作為根節點
root = new Entry<>(key, value, null);
size = 1;//元素個數為1
modCount++;//操作數+1
return null;//傳回空,根節點添加結束
}
int cmp;//表示比較結果
Entry<K, V> parent;
// cpr臨時表示比較器
Comparator<? super K> cpr = comparator;
if (cpr != null) {//比較器不為空,就使用比較器比較元素
do {
parent = t;//父節點為t
cmp = cpr.compare(key, t.key);//通過比較器對key和樹節點比較得到比較結果
if (cmp < 0)//比較結果小于0,表示插入的元素比樹節點小
t = t.left;//t往左走
else if (cmp > 0)//比較結果大于0,表示插入的元素比樹節點大
t = t.right;//t往右走
else//cmp比較結果為0,覆寫節點中的value
return t.setValue(value);
} while (t != null);//直到t為空停下來,保證插入的是節點
} else {//比較器為空就使用元素中的比較方法
if (key == null)//插入的元素key為空,沒辦法和樹結構中的元素比較,抛出空指針異常
throw new NullPointerException();
/*
* key進行強轉,看一下key是否實作了Comparable接口,是否存在compareTo方法,
* 如果沒有實作接口,也就不确定有沒有compareTo方法了,沒辦法進行比較了
*/
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;//父節點為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)//如果比較結果小于0插入左邊
parent.left = e;
else
parent.right = e;//否則插入右邊
fixAfterInsertion(e);//對樹進行自平衡
size++;
modCount++;
return null;
}
###1.4 元素插入後對樹進行自平衡
紅黑樹的自平衡規則:(目标就是黑色節點平衡)
- 每個節點都隻能是紅色或者黑色
- 根節點是黑色
- 每個葉節點（空節點）是黑色的。
- 如果一個結點是紅的，則它兩個子節點都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點。
- 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
private void fixAfterInsertion(Entry<K, V> x) {//x表示插入的節點,
x.color = RED;//設定插入的節點為紅色
//當x不為空,x不為根節點,x的父節點為紅色就需要進行平衡
while (x != null && x != root && x.parent.color == RED) {
//x的父節點等于x的爺爺節點的左邊,其實就是說x的父節點是否屬于左節點
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//擷取x的爺爺節點的右節點
Entry<K, V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {//爺爺節點的右節點為紅色
setColor(parentOf(x), BLACK);//将x的父節點設定為黑色
setColor(y, BLACK);//x父節點的兄弟節點設定為黑色
setColor(parentOf(parentOf(x)), RED);//爺爺節點設定為紅色
x = parentOf(parentOf(x));//x指向原來的爺爺節點,目的是為了繼續往上修改顔色
} else {//不為紅色,也就是子節點和父節點的顔色出現沖突
//如果x等于父節點的右節點
if (x == rightOf(parentOf(x))) {
//操作的x為x的父節點
x = parentOf(x);
//左自旋,旋轉後x為原來x的子節點
rotateLeft(x);
}
//x的父節點設定為黑色
setColor(parentOf(x), BLACK);
//x的爺爺節點設定為紅色
setColor(parentOf(parentOf(x)), RED);
//右自旋
rotateRight(parentOf(parentOf(x)));
}
} else {
//y為爺爺節點的左節點(父節點的兄弟節點)
Entry<K, V> y = leftOf(parentOf(parentOf(x)));
//如果y的顔色為紅色
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);//父節點設定為黑色
setColor(y, BLACK);//y設定為黑色
setColor(parentOf(parentOf(x)), RED);//爺爺節點設定為紅色
x = parentOf(parentOf(x));//x指向原來的爺爺節點,目的是為了繼續往上修改顔色
} else {
//如果父節點的左節點為x
if (x == leftOf(parentOf(x))) {
//x為父節點
x = parentOf(x);
//右自旋,旋轉後x為原來x的子節點
rotateRight(x);
}
setColor(parentOf(x), BLACK);//父節點設定為黑色
setColor(parentOf(parentOf(x)), RED);//爺爺節點設定為紅色
rotateLeft(parentOf(parentOf(x)));//左自旋
}
}
}
root.color = BLACK;//保證根節點必須為黑色
}
###1.5左自旋
private void rotateLeft(Entry<K, V> p) {
//p不為空
if (p != null) {
//r表示p的右節點
Entry<K, V> r = p.right;
//将r的左節點 指派給 p的有右節點
p.right = r.left;
//如果r的左節點不為空
if (r.left != null)
//r的左節點的父節點為p
r.left.parent = p;
//r的父節點為p的父節點
r.parent = p.parent;
//如果p的父節點為空
if (p.parent == null)
//r作為根節點
root = r;
//如果p的父節點的左節點等于p,說明p為父節點的左節點
else if (p.parent.left == p)
//p的父節點的左節點為r
p.parent.left = r;
else
//p的父節點的左節點為r
p.parent.right = r;
//r的左節點為p
r.left = p;
//p的父節點為r
p.parent = r;
}
}
###1.6右自旋
private void rotateRight(Entry<K, V> p) {
//p不為空
if (p != null) {
//l表示p的左節點
Entry<K, V> l = p.left;
//p的左節點指向l的右節點
p.left = l.right;
//如果l的右節點不為空
if (l.right != null)
//l的右節點的父節點為p
l.right.parent = p;
//l的父節點指向p的父節點
l.parent = p.parent;
//如果p的父節點為空
if (p.parent == null)
//l為根節點
root = l;
//如果p的父節點的右節點為p
else if (p.parent.right == p)
//p的父節點的右節點為l
p.parent.right = l;
else
//p的父節點的左節點為l
p.parent.left = l;
//l的右節點指向p
l.right = p;
//p的父節點指向l
p.parent = l;
}
}
###1.7案例示範:
示範代碼如下:
代碼執行步驟如下: