java8不是用紅黑樹(shù)來(lái)管理hashmap,而是在hash值相同的情況下(且重復(fù)數(shù)量大于8),用紅黑樹(shù)來(lái)管理數(shù)據(jù)。 紅黑樹(shù)相當(dāng)于排序數(shù)據(jù)。可以自動(dòng)的使用二分法進(jìn)行定位。性能較高。

惠州網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,惠州網(wǎng)站設(shè)計(jì)制作,有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為惠州成百上千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站制作要多少錢(qián),請(qǐng)找那個(gè)售后服務(wù)好的惠州做網(wǎng)站的公司定做!
一般情況下,hash值做的比較好的話(huà)基本上用不到紅黑樹(shù)。
跳表:是為一個(gè)有序的鏈表建立多級(jí)索引的數(shù)據(jù)結(jié)構(gòu)叫做跳表。redis中zset數(shù)據(jù)量大時(shí)底層數(shù)據(jù)結(jié)構(gòu)使用跳表。
redis中定時(shí)器使用的是無(wú)序的雙向鏈表。時(shí)間復(fù)雜度為O(N),redis作者在定時(shí)器備注了可以適當(dāng)優(yōu)化的措施:
1 盡可能讓數(shù)據(jù)有序,2 可以使用跳表完成
回歸正題,跳表:
其他地方借圖一張如下:
跳表是基于有序鏈表所實(shí)現(xiàn)的,為了實(shí)現(xiàn)快速的查找,在做節(jié)點(diǎn)比較的時(shí)候跳過(guò)一些節(jié)點(diǎn)以達(dá)到快速查找的目的,是一種空間換時(shí)間的思想。
如上圖,此跳表總共三層(level = 3),redis中zset在數(shù)據(jù)量比較大時(shí),采用的即是跳表實(shí)現(xiàn) 其最大層數(shù)是32,再插入節(jié)點(diǎn)的時(shí)候隨機(jī)生成層數(shù),最大不超過(guò)32;
如上圖為例,頭節(jié)點(diǎn)不保存數(shù)據(jù),按照上圖分析插入操作:
插入之前要先從上層到下層臨時(shí)保存每一層的當(dāng)前節(jié)點(diǎn),然后隨即生成新的newlevel,如果newlevel大于level,則對(duì)于(level-newlevel)層進(jìn)行初始化頭結(jié)點(diǎn) 。
插入14前,沒(méi)有數(shù)據(jù)只有頭結(jié)點(diǎn) ,當(dāng)前l(fā)evel默認(rèn)是1,用temp[0]臨時(shí)保存節(jié)點(diǎn),
while循環(huán)是找到下一個(gè)節(jié)點(diǎn),比如插入34時(shí),while之后level1 層 x節(jié)點(diǎn)就是23;插入50時(shí),while循環(huán)之后 level1層temp[0] = 43,level2層 temp[1]=34,level3層 temp[2]=14;
保存完臨時(shí)節(jié)點(diǎn)后,隨機(jī)生成新的層數(shù),
14插入時(shí)隨機(jī)層數(shù)是3,大于之前默認(rèn)的level =1;對(duì)于level2 和level3就要進(jìn)行頭結(jié)點(diǎn)賦值,temp[1]=header;temp[2]=header;
然后進(jìn)行新節(jié)點(diǎn)的插入,之前遍歷都是從高層向底層擴(kuò)展,插入操作要從底層向高層擴(kuò)展。
插入操作之后,形成了temp[0]-next = 節(jié)點(diǎn)14,temp[1]-next = 節(jié)點(diǎn)14,temp[2]-next = 節(jié)點(diǎn)14即header[0]-next = 節(jié)點(diǎn)14,header[1]-next = 節(jié)點(diǎn)14,header[2]-next = 節(jié)點(diǎn)14;
14節(jié)點(diǎn)插入之后,鏈表長(zhǎng)度+1(單指最底層的鏈表);
接著插入節(jié)點(diǎn)23,臨時(shí)變量temp值為temp[0]= 節(jié)點(diǎn)14,temp[1] = 節(jié)點(diǎn)14,temp[2] = 節(jié)點(diǎn)14; 隨機(jī)新的newlevel =1,說(shuō)明23 只出現(xiàn)在level1層,進(jìn)行插入后temp[0]-next = 節(jié)點(diǎn)23,其他兩個(gè)節(jié)點(diǎn)不變。
插入節(jié)點(diǎn)34后,各層鏈表為
header[2]-14
header[1]-14-34
header[0]-14-23-34
以上就是插入的大致邏輯分析。
刪除操作類(lèi)似,先從上層開(kāi)始向后遍歷然后向下,刪除時(shí)從下層開(kāi)始向上操作。
跳表實(shí)現(xiàn)定時(shí)器demo源碼地址: 跳表實(shí)現(xiàn)定時(shí)器demo
紅黑樹(shù):一顆節(jié)點(diǎn)非紅即黑的平衡二叉樹(shù)。epoll底層使用紅黑樹(shù)。
紅黑樹(shù)插入 查詢(xún),刪除等基本操作時(shí)間復(fù)雜度為O(lgn),跳表搜索插入刪除操作時(shí)間復(fù)雜度接近O(lgn),最壞情況下變成O(n)。
做范圍查找的時(shí)候 ,平衡樹(shù)比跳表操作要復(fù)雜,平衡樹(shù)上,找到指定范圍的小值之后,還需要以中序遍歷的順序繼續(xù)尋找其他不超過(guò)大值的節(jié)點(diǎn),相對(duì)而言,跳表的范圍查詢(xún)就比較簡(jiǎn)單,只要找到小值,在第一層鏈表進(jìn)行若干層遍歷就行。
從算法實(shí)現(xiàn)難度講,跳表比紅黑樹(shù)要簡(jiǎn)單的多。
紅黑樹(shù)也是實(shí)現(xiàn)定時(shí)器的數(shù)據(jù)結(jié)構(gòu)之一,具體實(shí)現(xiàn)不再詳敘。
最近研究JDK源碼的時(shí)候,發(fā)現(xiàn)TreeMap和TreeSet底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹(shù),當(dāng)然,TreeSet其實(shí)本質(zhì)上就是Value為一個(gè)固定值的TreeMap。在JDK1.8以后,HashMap也用到了紅黑樹(shù)。
那紅黑樹(shù)到底是怎樣的一種數(shù)據(jù)結(jié)構(gòu)呢?相信大家都不是非常了解,我也去翻了好多的相關(guān)文章,發(fā)現(xiàn)一篇很有趣的漫畫(huà),可以幫助大家很快了解紅黑樹(shù)大概是怎樣的一種數(shù)據(jù)結(jié)構(gòu),有哪些特點(diǎn)。 只是大概的介紹一下紅黑樹(shù),詳細(xì)的實(shí)現(xiàn)大家還是請(qǐng)參考相關(guān)的算法書(shū)籍。
以下內(nèi)容轉(zhuǎn)自: 漫畫(huà)算法:什么是紅黑樹(shù)?
1.左子樹(shù)上所有結(jié)點(diǎn)的值均小于或等于它的根結(jié)點(diǎn)的值。
2.右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值。
3.左、右子樹(shù)也分別為二叉排序樹(shù)。
下圖中這棵樹(shù),就是一顆典型的二叉查找樹(shù):
1.查看根節(jié)點(diǎn)9:
3.由于10 13,因此查看左孩子11:
假設(shè)初始的二叉查找樹(shù)只有三個(gè)節(jié)點(diǎn),根節(jié)點(diǎn)值為9,左孩子值為8,右孩子值為12:
2.根節(jié)點(diǎn)是黑色。
3.每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)(NIL節(jié)點(diǎn))。
4 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
5.從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
下圖中這棵樹(shù),就是一顆典型的紅黑樹(shù):
什么情況下會(huì)破壞紅黑樹(shù)的規(guī)則,什么情況下不會(huì)破壞規(guī)則呢?我們舉兩個(gè)簡(jiǎn)單的栗子:
1.向原紅黑樹(shù)插入值為14的新節(jié)點(diǎn):
為了重新符合紅黑樹(shù)的規(guī)則,嘗試把紅色節(jié)點(diǎn)變?yōu)楹谏蛘甙押谏?jié)點(diǎn)變?yōu)榧t色。
下圖所表示的是紅黑樹(shù)的一部分,需要注意節(jié)點(diǎn)25并非根節(jié)點(diǎn)。因?yàn)楣?jié)點(diǎn)21和節(jié)點(diǎn)22連續(xù)出現(xiàn)了紅色,不符合規(guī)則4,所以把節(jié)點(diǎn)22從紅色變成黑色:
但這樣并不算完,因?yàn)閼{空多出的黑色節(jié)點(diǎn)打破了規(guī)則5,所以發(fā)生連鎖反應(yīng),需要繼續(xù)把節(jié)點(diǎn)25從黑色變成紅色:
逆時(shí)針旋轉(zhuǎn)紅黑樹(shù)的兩個(gè)節(jié)點(diǎn),使得父節(jié)點(diǎn)被自己的右孩子取代,而自己成為自己的左孩子。說(shuō)起來(lái)很怪異,大家看下圖:
圖中,身為右孩子的Y取代了X的位置,而X變成了自己的左孩子。此為左旋轉(zhuǎn)。
順時(shí)針旋轉(zhuǎn)紅黑樹(shù)的兩個(gè)節(jié)點(diǎn),使得父節(jié)點(diǎn)被自己的左孩子取代,而自己成為自己的右孩子。大家看下圖:
圖中,身為左孩子的Y取代了X的位置,而X變成了自己的右孩子。此為右旋轉(zhuǎn)。
首先,我們需要做的是變色,把節(jié)點(diǎn)25及其下方的節(jié)點(diǎn)變色:
這時(shí)候我們需要把節(jié)點(diǎn)13看做X,節(jié)點(diǎn)8看做Y,像剛才的示意圖那樣進(jìn)行右旋轉(zhuǎn):
如果想要詳細(xì)了解紅黑樹(shù)算法,可以參考這篇文章: Java數(shù)據(jù)結(jié)構(gòu)和算法(十一)——紅黑樹(shù)
樹(shù) 是一種 抽象數(shù)據(jù)類(lèi)型 ,或是實(shí)作這種抽象數(shù)據(jù)類(lèi)型的數(shù)據(jù)結(jié)構(gòu),用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的 數(shù)據(jù)集合 。
紅黑樹(shù) 是一種自平衡二叉查找樹(shù),典型的用途是實(shí)現(xiàn) 關(guān)聯(lián)數(shù)組 ,它是復(fù)雜的,但它的操作有著良好的最壞情況運(yùn)行時(shí)間,并且在實(shí)踐中是高效的 O(log n ) 時(shí)間內(nèi)做查找,插入和刪除,這里的 n 是樹(shù)中元素的數(shù)目。
一個(gè)由n個(gè)節(jié)點(diǎn)隨機(jī)構(gòu)成的二叉查找樹(shù)的高度為(log n ).證明如下:
而時(shí)間復(fù)雜度是以某個(gè)基礎(chǔ)數(shù)據(jù)操作的重復(fù)次數(shù)作為量度。紅黑樹(shù)的是二叉搜索樹(shù),左子樹(shù)上所有節(jié)點(diǎn)的值均小于他的根節(jié)點(diǎn)的值,右子樹(shù)上所有節(jié)點(diǎn)均大于根節(jié)點(diǎn)的值,左右子節(jié)樹(shù)相對(duì)根節(jié)點(diǎn)按大小分布。如果把每次節(jié)點(diǎn)值的比較看成基礎(chǔ)數(shù)據(jù)操作,那么最差的查找情況是一直查找到高度最大的根節(jié)點(diǎn),那么查找的時(shí)間復(fù)雜度即與高度成正比,可表示成 O(log n ) 。
簡(jiǎn)單了解了紅黑樹(shù)的字面定義,下面動(dòng)手感受下紅黑樹(shù)的相關(guān)操作。當(dāng)你插入或者刪除一個(gè)節(jié)點(diǎn)時(shí),可能會(huì)破壞紅黑樹(shù)的性質(zhì),所以需要對(duì)樹(shù)節(jié)點(diǎn)進(jìn)行重新著色或者旋轉(zhuǎn),來(lái)保持紅黑樹(shù)的結(jié)構(gòu)。首先看下二叉樹(shù)的旋轉(zhuǎn)。
假設(shè)pivot節(jié)點(diǎn)不為空,其右子樹(shù)不為空,那么左旋即是:使pivot的右孩子Y為子樹(shù)的根,pivot節(jié)點(diǎn)為子樹(shù)根節(jié)點(diǎn)的左孩子,pivot左孩子、Y節(jié)點(diǎn)的右孩子不改變,Y節(jié)點(diǎn)左孩子變?yōu)閜ivot節(jié)點(diǎn)右孩子。
假設(shè)pivot節(jié)點(diǎn)不為空,其左子樹(shù)不為空,那么右旋:使pivot的左孩子Y為子樹(shù)的根,pivot節(jié)點(diǎn)為子樹(shù)根節(jié)點(diǎn)的右孩子,pivot的右孩子、Y節(jié)點(diǎn)的左孩子不變,Y節(jié)點(diǎn)的右孩子變?yōu)閜ivot節(jié)點(diǎn)的左孩子。
實(shí)戰(zhàn)演練之增加、刪除節(jié)點(diǎn)時(shí),如何保證紅黑樹(shù)的性質(zhì)不被破壞。
往一個(gè)空的紅黑樹(shù)中,依次插入數(shù)據(jù):12 1 9 2 0 11 7 19 4
節(jié)點(diǎn)為根節(jié)點(diǎn),所以為黑色,兩個(gè)null節(jié)點(diǎn)為黑色節(jié)點(diǎn)。
按照二叉搜索樹(shù)的邏輯,9小于12、大于1,應(yīng)該是1節(jié)點(diǎn)的右孩子。但,新增的兩個(gè)NIL節(jié)點(diǎn)已經(jīng)使得12,1,9,NI這條路徑的黑色節(jié)點(diǎn)至少為兩個(gè),而12,NIL這條路徑的黑色節(jié)點(diǎn)只有兩個(gè)。所以要對(duì)1節(jié)點(diǎn)進(jìn)行左旋,9節(jié)點(diǎn)變?yōu)?2節(jié)點(diǎn)的左孩子,發(fā)現(xiàn)問(wèn)題還是存在。繼續(xù),對(duì)12節(jié)點(diǎn)進(jìn)行右旋,9節(jié)點(diǎn)為根節(jié)點(diǎn),1、12分別為9節(jié)點(diǎn)的左右孩子。嘗試著色,9節(jié)點(diǎn)必須為黑色,而1,12節(jié)點(diǎn)可以為紅色,也可以為黑色。
0節(jié)點(diǎn)直接作為1節(jié)點(diǎn)的左孩子,保持跟2節(jié)點(diǎn)相同的顏色即可。左右子樹(shù)依舊保持平衡。
從二叉查找樹(shù)的性質(zhì)看,7節(jié)點(diǎn)作為2節(jié)點(diǎn)的右孩子即可。這時(shí)來(lái)分析著色問(wèn)題,我們先看最短路徑的黑色分布,9,12,NIL這條路徑,有三個(gè)黑色節(jié)點(diǎn),以此為參考,嘗試改變9節(jié)點(diǎn)左子樹(shù)的著色。目前最長(zhǎng)的路徑是9,1,2,7,NIL這條路徑。保持三個(gè)黑色節(jié)點(diǎn)的話(huà),9跟NIL已經(jīng)為黑色節(jié)點(diǎn),而紅色節(jié)點(diǎn)又不能挨著,所以只能是1為紅色節(jié)點(diǎn),2為黑色節(jié)點(diǎn),7為紅色節(jié)點(diǎn)。那么9,1,0,NIIL這條路徑,0就要為黑色節(jié)點(diǎn)。調(diào)整完畢。
19節(jié)點(diǎn)作為12節(jié)點(diǎn)的右孩子,與左孩子保持一樣的紅色即可。
4節(jié)點(diǎn)應(yīng)該作為7節(jié)點(diǎn)的左子樹(shù),無(wú)論著什么顏色,以1節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù),都要破壞紅黑性質(zhì)。所以應(yīng)該進(jìn)行旋轉(zhuǎn)。先以7為根節(jié)點(diǎn)進(jìn)行一次右旋,再以2為根節(jié)點(diǎn)進(jìn)行一次左旋。嘗試著色即可。
類(lèi)似插入節(jié)點(diǎn)的分析、總結(jié),刪除節(jié)點(diǎn)也可以針對(duì)每種場(chǎng)景找到固定的著色方法,就像玩一個(gè)游戲,有自己的推理跟玩法。我先做個(gè)PPT,這塊稍后補(bǔ)充。
所有的插入、刪除都是有限個(gè)情況,基于插入、刪除的情況分析,即可編寫(xiě)算法生成紅黑樹(shù),使其在固定的業(yè)務(wù)場(chǎng)景中發(fā)揮紅黑樹(shù)穩(wěn)定操作效率的特色了。
在 計(jì)算機(jī)科學(xué) 中, AVL樹(shù) 是最先發(fā)明的 自平衡二叉查找樹(shù) 。在AVL樹(shù)中任何節(jié)點(diǎn)的兩個(gè) 子樹(shù) 的高度最大差別為一,所以它也被稱(chēng)為 高度平衡樹(shù) 。查找、插入和刪除在平均和最壞情況下都是 O (log n )。增加和刪除可能需要通過(guò)一次或多次 樹(shù)旋轉(zhuǎn) 來(lái)重新平衡這個(gè)樹(shù)。
節(jié)點(diǎn)的 平衡因子 是它的左子樹(shù)的高度減去它的右子樹(shù)的高度(有時(shí)相反)。帶有平衡因子1、0或 -1的節(jié)點(diǎn)被認(rèn)為是平衡的。帶有平衡因子 -2或2的節(jié)點(diǎn)被認(rèn)為是不平衡的,并需要重新平衡這個(gè)樹(shù)。平衡因子可以直接存儲(chǔ)在每個(gè)節(jié)點(diǎn)中,或從可能存儲(chǔ)在節(jié)點(diǎn)中的子樹(shù)高度計(jì)算出來(lái)。
不提問(wèn)題的碼農(nóng)不是好程序員。自己寫(xiě)完了紅黑樹(shù)的簡(jiǎn)單剖析,感覺(jué)還是只懂皮毛,沒(méi)有從觸碰到算法的核心內(nèi)容。所以,不妨留幾個(gè)小問(wèn)題,擔(dān)心自己腦子生銹或者沒(méi)事想玩手機(jī)的時(shí)候,再提筆研究下紅黑樹(shù)。
教你初步了解紅黑樹(shù)
算法的時(shí)間復(fù)雜度和空間復(fù)雜度-總結(jié)
紅黑樹(shù)從頭至尾插入和刪除
AVL樹(shù)
紅黑樹(shù)C源碼實(shí)現(xiàn)與剖析
Echo
8 Nov,2016
參考資料的網(wǎng)頁(yè)上有比較的代碼,你可以仔細(xì)看下~~~
java中HashMap,LinkedHashMap,TreeMap,HashTable的區(qū)別
java為數(shù)據(jù)結(jié)構(gòu)中的映射定義了一個(gè)接口java.util.Map;它有四個(gè)實(shí)現(xiàn)類(lèi),分別是HashMap Hashtable LinkedHashMap 和TreeMap
Map主要用于存儲(chǔ)健值對(duì),根據(jù)鍵得到值,因此不允許鍵重復(fù)(重復(fù)了覆蓋了),但允許值重復(fù)。
Hashmap 是一個(gè)最常用的Map,它根據(jù)鍵的HashCode 值存儲(chǔ)數(shù)據(jù),根據(jù)鍵可以直接獲取它的值,具有很快的訪問(wèn)速度,遍歷時(shí),取得數(shù)據(jù)的順序是完全隨機(jī)的。HashMap最多只允許一條記錄的鍵為Null;允許多條記錄的值為 Null;HashMap不支持線(xiàn)程的同步,即任一時(shí)刻可以有多個(gè)線(xiàn)程同時(shí)寫(xiě)HashMap;可能會(huì)導(dǎo)致數(shù)據(jù)的不一致。如果需要同步,可以用 Collections的synchronizedMap方法使HashMap具有同步的能力,或者使用ConcurrentHashMap。
Hashtable與 HashMap類(lèi)似,它繼承自Dictionary類(lèi),不同的是:它不允許記錄的鍵或者值為空;它支持線(xiàn)程的同步,即任一時(shí)刻只有一個(gè)線(xiàn)程能寫(xiě)Hashtable,因此也導(dǎo)致了 Hashtable在寫(xiě)入時(shí)會(huì)比較慢。
LinkedHashMap保存了記錄的插入順序,在用Iterator遍歷LinkedHashMap時(shí),先得到的記錄肯定是先插入的.也可以在構(gòu)造時(shí)用帶參數(shù),按照應(yīng)用次數(shù)排序。在遍歷的時(shí)候會(huì)比HashMap慢,不過(guò)有種情況例外,當(dāng)HashMap容量很大,實(shí)際數(shù)據(jù)較少時(shí),遍歷起來(lái)可能會(huì)比LinkedHashMap慢,因?yàn)長(zhǎng)inkedHashMap的遍歷速度只和實(shí)際數(shù)據(jù)有關(guān),和容量無(wú)關(guān),而HashMap的遍歷速度和他的容量有關(guān)。
TreeMap實(shí)現(xiàn)SortMap接口,能夠把它保存的記錄根據(jù)鍵排序,默認(rèn)是按鍵值的升序排序,也可以指定排序的比較器,當(dāng)用Iterator 遍歷TreeMap時(shí),得到的記錄是排過(guò)序的。
一般情況下,我們用的最多的是HashMap,HashMap里面存入的鍵值對(duì)在取出的時(shí)候是隨機(jī)的,它根據(jù)鍵的HashCode值存儲(chǔ)數(shù)據(jù),根據(jù)鍵可以直接獲取它的值,具有很快的訪問(wèn)速度。在Map 中插入、刪除和定位元素,HashMap 是最好的選擇。
TreeMap取出來(lái)的是排序后的鍵值對(duì)。但如果您要按自然順序或自定義順序遍歷鍵,那么TreeMap會(huì)更好。
LinkedHashMap 是HashMap的一個(gè)子類(lèi),如果需要輸出的順序和輸入的相同,那么用LinkedHashMap可以實(shí)現(xiàn),它還可以按讀取順序來(lái)排列,像連接池中可以應(yīng)用。
網(wǎng)站題目:紅黑樹(shù)java代碼源碼 紅黑樹(shù)c語(yǔ)言實(shí)現(xiàn)
當(dāng)前地址:http://www.chinadenli.net/article48/dooijep.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供云服務(wù)器、搜索引擎優(yōu)化、營(yíng)銷(xiāo)型網(wǎng)站建設(shè)、Google、網(wǎng)站排名、靜態(tài)網(wǎng)站
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話(huà):028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)