文章出處
文章列表
//對treeMap的紅黑樹理解注解. 2017.02.16 by 何錦彬 JDK,1.7.51
/** From CLR */ private void fixAfterInsertion(Entry<K, V> x) { //新加入紅黑樹的默認節點就是紅色 x.color = RED; /** * 1. 如為根節點直接跳出 */ while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //如果X的父節點（P）是其父節點的父節點（G）的左節點 //即 下面這種情況 /** * G * P(RED) U */ //獲取其叔(U)節點 Entry<K, V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { // 這種情況 /** * G * P(RED) U(RED) * X */ //如果叔節點是紅色的（父節點有判斷是紅色）. 即是雙紅色，比較好辦，通過改變顏色就行. 把P和U都設置成黑色然后,X加到P節點。 G節點當作新加入節點繼續迭代 setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { //處理紅父，黑叔的情況 if (x == rightOf(parentOf(x))) { // 這種情況 /** * G * P(RED) U(BLACK) * X */ //如果X是右邊節點 x = parentOf(x); // 進行左旋 rotateLeft(x); } //左旋后，是這種情況了 /** * G * P(RED) U(BLACK) * X */ // 到這，X只能是左節點了，而且P是紅色，U是黑色的情況 //把P和G改成黑色，以G為節點進行右旋 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { //父節點在右邊的 /** * G * U P(RED) */ //獲取U Entry<K, V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { //紅父紅叔的情況 /** * G * U(RED) P(RED) */ setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); //把G當作新插入的節點繼續進行迭代 x = parentOf(parentOf(x)); } else { //紅父黑叔，并且是右父的情況 /** * G * U(RED) P(RED) */ if (x == leftOf(parentOf(x))) { x = parentOf(x); //以P為節點進行右旋 rotateRight(x); } //右旋后 /** * G * U(BLACK) P(RED) * X */ setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); //以G為節點進行左旋 rotateLeft(parentOf(parentOf(x))); } } } //紅黑樹的根節點始終是黑色 root.color = BLACK; }
2， HASHMAP的死鏈問題
//對HashMap死鏈理解的注解 . 2017.02.17 by 何錦彬 JDK,1.7.51
void transfer(Entry[] newTable, boolean rehash) { //獲取新table的容量 int newCapacity = newTable.length; //迭代以前的數組 for (Entry<K,V> e : table) { //如果數組上有元素 while(null != e) { // 賦值next Entry<K,V> next = e.next; //獲取e在新的table里的位置 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); //把e指向當前的新數組里的第一個元素，這里會并發了，如果在這斷點等待下個線程過來，就會死循環，嘗試下 e.next = newTable[i]; //替代新數組的位置 newTable[i] = e; e = next; } } }
擴容前
[ 1 ] [ 2 ] [ 3 ] [ 空]
5 10
第一個線程擴容后，數組鏈表如下
[ 1 ] [ 10 ] [3] [] [] [] []
2
第二個線程又把從頭把2指向10，然后2和10形成了個死循環
HashMap在 JDK8后 把數組鏈表變成了數組+鏈表+紅黑樹. 鏈表為O(n)，而紅黑樹為O(logN)
for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //JDK8 的hashmap，鏈表到了8就需要變成顆紅黑樹了 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; }
調整紅黑樹的方法其實和treeMap的一樣了
如下：
//hashmap的紅黑樹平衡 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { x.red = true; //死循環加變量定義，總感覺JAVA很少這樣寫代碼 哈 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { //xp X父節點， XPP X的祖父節點， XPPL 祖父左節點 XXPR 祖父右節點 if ((xp = x.parent) == null) { x.red = false; return x; } // 如果父節點是黑色， 或者XP父節點是空，直接返回 else if (!xp.red || (xpp = xp.parent) == null) return root; // 下面的代碼就和上面的很treeMap像了， if (xp == (xppl = xpp.left)) { // 第一種情況, 賦值xppl //父節點是左節點的情況,下面這種 /** * G * P(RED) U */ if ((xppr = xpp.right) != null && xppr.red) { //如果紅叔的情況 // 這種情況 /** * G * P(RED) U(RED) * X */ //改變其顏色， xppr.red = false; xp.red = false; xpp.red = true; x = xpp; } else { // 黑叔的情況 // 這種情況 /** * G * P(RED) U(BLACK) */ if (x == xp.right) { //如果插入節點在右邊 這種 // 這種情況 /** * G * P(RED) U(BLACK) * X */ //需要進行左旋 root = rotateLeft(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } //左旋后情況都是這種了 /** * G * P(RED) U(BLACK) * X */ // 到這，X只能是左節點了，而且P是紅色，U是黑色的情況 if (xp != null) { //把P和G改成黑色，以G為節點進行右旋 xp.red = false; if (xpp != null) { xpp.red = true; root = rotateRight(root, xpp); } } } } else { //父節點在右邊的 /** * G * U P(RED) */ //獲取U if (xppl != null && xppl.red) { //紅父紅叔的情況 /** * G * U(RED) P(RED) */ xppl.red = false; xp.red = false; xpp.red = true; x = xpp; } else { if (x == xp.left) { //如果插入的X是右節點 /** * G * U(BLACK) P(RED) * X */ root = rotateRight(root, x = xp); xpp = (xp = x.parent) == null ? null : xp.parent; } //右旋后 /** * G * U(BLACK) P(RED) * X */ if (xp != null) { xp.red = false; if (xpp != null) { xpp.red = true; root = rotateLeft(root, xpp); } } } } }
文章列表
全站熱搜
留言列表
