java紅黑樹實現代碼 java 紅黑樹實現

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

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

創新互聯公司專注于網站制作、做網站、網頁設計、網站制作、網站開發。公司秉持“客戶至上,用心服務”的宗旨,從客戶的利益和觀點出發,讓客戶在網絡營銷中找到自己的駐足之地。尊重和關懷每一位客戶，用嚴謹的態度對待客戶，用專業的服務創造價值，成為客戶值得信賴的朋友，為客戶解除后顧之憂。

java中HashMap,LinkedHashMap,TreeMap，HashTable的區別

java為數據結構中的映射定義了一個接口java.util.Map;它有四個實現類,分別是HashMap Hashtable LinkedHashMap 和TreeMap

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

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

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

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

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

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

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

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

紅黑樹詳解

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

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

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

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

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

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

這樣的瘸腿形態雖然也符合二叉查找樹的特性，但是查找的性能卻大打折扣，幾乎變成了線性數據結構。為了解決二叉查找樹多次插入新節點而導致的不平衡問題，紅黑樹便應運而生了。

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

1、根節點是黑色，節點是紅色或黑色；

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

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

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

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

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

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

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

但這樣并不算完，節點22變成黑色后，憑空多出的黑色節點又打破了規則，發生連鎖反應，需要繼續把節點25從黑色變為紅色。

此時仍未結束，節點25變為紅色后，又和節點27形成了兩個連續的紅色，規則又被打破，需要繼續把節點27從紅色變為黑色。

如此一路走下來，完成變色調整。

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

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

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

還以剛才插入節點21為例：

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

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

既然變色已經無法解決問題，我們此時就要使用旋轉了，我們把節點13看作X，把節點17看作Y，進行左旋轉：

旋轉完成后，由于根節點必須是黑色，所以還需要進行變色：

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

然后再進行變色：

經過上面一系列的調整，我們的紅黑樹終于變得重新符合規則，整個過程有點復雜，經歷了：變色--左旋轉--變色--右旋轉--變色這樣的一系列步驟。

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

有關紅黑樹的java程序，編譯成功但運行不出結果。

java8不是用紅黑樹來管理hashmap，而是在hash值相同的情況下（且重復數量大于8），用紅黑樹來管理數據。 紅黑樹相當于排序數據。可以自動的使用二分法進行定位。性能較高。

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

當前文章：java紅黑樹實現代碼 java 紅黑樹實現
分享路徑：http://m.kartarina.com/article24/hgcpce.html

成都網站建設公司_創新互聯，為您提供靜態網站、外貿網站建設、企業建站、網站策劃、微信公眾號、自適應網站

廣告

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