java紅黑樹實現(xiàn)代碼 java 紅黑樹實現(xiàn)

請問java中HashMap是怎么實現(xiàn)的，還有treeMap的實現(xiàn)原理是紅黑樹，請解釋一下紅黑樹

參考資料的網(wǎng)頁上有比較的代碼,你可以仔細看下~~~

創(chuàng)新互聯(lián)公司專注于網(wǎng)站制作、做網(wǎng)站、網(wǎng)頁設(shè)計、網(wǎng)站制作、網(wǎng)站開發(fā)。公司秉持“客戶至上,用心服務(wù)”的宗旨,從客戶的利益和觀點出發(fā),讓客戶在網(wǎng)絡(luò)營銷中找到自己的駐足之地。尊重和關(guān)懷每一位客戶，用嚴謹?shù)膽B(tài)度對待客戶，用專業(yè)的服務(wù)創(chuàng)造價值，成為客戶值得信賴的朋友，為客戶解除后顧之憂。

java中HashMap,LinkedHashMap,TreeMap，HashTable的區(qū)別

java為數(shù)據(jù)結(jié)構(gòu)中的映射定義了一個接口java.util.Map;它有四個實現(xiàn)類,分別是HashMap Hashtable LinkedHashMap 和TreeMap

Map主要用于存儲健值對，根據(jù)鍵得到值，因此不允許鍵重復(fù)(重復(fù)了覆蓋了),但允許值重復(fù)。

Hashmap 是一個最常用的Map,它根據(jù)鍵的HashCode 值存儲數(shù)據(jù),根據(jù)鍵可以直接獲取它的值，具有很快的訪問速度，遍歷時，取得數(shù)據(jù)的順序是完全隨機的。HashMap最多只允許一條記錄的鍵為Null;允許多條記錄的值為 Null;HashMap不支持線程的同步，即任一時刻可以有多個線程同時寫HashMap;可能會導致數(shù)據(jù)的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。

Hashtable與 HashMap類似,它繼承自Dictionary類，不同的是:它不允許記錄的鍵或者值為空;它支持線程的同步，即任一時刻只有一個線程能寫Hashtable,因此也導致了 Hashtable在寫入時會比較慢。

LinkedHashMap保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的.也可以在構(gòu)造時用帶參數(shù)，按照應(yīng)用次數(shù)排序。在遍歷的時候會比HashMap慢，不過有種情況例外，當HashMap容量很大，實際數(shù)據(jù)較少時，遍歷起來可能會比LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數(shù)據(jù)有關(guān)，和容量無關(guān)，而HashMap的遍歷速度和他的容量有關(guān)。

TreeMap實現(xiàn)SortMap接口，能夠把它保存的記錄根據(jù)鍵排序,默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator 遍歷TreeMap時，得到的記錄是排過序的。

一般情況下，我們用的最多的是HashMap,HashMap里面存入的鍵值對在取出的時候是隨機的,它根據(jù)鍵的HashCode值存儲數(shù)據(jù),根據(jù)鍵可以直接獲取它的值，具有很快的訪問速度。在Map 中插入、刪除和定位元素，HashMap 是最好的選擇。

TreeMap取出來的是排序后的鍵值對。但如果您要按自然順序或自定義順序遍歷鍵，那么TreeMap會更好。

LinkedHashMap 是HashMap的一個子類，如果需要輸出的順序和輸入的相同,那么用LinkedHashMap可以實現(xiàn),它還可以按讀取順序來排列，像連接池中可以應(yīng)用。

紅黑樹詳解

首先，我們來了解一下二叉查找樹,二叉查找樹具備以下幾個特點：

1、左子樹上所有節(jié)點的值均小于或等于它的根節(jié)點的值；

2、右子樹上所有節(jié)點的值均大于或等于它的根節(jié)點的值；

3、左右子樹也分別為二叉排序樹。

下面我們以一棵典型的二叉查找樹來查找值為10的節(jié)點：

以上圖例正是典型的二分查找的思想，查找所需的最大次數(shù)等同于二叉查找樹的高度。在往樹中插入新節(jié)點的時候也要用類似的方法，通過一層一層地比較大小從而找到新節(jié)點適合插入的位置。但是即便如此，二叉查找樹依舊存在它的缺陷，并且此缺陷恰恰體現(xiàn)在插入新節(jié)點的時候。請看下面圖例展示：

這樣的瘸腿形態(tài)雖然也符合二叉查找樹的特性，但是查找的性能卻大打折扣，幾乎變成了線性數(shù)據(jù)結(jié)構(gòu)。為了解決二叉查找樹多次插入新節(jié)點而導致的不平衡問題，紅黑樹便應(yīng)運而生了。

紅黑樹是一種自平衡的二叉查找樹，除了符合二叉查找樹的特性外，還具有下列性質(zhì)：

1、根節(jié)點是黑色，節(jié)點是紅色或黑色；

2、每個葉子節(jié)點都是黑的空節(jié)點；（nil節(jié)點）

3、每個紅色節(jié)點的兩個子節(jié)點都是黑色；（也就是說從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點）

4、從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。

