1、concurrenthashmap的紅黑樹實現(xiàn)分析知止而后有定，定而后能靜，靜而后能安，安而后能慮，慮而后能得紅黑樹紅黑樹是一種特殊的二叉樹，主要用它存儲有序的數(shù)據(jù)，提供高效的數(shù)據(jù)檢索，時間復雜度為O(lgn)，每個節(jié)點都有一個標識位表示顏色，紅色或黑色，有如下5種特性：每個節(jié)點要么紅色，要么是黑色；根節(jié)點一定是黑色的；每個空葉子節(jié)點必須是黑色的；如果一個節(jié)點是紅色的，那么它的子節(jié)點必須是黑色的；從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑包含相同個數(shù)的黑色節(jié)點；結(jié)構(gòu)示意圖只要滿足以上5個特性的二叉樹都是紅黑樹，當有新的節(jié)點加入時，有可能會破壞其中一些特性，需要通過左旋或右旋操作調(diào)整樹結(jié)構(gòu)，重新著色

2、，使之重新滿足所有特性。ConcurrentHashMap紅黑樹實現(xiàn)談談ConcurrentHashMap1.7和1.8的不同實現(xiàn)一文中已經(jīng)提到，在1.8的實現(xiàn)中，當一個鏈表中的元素達到8個時，會調(diào)用treeifyBin()方法把鏈表結(jié)構(gòu)轉(zhuǎn)化成紅黑樹結(jié)構(gòu)，實現(xiàn)如下：/*Replacesalllinkednodesinbinatgivenindexunlesstableis*toosmall,inwhichcaseresizesinstead.*/privatefinalvoidtreeifyBin(Nodetab,intindex)Nodeb;intn,sc;if(tab != null) i

