這篇文章主要介紹“Java TreeMap源碼是什么”，在日常操作中，相信很多人在Java TreeMap源碼是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java TreeMap源碼是什么”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

創(chuàng)新互聯(lián)是一家專業(yè)提供叢臺企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、H5建站、小程序制作等業(yè)務(wù)。10年已為叢臺眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進(jìn)行中。

簽名（signature）

public class TreeMap<K,V>
       extends AbstractMap<K,V>
       implements NavigableMap<K,V>, Cloneable, java.io.Serializable

可以看到，相比HashMap來說，TreeMap多繼承了一個接口NavigableMap，也就是這個接口，決定了TreeMap與HashMap的不同：

HashMap的key是無序的，TreeMap的key是有序的

接口NavigableMap

首先看下NavigableMap的簽名

public interface NavigableMap<K,V> extends SortedMap<K,V>

發(fā)現(xiàn)NavigableMap繼承了SortedMap，再看SortedMap的簽名

SortedMap

public interface SortedMap<K,V> extends Map<K,V>

SortedMap就像其名字那樣，說明這個Map是有序的。這個順序一般是指由Comparable接口提供的keys的自然序（natural ordering），或者也可以在創(chuàng)建SortedMap實(shí)例時，指定一個Comparator來 決定。 當(dāng)我們在用集合視角（collection  views，與HashMap一樣，也是由entrySet、keySet與values方法提供）來迭代（iterate）一個SortedMap實(shí)例 時會體現(xiàn)出key的順序。 這里引申下關(guān)于Comparable與Comparator的區(qū)別（參考這里）：

• Comparable一般表示類的自然序，比如定義一個Student類，學(xué)號為默認(rèn)排序

• Comparator一般表示類在某種場合下的特殊分類，需要定制化排序。比如現(xiàn)在想按照Student類的age來排序

插入SortedMap中的key的類類都必須繼承Comparable類（或指定一個comparator），這樣才能確定如何比較（通過k1.compareTo(k2)或comparator.compare(k1, k2)）兩個key，否則，在插入時，會報ClassCastException的異常。 此為，SortedMap中key的順序性應(yīng)該與equals方法保持一致。也就是說k1.compareTo(k2)或comparator.compare(k1, k2)為true時，k1.equals(k2)也 應(yīng)該為true。 介紹完了SortedMap，再來回到我們的NavigableMap上面來。  NavigableMap是JDK1.6新增的，在SortedMap的基礎(chǔ)上，增加了一些“導(dǎo)航方法”（navigation  methods）來返回與搜索目標(biāo)最近的元素。例如下面這些方法：

• lowerEntry，返回所有比給定Map.Entry小的元素

• floorEntry，返回所有比給定Map.Entry小或相等的元素

• ceilingEntry，返回所有比給定Map.Entry大或相等的元素

• higherEntry，返回所有比給定Map.Entry大的元素

設(shè)計理念（design concept）

紅黑樹（Red&ndash;black tree）

TreeMap是用紅黑樹作為基礎(chǔ)實(shí)現(xiàn)的，紅黑樹是一種二叉搜索樹，讓我們在一起回憶下二叉搜索樹的一些性質(zhì)

二叉搜索樹

先看看二叉搜索樹（binary search tree，BST）長什么樣呢？

二叉搜索樹

相信大家對這個圖都不陌生，關(guān)鍵點(diǎn)是：

左子樹的值小于根節(jié)點(diǎn)，右子樹的值大于根節(jié)點(diǎn)。

二叉搜索樹的優(yōu)勢在于每進(jìn)行一次判斷就是能將問題的規(guī)模減少一半，所以如果二叉搜索樹是平衡的話，查找元素的時間復(fù)雜度為log(n)，也就是樹的高度。 我這里想到一個比較嚴(yán)肅的問題，如果說二叉搜索樹將問題規(guī)模減少了一半，那么三叉搜索樹不就將問題規(guī)模減少了三分之二，這不是更好嘛，以此類推，我們還可以有四叉搜索樹，五叉搜索樹&hellip;&hellip;對于更一般的情況：

n個元素，K叉樹搜索樹的K為多少時效率是***的？K＝2時嗎？

K 叉搜索樹

如果大家按照我上面分析，很可能也陷入一個誤區(qū)，就是

三叉搜索樹在將問題規(guī)模減少三分之二時，所需比較操作的次數(shù)是兩次（二叉搜索樹再將問題規(guī)模減少一半時，只需要一次比較操作）

我們不能把這兩次給忽略了，對于更一般的情況：

n個元素，K叉樹搜索樹需要的平均比較次數(shù)為k*log(n/k)。

對于極端情況k＝n時，K叉樹就轉(zhuǎn)化為了線性表了，復(fù)雜度也就是O(n)了，如果用數(shù)學(xué)角度來解這個問題，相當(dāng)于：

n為固定值時，k取何值時，k*log(n/k)的取值最小？