這些規(guī)則的限制，保證了紅黑樹的平衡，紅黑樹從根到葉子的最長路徑不會超過最短路徑的兩倍。當紅黑樹插入或者刪除節(jié)點的時候，紅黑樹的規(guī)則可能被打破，這時候就需要做出調(diào)整來維持它的平衡了。請看下面的例子（注意：新插入的節(jié)點必須是紅色，否則就沒有意義了）：

由于父節(jié)點22是也是紅色節(jié)點，因此打破了紅黑樹的規(guī)則（每個紅黑樹的兩個子節(jié)點都是黑色），所以必須進行調(diào)整，使之重新符合規(guī)則。那么我們需要作出怎樣的調(diào)整才能保證一棵紅黑樹始終是符合規(guī)則的標準紅黑樹呢？調(diào)整有兩種方法：“變色”和“旋轉(zhuǎn)”，其中，旋轉(zhuǎn)又分為兩種形式：“左旋轉(zhuǎn)”和“右旋轉(zhuǎn)”。

為了重新符合紅黑樹的規(guī)則，嘗試把紅色節(jié)點變成黑色，或者把黑色節(jié)點變成紅色。

下圖是摘自上面紅黑樹的一部分，節(jié)點25并非根節(jié)點。正如上面所說因為新節(jié)點21和節(jié)點22連續(xù)出現(xiàn)了紅色，不符合規(guī)則，所以把節(jié)點22從紅色變成黑色。

但這樣并不算完，節(jié)點22變成黑色后，憑空多出的黑色節(jié)點又打破了規(guī)則，發(fā)生連鎖反應(yīng)，需要繼續(xù)把節(jié)點25從黑色變?yōu)榧t色。

此時仍未結(jié)束，節(jié)點25變?yōu)榧t色后，又和節(jié)點27形成了兩個連續(xù)的紅色，規(guī)則又被打破，需要繼續(xù)把節(jié)點27從紅色變?yōu)楹谏?/p>

如此一路走下來，完成變色調(diào)整。

逆時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點，使得父節(jié)點被自己的右孩子取代，而自己成為左孩子。

順時針旋轉(zhuǎn)紅黑樹的兩個節(jié)點，使得父節(jié)點被自己的左孩子取代，而自己成為右孩子。

這幾種方法究竟怎么使用呢？紅黑樹的插入和刪除包含很多種情況，每種情況都有不同的處理方式，下面舉一個典型的例子，可以體會一下這個過程。

還以剛才插入節(jié)點21為例：

首先我們變色處理，把節(jié)點25及其下方的節(jié)點變色：

此時節(jié)點17和節(jié)點25是連續(xù)的兩個紅色節(jié)點，那么此時再把節(jié)點17變成黑色節(jié)點可以嗎？顯然是不可以的，這樣依然不符合規(guī)則，更不可以把根節(jié)點13變成紅色。

既然變色已經(jīng)無法解決問題，我們此時就要使用旋轉(zhuǎn)了，我們把節(jié)點13看作X，把節(jié)點17看作Y，進行左旋轉(zhuǎn)：

旋轉(zhuǎn)完成后，由于根節(jié)點必須是黑色，所以還需要進行變色：

至此并沒有結(jié)束，因為其中兩條路徑（17-8-6-NIL）的黑色節(jié)點數(shù)是4，其他路徑的黑色節(jié)點數(shù)是3，依舊不符合規(guī)則。這時我們需要把節(jié)點13看成X，節(jié)點8看成Y，做右旋轉(zhuǎn)：

然后再進行變色：

經(jīng)過上面一系列的調(diào)整，我們的紅黑樹終于變得重新符合規(guī)則，整個過程有點復(fù)雜，經(jīng)歷了：變色--左旋轉(zhuǎn)--變色--右旋轉(zhuǎn)--變色這樣的一系列步驟。

經(jīng)過上面細致的步驟演示，想必大家對二叉查找樹和紅黑樹有所了解了吧，對紅黑樹結(jié)構(gòu)插入新節(jié)點所觸發(fā)的一系列的變化流程也有了大概印象。實際中紅黑樹的應(yīng)用是很多的，比如JDK（Java開發(fā)工具包）的集合類TreeMap和TreeSet底層就是紅黑樹實現(xiàn)的，在Java8中，HashMap也用到了紅黑樹。其實關(guān)于紅黑樹自平衡的調(diào)整，插入和刪除節(jié)點時涉及到的情形一一展開講解還是很多很多的，但是萬變不離其中，紅黑樹自平衡調(diào)整的主體思想都是上面所敘述的，大家有興趣可以再進行深入的探究。

有關(guān)紅黑樹的java程序，編譯成功但運行不出結(jié)果。

java8不是用紅黑樹來管理hashmap，而是在hash值相同的情況下（且重復(fù)數(shù)量大于8），用紅黑樹來管理數(shù)據(jù)。 紅黑樹相當于排序數(shù)據(jù)?？梢宰詣拥氖褂枚址ㄟM行定位。性能較高。

一般情況下，hash值做的比較好的話基本上用不到紅黑樹。

當前文章：java紅黑樹實現(xiàn)代碼 java 紅黑樹實現(xiàn)
分享路徑：http://muchs.cn/article24/hgcpce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、企業(yè)建站、網(wǎng)站策劃、微信公眾號、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)