日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
JavaTreeMap源碼解析

 繼上篇文章介紹完了HashMap，這篇文章開(kāi)始介紹Map系列另一個(gè)比較重要的類TreeMap。 大家也許能感覺(jué)到，網(wǎng)絡(luò)上介紹HashMap的文章比較多，但是介紹TreeMap反而不那么多，這里面是有原因：一方面HashMap的使用場(chǎng)景比較多；二是相對(duì)于HashMap來(lái)說(shuō)，TreeMap所用到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜。 廢話不多說(shuō)，進(jìn)入正題。

因?yàn)榕驼嬲\(chéng)，有更多的客戶和我們聚集在一起，為了共同目標(biāo)，成都創(chuàng)新互聯(lián)公司在工作上密切配合，從創(chuàng)業(yè)型企業(yè)到如今不斷成長(zhǎng)，要感謝客戶對(duì)我們的高要求，讓我們敢于面對(duì)挑戰(zhàn)，才有今天的進(jìn)步與發(fā)展。從網(wǎng)站到微信小程序定制開(kāi)發(fā),軟件開(kāi)發(fā),成都App定制開(kāi)發(fā),十多年企業(yè)網(wǎng)站建設(shè)服務(wù)經(jīng)驗(yàn),為企業(yè)提供網(wǎng)站設(shè)計(jì),網(wǎng)站改版維護(hù)一條龍服務(wù).為企業(yè)提供網(wǎng)絡(luò)營(yíng)銷推廣,定制網(wǎng)站制作,原創(chuàng)設(shè)計(jì),十多年品質(zhì),值得您的信賴.

簽名（signature）

public class TreeMap
       extends AbstractMap
       implements NavigableMap, Cloneable, java.io.Serializable

可以看到，相比HashMap來(lái)說(shuō)，TreeMap多繼承了一個(gè)接口NavigableMap，也就是這個(gè)接口，決定了TreeMap與HashMap的不同：

HashMap的key是無(wú)序的，TreeMap的key是有序的

接口NavigableMap

首先看下NavigableMap的簽名

public interface NavigableMap extends SortedMap

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

SortedMap

public interface SortedMap extends Map

SortedMap就像其名字那樣，說(shuō)明這個(gè)Map是有序的。這個(gè)順序一般是指由Comparable接口提供的keys的自然序（natural ordering），或者也可以在創(chuàng)建SortedMap實(shí)例時(shí)，指定一個(gè)Comparator來(lái) 決定。 當(dāng)我們?cè)谟眉弦暯牵╟ollection views，與HashMap一樣，也是由entrySet、keySet與values方法提供）來(lái)迭代（iterate）一個(gè)SortedMap實(shí)例 時(shí)會(huì)體現(xiàn)出key的順序。 這里引申下關(guān)于Comparable與Comparator的區(qū)別（參考這里）：

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

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

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

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

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

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

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

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

紅黑樹(shù)（Red–black tree）

TreeMap是用紅黑樹(shù)作為基礎(chǔ)實(shí)現(xiàn)的，紅黑樹(shù)是一種二叉搜索樹(shù)，讓我們?cè)谝黄鸹貞浵露嫠阉鳂?shù)的一些性質(zhì)

二叉搜索樹(shù)

先看看二叉搜索樹(shù)（binary search tree，BST）長(zhǎng)什么樣呢？


二叉搜索樹(shù)

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

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

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

n個(gè)元素，K叉樹(shù)搜索樹(shù)的K為多少時(shí)效率是***的？K＝2時(shí)嗎？

K 叉搜索樹(shù)

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

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

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

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

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

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

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

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

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

 
 
    
  
  
  1. function foo(k) {return k/Math.log(k);} 
    2. 
  
  
  2. > foo(2) 
    3. 
  
  
  3. 2.8853900817779268 
    4. 
  
  
  4. > foo(3) 
    5. 
  
  
  5. 2.730717679880512 
    6. 
  
  
  6. > foo(4) 
    7. 
  
  
  7. 2.8853900817779268 
    8. 
  
  
  8. > foo(5) 
    9. 
  
  
  9. 3.1066746727980594 
    10.

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

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

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

紅黑樹(shù)性質(zhì)

先看看紅黑樹(shù)的樣子：


紅黑樹(shù)示例

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

葉子節(jié)點(diǎn)為上圖中的NIL節(jié)點(diǎn)，國(guó)內(nèi)一些教材中沒(méi)有這個(gè)NIL節(jié)點(diǎn)，我們?cè)诋?huà)圖時(shí)有時(shí)也會(huì)省略這些NIL節(jié)點(diǎn)，但是我們需要明確，當(dāng)我們說(shuō)葉子節(jié)點(diǎn)時(shí)，指的就是這些NIL節(jié)點(diǎn)。

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

  1. 樹(shù)的節(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個(gè)條件后，就能夠保證：根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑不會(huì)大于根節(jié)點(diǎn)到葉子最短路徑的2倍。 其實(shí)這個(gè)很好理解，主要是用了性質(zhì)4與5，這里簡(jiǎn)單說(shuō)下：

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

紅黑樹(shù)操作


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

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

源碼剖析

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

總結(jié)

到目前為止，TreeMap與HashMap的的實(shí)現(xiàn)算是都介紹完了，可以看到它們實(shí)現(xiàn)的不同，決定了它們應(yīng)用場(chǎng)景的不同：

  • TreeMap的key是有序的，增刪改查操作的時(shí)間復(fù)雜度為O(log(n))，為了保證紅黑樹(shù)平衡，在必要時(shí)會(huì)進(jìn)行旋轉(zhuǎn)
  • HashMap的key是無(wú)序的，增刪改查操作的時(shí)間復(fù)雜度為O(1)，為了做到動(dòng)態(tài)擴(kuò)容，在必要時(shí)會(huì)進(jìn)行resize。

另外，我這里沒(méi)有解釋具體代碼，難免有些標(biāo)題黨了，請(qǐng)大家見(jiàn)諒，后面理解的更深刻了再來(lái)填坑。


當(dāng)前文章：JavaTreeMap源碼解析
本文路徑：http://m.5511xx.com/article/djegcic.html