k*log(n/k)根據(jù)對數(shù)的運(yùn)算規(guī)則可以轉(zhuǎn)化為ln(n)*k/ln(k)，ln(n)為常數(shù)，所以相當(dāng)于取k/ln(k)的極小值。這個問題對于大一剛學(xué)高數(shù)的人來說再簡單不過了，我們這里直接看結(jié)果

當(dāng)k＝e時，k/ln(k)取最小值。

自然數(shù)e的取值大約為2.718左右，可以看到二叉樹基本上就是這樣***解了。在Nodejs的REPL中進(jìn)行下面的操作

function foo(k) {return k/Math.log(k);} > foo(2) 2.8853900817779268 > foo(3) 2.730717679880512 > foo(4) 2.8853900817779268 > foo(5) 3.1066746727980594

貌似k＝3時比k＝2時得到的結(jié)果還要小，那也就是說三叉搜索樹應(yīng)該比二叉搜索樹更好些呀，但是為什么二叉樹更流行呢？后來在***的stackoverflow上找到了答案，主旨如下：

現(xiàn)在的CPU可以針對二重邏輯（binary logic）的代碼做優(yōu)化，三重邏輯會被分解為多個二重邏輯。

這樣也就大概能理解為什么二叉樹這么流行了，就是因?yàn)檫M(jìn)行一次比較操作，我們最多可以將問題規(guī)模減少一半。 好了這里扯的有點(diǎn)遠(yuǎn)了，我們再回到紅黑樹上來。

紅黑樹性質(zhì)

先看看紅黑樹的樣子：

紅黑樹示例

上圖是從wiki截來的，需要說明的一點(diǎn)是：

葉子節(jié)點(diǎn)為上圖中的NIL節(jié)點(diǎn)，國內(nèi)一些教材中沒有這個NIL節(jié)點(diǎn)，我們在畫圖時有時也會省略這些NIL節(jié)點(diǎn)，但是我們需要明確，當(dāng)我們說葉子節(jié)點(diǎn)時，指的就是這些NIL節(jié)點(diǎn)。

紅黑樹通過下面5條規(guī)則，保證了樹是平衡的：

1. 樹的節(jié)點(diǎn)只有紅與黑兩種顏色

2. 根節(jié)點(diǎn)為黑色的

3. 葉子節(jié)點(diǎn)為黑色的

4. 紅色節(jié)點(diǎn)的字節(jié)點(diǎn)必定是黑色的

5. 從任意一節(jié)點(diǎn)出發(fā)，到其后繼的葉子節(jié)點(diǎn)的路徑中，黑色節(jié)點(diǎn)的數(shù)目相同

滿足了上面5個條件后，就能夠保證：根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長路徑不會大于根節(jié)點(diǎn)到葉子最短路徑的2倍。 其實(shí)這個很好理解，主要是用了性質(zhì)4與5，這里簡單說下：

假設(shè)根節(jié)點(diǎn)到葉子節(jié)點(diǎn)最短的路徑中，黑色節(jié)點(diǎn)數(shù)目為B，那么根據(jù)性質(zhì)5，根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長路徑中，黑色節(jié)點(diǎn)數(shù)目也是B，最長的情況就是每兩個黑色節(jié)點(diǎn)中間有個紅色節(jié)點(diǎn)（也就是紅黑相間的情況），所以紅色節(jié)點(diǎn)最多為B－1個。這樣就能證明上面的結(jié)論了。

紅黑樹操作

紅黑樹旋轉(zhuǎn)示例（沒有畫出NIL節(jié)點(diǎn)）

關(guān)于紅黑樹的插入、刪除、左旋、右旋這些操作，我覺得***可以做到可視化，文字表達(dá)比較繁瑣，我這里就不在獻(xiàn)丑了，網(wǎng)上能找到的也比較多，像v_July_v的《教你透徹了解紅黑樹》。我這里推薦個swf教學(xué)視頻（視頻為英文，大家不要害怕，重點(diǎn)是看圖??），7分鐘左右，大家可以參考。 這里還有個交互式紅黑樹的可視化網(wǎng)頁，大家可以上去自己操作操作，插入幾個節(jié)點(diǎn)，刪除幾個節(jié)點(diǎn)玩玩，看看左旋右旋是怎么玩的。

源碼剖析

由于紅黑樹的操作我這里不說了，所以這里基本上也就沒什么源碼可以講了，因?yàn)檫@里面重要的算法都是From CLR，這里的CLR是指Cormen, Leiserson, Rivest，他們是算法導(dǎo)論的作者，也就是說TreeMap里面算法都是參照算法導(dǎo)論的偽代碼。 因?yàn)榧t黑樹是平衡的二叉搜索樹，所以其put（包含update操作）、get、remove的時間復(fù)雜度都為log(n)。

到此，關(guān)于“Java TreeMap源碼是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！

名稱欄目：JavaTreeMap源碼是什么
鏈接URL：http://www.chinadenli.net/article22/jcojjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計公司、服務(wù)器托管、自適應(yīng)網(wǎng)站、關(guān)鍵詞優(yōu)化、網(wǎng)站改版、App開發(fā)

廣告

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