TreeMap
文章開頭，全家桶少不了。
作為HashMap的好兄弟，TreeMap存在肯定是有的他的理由的。
我看源碼喜歡先看JavaDoc
翻譯TreeMap的JavaDoc
基于紅黑樹的NavigableMap實現(xiàn)。 根據(jù)映射的鍵的Comparable或根據(jù)映射創(chuàng)建時提供的Comparator對映射進行排序，具體取決于所使用的構(gòu)造函數(shù)。
此實現(xiàn)為containsKey，get，put和remove操作提供了保證的log（n）時間成本。算法是對Cormen，Leiserson和Rivest的<<算法簡介>>中的算法的改編。
請注意，與任何已排序的映射一樣，樹映射所維護的順序以及是否提供顯式比較器，必須與equals是正確的實現(xiàn)Map接口。具體請參見Comparable或Comparator，以精確了解與equals一致的。之所以這樣，是因為Map接口是根據(jù)equals操作的，但是排序的映射使用其compareTo或compare方法執(zhí)行所有鍵比較，此方法視為相等的兩個鍵是排序后的Map。排序后的映射的行為是明確定義的，即使其順序與equals不匹配；它只是無法遵守Map接口的一般合同。
查看TreeMap的繼承圖
也就是說所有基本的CRUD操作其實都是和Map一樣的，所以就不詳細寫了，主要還是寫一些這個的應(yīng)用場景以及使用的注意點，以及他的特點。
首先TreeMap是基于紅黑樹來實現(xiàn)的，那就順帶復(fù)習(xí)一下紅黑樹好了。
紅黑樹規(guī)則特點：
節(jié)點分為紅色或者黑色；
根節(jié)點必為黑色；
葉子節(jié)點都為黑色，且為null；
連接紅色節(jié)點的兩個子節(jié)點都為黑色（紅黑樹不會出現(xiàn)相鄰的紅色節(jié)點）；
從任意節(jié)點出發(fā)，到其每個葉子節(jié)點的路徑中包含相同數(shù)量的黑色節(jié)點；
新加入到紅黑樹的節(jié)點為紅色節(jié)點；
紅黑樹自平衡基本操作：
變色：在不違反上述紅黑樹規(guī)則特點情況下，將紅黑樹某個node節(jié)點顏色由紅變黑，或者由黑變紅；
左旋：逆時針旋轉(zhuǎn)兩個節(jié)點，讓一個節(jié)點被其右子節(jié)點取代，而該節(jié)點成為右子節(jié)點的左子節(jié)點
右旋：順時針旋轉(zhuǎn)兩個節(jié)點，讓一個節(jié)點被其左子節(jié)點取代，而該節(jié)點成為左子節(jié)點的右子節(jié)點
TreeMap的特點：
TreeMap實現(xiàn)了NavigableMap接口，而NavigableMap接口繼承著SortedMap接口，致使我們的TreeMap是有序的！如果沒有實現(xiàn)comparator，默認按照key的自然順序排序。如果在構(gòu)造方法中傳遞了Comparator對象，那么就會按照Comparator的方法進行比較值得說明的是：如果使用的是compareTo(T o)方法來比較，key一定是不能為null，并且得實現(xiàn)了Comparable接口的。即使是傳入了Comparator對象，不用compareTo(T o)方法來比較，key也是不能為null的
由于底層是紅黑樹，那么時間復(fù)雜度可以保證為log(n)這個理論的介紹可以看https://blog.csdn.net/JERRY_PRI/article/details/8959426?utm_source=blogxgwz1
key不能為null，為null為拋出NullPointException的，但是如果硬要為null就是在構(gòu)造的時候用自己的Comparator
想要自定義比較，在構(gòu)造方法中傳入Comparator對象，否則使用key的自然排序來進行比較
TreeMap非同步的，想要同步可以使用Collections來進行封裝
TreeMap的使用場景：
這其實也認為是紅黑樹的使用場景
紅黑樹是犧牲了嚴(yán)格的高度平衡的優(yōu)越條件為代價，它只要求部分地達到平衡要求，降低了對旋轉(zhuǎn)的要求，從而提高了性能。
紅黑樹能夠以O(shè)(log2 n)的時間復(fù)雜度進行搜索、插入、刪除操作。此外，由于它的設(shè)計，任何不平衡都會在三次旋轉(zhuǎn)之內(nèi)解決。當(dāng)然，還有一些更好的，但實現(xiàn)起來更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)能夠做到一步旋轉(zhuǎn)之內(nèi)達到平衡，但紅黑樹能夠給我們一個比較“便宜”的解決方案。
TreeMap 實現(xiàn)了 SortMap 接口，其能夠根據(jù)鍵排序，默認是按鍵的升序排序，也可以指定排序的比較器，當(dāng)用 Iterator 遍歷 TreeMap 時得到的記錄是排過序的，TreeMap 取出來的是排序后的鍵值
紅黑樹占用的內(nèi)存更?。▋H需要為其存在的節(jié)點分配內(nèi)存），而Hash事先應(yīng)該分配足夠的內(nèi)存存儲散列表,即使有些槽可能棄用。
TreeMap的注意點：
紅黑樹是以 key 來進行排序的，所以這里以 key 來進行比較檢索出合適的葉子結(jié)點，而比較多依據(jù)就是 Comparator 或者 Comparable ，如果比較出來的結(jié)果是 0，那么后面的 value 會覆蓋前面的 value。所以在使用 Map 的時候，一定要注意底層的數(shù)據(jù)結(jié)構(gòu)和對 key 的處理方式。
總結(jié)
- 上一篇： 【H2 Database】导出CSV
- 下一篇： 对嗓子有好处的水果