前言
從jdk8.0開始HashMap進行了一次革新焚虱，為了提高查找效率在哈希桶內(nèi)元素超過8個時自動變?yōu)榧t黑樹結(jié)構(gòu)。
紅黑樹到底是為了解決什么問題存在的沾鳄？它又是怎么出現(xiàn)的翔烁？我們首先要理解一顆二叉查找樹辉哥。
二叉查找樹或者是一棵空樹兜喻，或者是具有下列性質(zhì)的二叉樹：
（1）若左子樹不空暇赤，則左子樹上所有結(jié)點的值均小于或等于它的根結(jié)點的值匀油；
（2）若右子樹不空稠炬，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值空镜；
（3）左杏糙、右子樹也分別為二叉查找樹贩耐；
.
當然如果要說二叉查找樹的話我們必須從符號表說起耻瑟，可我們今天的目的是為了簡述紅黑樹旨指，所以二叉查找樹的各種實現(xiàn)就當大家都已經(jīng)懂得。那為什么會出現(xiàn)紅黑樹呢喳整，我們發(fā)現(xiàn)一種情況當輸入的鍵值對鍵值按升序或者降序插入的時候谆构，會有下圖的情況出現(xiàn)
紅黑樹.png而這種情況也是最糟糕的情況假設(shè)我們要查找鍵為5的結(jié)點，那么花費的時間就是最長的了框都，我們發(fā)現(xiàn)其實查找時間其實跟樹的高度應(yīng)該是呈現(xiàn)一種正比的關(guān)系搬素。
那么可能有些同學想到了平衡二叉查找樹，也就是任何節(jié)點的兩個子樹的高度最大差別為一。但是我們發(fā)現(xiàn)一個問題熬尺，那就是每次插入或者刪除需要平衡次數(shù)非常多摸屠。那么有什么什么折中的方案既能保證能正常二叉查找樹的性質(zhì)又能保證查找的效率。
紅黑樹
沒錯就是紅黑樹粱哼，不過為了理解紅黑樹我們需要做一些準備工作季二，首先我們要了解一下B-樹中最簡單的2-3樹。
這是一顆很神奇的樹揭措，包含2-結(jié)點(1個鍵兩個鏈接)和3-結(jié)點(2個鍵3個鏈接)胯舷。
我們只要記住幾點就是一個新的鍵插入2-結(jié)點直接變3-結(jié)點，
而當要插入到3-結(jié)點時绊含，那么變成4-結(jié)點桑嘶，4-結(jié)點中間的鍵值上升到父結(jié)點直到父節(jié)點是一個2-結(jié)點
或者到了根節(jié)點還不是2-結(jié)點那么根節(jié)點直接分解使高度加一
可能覺得2-3樹已經(jīng)完美解決我們的問題了,但現(xiàn)實往往不盡人意，為什么呢艺挪？不翩？
首先表示一顆2-3樹光表示2-結(jié)點和3-結(jié)點和它們之間的轉(zhuǎn)換就需要花費力氣兵扬，而且我們可能需要要跟結(jié)點之內(nèi)的鍵值進行比較麻裳，而它實際插入情況7種，代表著光判斷起碼寫7個if器钟，2-3樹解決我們的問題津坑，可是實際書寫顯得比較復雜
我們需要一種簡單的數(shù)據(jù)結(jié)構(gòu)來解決我們的問題對了就是紅黑樹，它其實就是2-3樹的變形.它其中有兩種鏈接一種是紅鏈接一種是黑鏈接(指向的結(jié)點顏色就是鏈接顏色)傲霸，用這兩種鏈接就能表示我們2-3樹疆瑰。如下圖。
當然紅黑樹有以下幾個特點:
1.紅鏈接均為左鏈接昙啄。
2.沒有任何一個結(jié)點和兩條紅鏈接相連穆役。
3.而且它是完美黑色平衡的(葉子結(jié)點到根結(jié)點黑色鏈接數(shù)量都是相同的)。
但是現(xiàn)實是殘酷的梳凛，我們在對紅黑樹做操作的時候是有可能出現(xiàn)紅色右鏈接或者連續(xù)兩條紅色鏈接耿币。我們這時候可以通過旋轉(zhuǎn)或者上移中鍵進行操作而對其進行操作
public class RBBST<Key extends Comparable<Key>, Value> {
private Node root;
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
private Node left;
private Node right;
private boolean color;
private Key key;
private Value val;
private int N;
public Node(boolean color, Key key, Value val, int N) {
this.color = color;
this.key = key;
this.val = val;
this.N = N;
}
}
public int size() {
return size(root);
}
private int size(Node n) {
if(n==null) {
return 0;
}
return n.N;
}
private boolean isRed(Node n) {
if(n==null) return false;
return n.color == RED;
}
private Node rotateLeft(Node n) {
Node x = n.right;
n.right = x.left;
x.left = n;
x.color = n.color;
n.color = RED;
x.N = n.N;
n.N = size(n.left)+size(n.right)+1;
return x;
}
private Node rotateRight(Node n) {
Node x = n.left;
n.left = x.right;
x.right = n;
x.color = n.color;
n.color = RED;
x.N = n.N;
n.N = size(n.left)+size(n.right)+1;//變了 變成x了
return x;
}
private void change2Conn(Node n) {
n.left.color = BLACK;
n.right.color = BLACK;
n.color = RED;
//return n;還是原來的
}
public void put(Key key, Value val) {
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node n, Key key, Value val) {
if(n==null) {
return new Node(RED, key, val, 1);
}
int cmp = key.compareTo(n.key);
if(cmp<0) n.left = put(n.left, key, val);
else if(cmp>0) n.right = put(n.right, key, val);
else n.val = val; //find key
if(!isRed(n.left)&&isRed(n.right)) n = rotateLeft(n);
if(isRed(n.left)&&isRed(n.left.left)) n = rotateRight(n);
if(isRed(n.left)&&isRed(n.right)) change2Conn(n);
n.N = size(n.left) + size(n.right) + 1;
return n;
}
}
你以為到這里就完了嗎，本著求知的態(tài)度我們繼續(xù)講一講HashMap這個Java里面無比精妙的類
HashMap 紅黑樹實現(xiàn)
就看兩段代碼理解了HashMap的紅黑樹實現(xiàn)也就大致理解了
左旋轉(zhuǎn)
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
略微一看很難懂,這完全與我們自己的實現(xiàn)不同呀,傳兩個結(jié)點進來這是干什么韧拒？
跳過我們看具體插入的實現(xiàn)
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
是否感覺略微的不適與暈眩淹接，但是你耐著性子看下去發(fā)現(xiàn)邏輯竟是如此的簡單。
root代表著在Node[]這個表中每一個位置上第一個結(jié)點,而x就是我們需要插入這個位置的結(jié)點當然如果兩者的key.equals(root.key)其實返回false不然就覆蓋了
當x的父親結(jié)點為空時叛溢，很明顯它就直接返回塑悼。為了幫助更好理解這段代碼我們嘗試閱讀這么兩個函數(shù)
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
上面這一段是當一個哈希桶元素數(shù)超過8且其中表的長度大于64的時候發(fā)生的對哈希桶進行樹型化。我們看到一開始是對根結(jié)點進行賦值的楷掉，但是中間插入了
balanceInsertion()這個函數(shù)意味著root是為了滿足紅黑樹而不斷變化的厢蒜，而其中的moveRootToFront()是當本身在哈希桶第一個位置的元素不是root時進行把root賦值到哈希桶的第一個位置的值大概意思就是本來是以鏈表的形式存的，然后不斷循環(huán)遍歷已經(jīng)通過
treeifyBin()中的replacementTreeNode()從Node類型變?yōu)門reeNode類型的結(jié)點然后每次都循環(huán)都相當于對紅黑樹插入一個結(jié)點，當然插入后需要修復紅黑樹看到這里我們可能明白了
rotateleft()的作用了,跟普通紅黑樹的左旋差不多郭怪，就是把右子樹的左子樹掛在右子樹的父親結(jié)點的左子樹的地方支示，而右子樹又變成它父親結(jié)點的父親，成為它父親結(jié)點的父親結(jié)點的兒子鄙才。可是有一點筆者邏輯思維有點混亂的是它的red屬性是怎么變換颂鸿，好像并不是按照正常方式左旋變換,因為左旋方法里面除了當是根結(jié)點的時候會讓其變?yōu)閒alse，而沒有任何地方作出改變了攒庵。
