完整代碼:代碼
前言
在寫這篇文章之前,我針對紅黑樹參考算法導(dǎo)論寫了一篇文章圖解紅黑樹-算法導(dǎo)論-java實現(xiàn)基于HashMap1.8,里面的的插入和刪除以及旋轉(zhuǎn)就是用的HashMap1.8里面的代碼,所以里面細(xì)致地分析了
balanceDeletion,balanceInsertion,rotateLeft,rotateRight,那這篇主要分析TreeNode中去其他的方法以及一些HashMap中TreeNode新加入的屬性和操作.
往紅黑樹中插入元素 putTreeVal方法
在看
putTreeVal方法前,先看這幾個函數(shù),因為putTreeVal在函數(shù)體中有調(diào)用這幾個函數(shù)
comparableClassFor方法
/**
*
* @param x 對象x
* @return 如果x所屬的類實現(xiàn)了Comparable<T>接口,并且T是x類 比如 class Person implements Comparable<Person>
* 如果class Person 或者類似于 class Person implements Comparable 或者 class Person implements Comparable<String>都會返回null
*/
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // 如果是String類直接返回了
return c;
/**
* getGenericInterfaces():
* Returns the Types representing the interfaces directly implemented
* by the class or interface represented by this object.
* 就是返回c類實現(xiàn)的所有接口
*/
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
/**
* Comparable<Person> 如果此接口含有泛型 并且原型class是Compable類
* getActualTypeArguments() 返回這個類里面所有的泛型 返回一個數(shù)組
* as.length == 1 && as[0] == c 是為了保證Comparable<T>里面只有一個泛型并且就是傳入的類c
*/
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
給一個最直觀的測試讓大家明白這個函數(shù)的作用.
| Person類的定義 | 調(diào)用 | 返回 |
|---|---|---|
class Person |
comparableClassFor(new Person("Tom", 12)) |
null |
class Person implements Comparable |
comparableClassFor(new Person("Tom", 12)) |
null |
class Person implements Comparable<String> |
comparableClassFor(new Person("Tom", 12)) |
null |
class Person implements Comparable<Person> |
comparableClassFor(new Person("Tom", 12)) |
Person |
compareComparables方法
方法很簡單,就是在滿足條件的情況下調(diào)用
CompareTo方法返回,否則返回0
/**
* Returns k.compareTo(x) if x matches kc (k's screened comparable
* class), else 0.
* 如果類不同就返回0 否則就返回調(diào)用compareTo比較后的結(jié)果
*/
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
tieBreakOrder方法
identityHashCode()和hashCode()的區(qū)別會在另外一篇博客待完成中分析
/**
* a或者b為null或者如果a和b同屬一個類就調(diào)用系統(tǒng)的identityHashCode
*/
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
root方法
因為當(dāng)前的節(jié)點可能不是紅黑樹的根,為什么呢?
1.紅黑樹中的每個節(jié)點都是
TreeNode節(jié)點,所以每個節(jié)點都可以調(diào)用TreeNode中的方法.
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
find方法
TreeNode<K,V> find(int h, Object k, Class<?> kc)方法就是二叉樹的查找了,查找該k和對應(yīng)的h是否存在在以當(dāng)前節(jié)點為頭結(jié)點的子樹中了.
代碼就不貼了,比較簡單.
putTreeVal方法
因為紅黑樹插入的時候需要比較
TreeNode,這里是把節(jié)點的hash值來比較大小,具體比較機制在代碼的注釋中有解釋.
至于為什么不直接用
CompareTo方法來比較,因為在HashMap 1.7的時候沒有引入紅黑樹,所以大部分的代碼的Key是可能沒有實現(xiàn)Comparable接口,因此我猜應(yīng)該是為了兼容的問題.
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
//找到紅黑樹的根
TreeNode<K,V> root = (parent != null) ? root() : this;
/**
* for 循環(huán)去尋找到該節(jié)點應(yīng)該插入的位置,TreeNode之間的比較是通過該節(jié)點的hash值
* 1. 如果該節(jié)點已經(jīng)存在 那就直接返回
* 2. 如果該節(jié)點hash值小于該節(jié)點的hash值 往左側(cè)
* 3. 如果該節(jié)點hash值小于該節(jié)點的hash值 往右側(cè)
*
*/
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h) // 左側(cè)
dir = -1;
else if (ph < h) // 右側(cè)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) //已經(jīng)存在
return p;
/**
* hash值相等但是key值沒有匹配上會進行以下操作
* 1. 調(diào)用comparableClassFor先看該k是否已經(jīng)實現(xiàn)compareable<k.class>接口
* 2. 如果實現(xiàn)了Compareable<k.class>接口 就進行compareComparables方法看看是否可以比較出結(jié)果
* 3. 如果還是沒有比較出結(jié)果,就去左右子樹中搜索有沒有該節(jié)點(注意只搜索一次)
* 4. 如果左右子樹中也沒有該節(jié)點,說明必須要插入該節(jié)點到此紅黑樹中,所以就調(diào)用tieBreakOrder強行分出大小
*/
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
/**
* 觀察當(dāng)前節(jié)點是進入左側(cè) 還是進入右側(cè) 還是插入
* 如果是插入的時候會進入if block 中的內(nèi)容
*/
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); //生成節(jié)點
//插入到紅黑樹中
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//插入到鏈表中
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
/**
* 調(diào)整紅黑樹返回新的節(jié)點值
* 把返回新的節(jié)點值移到鏈表的頭
*/
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
balanceInsertion方法在圖解紅黑樹-算法導(dǎo)論-java實現(xiàn)基于HashMap1.8已經(jīng)分析過了
由于
HashMap在樹化的過程中既保持了紅黑樹的結(jié)構(gòu),并且也保持了原先鏈表中的結(jié)構(gòu),只不過這個鏈表與其他沒有樹化的鏈表的區(qū)別在于樹化的鏈表的節(jié)點類型是TreeNode,而沒有樹化的鏈表的節(jié)點類型是Node,所以當(dāng)新節(jié)點在插入的時候既要往紅黑樹中插入,也要往鏈表中插入.
所以在
balanceInsertion的過程中有可能會通過旋轉(zhuǎn)root會發(fā)生改變,因此moveRootToFront的作用就是把root節(jié)點move到鏈表的頭.
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
//計算在哪個bin
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//如果鏈表的頭不是紅黑樹的頭節(jié)點 則把root移到頭節(jié)點 也就是first的前面
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
// 檢查一下紅黑樹的各個成員變量是否正常
assert checkInvariants(root);
}
}
checkInvariants方法
循環(huán)檢查紅黑樹每個節(jié)點的成員變量是否正常.
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
樹化 treeify方法
調(diào)用該方法的
TreeNode節(jié)點是一個從原先的Node類型的鏈表轉(zhuǎn)化成TreeNode中的頭節(jié)點,看原因在哪里? 在treeifyBin方法中可以找到答案的.
/**
* @return 調(diào)用該方法的時候this就已經(jīng)是一個TreeNode了
* 而且整個鏈表的節(jié)點類型已經(jīng)從Node轉(zhuǎn)換成TreeNode 但是順序沒有變化
*/
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;
// 插入的是第一個元素 并給root賦值
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//插入到紅黑樹中的位置 邏輯跟putTreeVal類似
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;
}
}
}
}
// 把root節(jié)點移到鏈表頭
moveRootToFront(tab, root);
}
鏈表化untreeify
當(dāng)紅黑樹中的節(jié)點個數(shù)等于6,就把紅黑樹轉(zhuǎn)化成簡單的鏈表類型
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
//將Node轉(zhuǎn)化成TreeNode
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
擴容時轉(zhuǎn)移節(jié)點 split
思想與鏈表的轉(zhuǎn)移節(jié)點類似,根據(jù)
rehash的特殊性,把紅黑樹拆成兩個鏈表,然后再根據(jù)兩個鏈表的長度決定是否樹化或者鏈表化.對原理不明白的可以參考另一篇文章HashMap1.8 源碼解析(1)--插入元素的rehash部分.
有人可能對鏈表化有疑問？畢竟已經(jīng)是鏈表了啊,為什么還需要進行鏈表化,答案是因為此時的鏈表是
TreeNode類型的,需要轉(zhuǎn)化成Node類型的.
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// 將紅黑樹根據(jù)rehash分成兩個鏈表
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//根據(jù)每個鏈表的長度來決定是樹化還是鏈表化
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
小例子
public class Person {
String name;
int age;
public Person() {}
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj instanceof Person) {
Person p = (Person)obj;
return p.name.equals(this.name);
}
return false;
//return true;
}
@Override
public int hashCode() {
// TODO Auto-generated method stub
return age;
}
}
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
public class TestHashMap {
public static void main(String[] args) {
test_redblacktree_put();
//test_system_hashcode();
}
public static void test_redblacktree_put() {
HashMap<Person, Integer> map = new HashMap<>(64);
char[] strs = "SEARCHXMPL".toCharArray();
for (int i = 0; i < strs.length; i++) {
//System.out.println("insert into " + strs[i]);
map.put(new Person(strs[i] + "", (strs[i] - '0') * 64), i);
printMap(map);
}
map.put(new Person("Z", ('M' - '0') * 64), -1); //will goto tieBreak block
printMap(map);
}
private static void printMap(HashMap<Person, Integer> map) {
HashMap.Node<Person, Integer>[] table = map.table;
for (int i = 0; i < table.length; i++) {
HashMap.Node<Person, Integer> e;
if ((e = table[i]) != null) {
System.out.print(i + ":");
System.out.print(e);
HashMap.Node<Person, Integer> p;
while ((p = e.next) != null) {
System.out.print("->" + p);
e = e.next;
}
System.out.println();
}
}
}
}
簡單看一下結(jié)果:
插入到
P時才進行樹化
image.png
樹化結(jié)束時的紅黑樹結(jié)構(gòu)以及鏈表結(jié)構(gòu) 此時
E是鏈表和紅黑樹的頭
當(dāng)插入節(jié)點
L時,紅黑樹的root節(jié)點發(fā)生了變化成為了M,通過moveRootToFront方法把M移到E的前面成為鏈表的頭結(jié)點.
image.png
建議感興趣的人可以下載完整代碼自己調(diào)試一下看看結(jié)果如何,對理解紅黑樹會有更清晰些.
至此
HashMap中TreeNode所有的方法都已經(jīng)分析了,希望可以對你有所幫助,如果哪里寫得有問題,還請指正哈.
1.HashMap1.8 源碼解析(1)--插入元素
2.HashMap1.8 源碼解析(2)--刪除元素
3.HashMap1.8 源碼解析(3)--TreeNode(紅黑樹)包括每一個方法
4.HashMap1.8 源碼解析(4)--遍歷元素
參考
1.
java1.8源碼