3、f (n = tab.length)tryPresize(nelse if (b = tabAt(tab, index) != null&& b.hash >= 0) synchronized (b)if(tabAt(tab,index)=b)TreeNodehd=null,tl=null;for(Nodee=b;e!=null;e=e.next)TreeNodep=newTreeNode(e.hash,e.key,e.val,null,null);if(p.prev=tl)=null)hd=p;elsetl.next=p;tl=p;setTabAt(tab,index,

4、newTreeBin(hd);從上述實現(xiàn)可以看出：并非一開始就創(chuàng)建紅黑樹結(jié)構(gòu)，如果當前Node數(shù)組長度小于閾值MIN_TREEIFY_CAPACITY默認為64，先通過擴大數(shù)組容量為原來的兩倍以緩解單個鏈表元素過大的性能問題。紅黑樹構(gòu)造過程下面對紅黑樹的構(gòu)造過程進行分析：1、通過遍歷Node鏈表，生成對應的TreeNode鏈表，其中TreeNode在實現(xiàn)上繼承了Node類；classTreeNodeextendsNodeTreeNodeparent;/red-blacktreelinksTreeNodeleft;TreeNoderight;TreeNodeprev;/neededtounlin

5、knextupondeletionbooleanred;假設TreeNode鏈表如下，其中節(jié)點中的數(shù)值代表hash值：2、根據(jù)TreeNode鏈表初始化TreeBin類對象，TreeBin在實現(xiàn)上同樣繼承了Node類，所以初始化完成的TreeBin類對象可以保持在Node數(shù)組中；classTreeBinextendsNodeTreeNoderoot;volatileTreeNodefirst;volatileThreadwaiter;volatileintlockState;/valuesforlockState/setwhileholdingwritelockstaticfinalintWR

6、ITER=1;/setwhenwaitingforwritelockstaticfinalintWAITER=2;/incrementvalueforsettingreadlockstaticfinalintREADER=4;3、遍歷TreeNode鏈表生成紅黑樹，一開始二叉樹的根節(jié)點root為空，則設置鏈表中的第一個節(jié)點80為root，并設置其red屬性為false,因為在紅黑樹的特性1中，明確規(guī)定根節(jié)點必須是黑色的；for(TreeNodex=b,next;x!=null;x=next)next=(TreeNode)x.next;x.left=x.right=null;if(r=null)

7、x.parent=null;x.red=false;r=x;.二叉樹結(jié)構(gòu)：4、加入節(jié)點60，如果root不為空，則通過比較節(jié)點hash值的大小將新節(jié)點插入到指定位置，實現(xiàn)如下：Kk=x.key;inth=x.hash;Classkc=null;for(TreeNodep=r;)intdir,ph;Kpk=p.key;if(ph=p.hash)>h)dir=-1;elseif(phdir=1;elseif(kc=null&&(kc=comparableClassFor(k)=null)|(dir=compareComparables(kc,k,pk)=0)dir=tieBr

8、eakOrder(k,pk);TreeNodexp=p;if(p=(dirx.parent=xp;if(dirxp.left=x;elsexp.right=x;r=balanceInsertion(r,x);break;其中x代表即將插入到紅黑樹的節(jié)點，p指向紅黑樹中當前遍歷到的節(jié)點，從根節(jié)點開始遞歸遍歷，x的插入過程如下：1)、如果x的hash值小于p的hash值，則判斷p的左節(jié)點是否為空，如果不為空，則把p指向其左節(jié)點，并繼續(xù)和p進行比較，如果p的左節(jié)點為空，則把x指向的節(jié)點插入到該位置；2)、如果x的hash值大于p的hash值，則判斷p的右節(jié)點是否為空，如果不為空，則把p指向其右節(jié)點，

9、并繼續(xù)和p進行比較，如果p的右節(jié)點為空，則把x指向的節(jié)點插入到該位置；3)、如果x的hash值和p的hash值相等，怎么辦？解決：首先判斷節(jié)點中的key對象的類是否實現(xiàn)了Comparable接口，如果實現(xiàn)Comparable接口，則調(diào)用compareTo方法比較兩者key的大小，但是如果key對象沒有實現(xiàn)Comparable接口，或則compareTo方法返回了0，則繼續(xù)調(diào)用tieBreakOrder方法計算dir值，tieBreakOrder方法實現(xiàn)如下：staticinttieBreakOrder(Objecta,Objectb)intd;if(a=null|b=null|(d=a.get

10、Class().getName().compareTo(b.getClass().getName()=0)d=(System.identityHashCode(a)-1:1);returnd;最終比較key對象的默認hashCode()方法的返回值，因為System.identityHashCode(a)調(diào)用的是對象a默認的hashCode()；插入節(jié)點60之后的二叉樹：5、當有新節(jié)點加入時，可能會破壞紅黑樹的特性，需要執(zhí)行balanceInsertion()方法調(diào)整二叉樹，使之重新滿足特性，方法中的變量xp指向x的父節(jié)點，xpp指向xp父節(jié)點，xppl和xppr分另U指向xpp的左右子節(jié)點，

11、balanceInsertion()方法首先會把新加入的節(jié)點設置成紅色。、加入節(jié)點60之后，此時xp指向節(jié)點80，其父節(jié)點為空，直接返回。if(xp=x.parent)=null)x.red=false;returnx;elseif(!xp.red|(xpp=xp.parent)=null)returnroot;調(diào)整之后的二叉樹：、加入節(jié)點50,二叉樹如下：繼續(xù)執(zhí)行balanceInsertion()方法調(diào)整二叉樹，此時節(jié)點50的父節(jié)點60是左兒子，走如下邏輯：if(xp=(xppl=xpp.left)if(xppr=xpp.right)!=nullx = xpp; else root =xp

12、p = (xp = x.parent) =if (xp != null)if (xpp != null)root =&&xppr.red)xppr.red=false;xp.red=false;xpp.red=true;if(x=xp.right)rotateLeft(root,x=xp);null?null:xp.parent;xpp.red = true;xp.red=false;rotateRight(root, xpp);根據(jù)上述邏輯，把節(jié)點60設置成黑色，把節(jié)點80設置成紅色，并對節(jié)點80執(zhí)行右旋操作，右旋實現(xiàn)如下：staticTreeNoderotateRight(

13、TreeNoderoot,TreeNodep)TreeNodel,pp,lr;if(p!=null&&(l=p.left)!=null)if(lr=p.left=l.right)!=null)lr.parent=p;if(pp=l.parent=p.parent)=null)(root=l).red=false;elseif(pp.right=p)pp.right=l;elsepp.left=l;l.right=p;p.parent=l;returnroot;右旋之后的紅黑樹如下：、加入節(jié)點70,二叉樹如下：繼續(xù)執(zhí)行balanceInsertion()方法調(diào)整二叉樹，此時父節(jié)點80是個右兒子，節(jié)點70是左兒子，且叔節(jié)點50不為空，且是紅色的，則執(zhí)行如下邏輯：if(xppl!=null&&xppl.red)xppl.red=false;xp.red=false;xpp.red=true;x=xpp;此時二叉樹如下：此時x指向xpp，即節(jié)點60，繼續(xù)循環(huán)處理x,設