TreeMap底層數據結構

在日常的工作中，相比較與HashMap而言，TreeMap的使用會少很多，即使在某些場景，需要使用到排序的Map時，也更多的是選擇LinkedHashMap，那麼這個TreeMap到底是個怎樣的容器，又適用於什麼樣的應用場景呢？

1. 數據結構分析

分析數據結構，最好的方式無疑是google+baidu+源碼了

1. 繼承體系

看到源碼第一眼，就會發現與HashMap不同的是 TreeMap 實現的是NavigableMap，而不是直接實現Map

有必要仔細看下這個NavigableMap，到底有些什麼特殊之處

繼承體系:

Map -> SortMap -> NavigbleMap

其中SortMap新增了下面幾個介面，目前也不知道具體有啥用，先翻譯下源碼註釋

接著就是NavigableMap定義的介面

基本上這兩個介面就是提供了一些基於排序的獲取kv對的方式

2. 數據結構

看下內部的成員變數，發現可能涉及到數據結構的就只有下面的這個root了

private transient Entry<K,V> root;

結合TreeMap的命名來看，底層的結構多半就真的是Tree了，有樹的根節點，一般來講遍歷都是沒啥問題的

接下來看下 Entry的實現

從Entry的內部成員變數可以看出，這是一個二叉樹，且極有可能就是一顆紅黑樹（因為有個black）

2. 添加一個kv對

通過新增一個kv對的調用鏈，來分析下這棵樹，到底是不是紅黑樹

將put方法撈出來, 然後補上註釋

從添加邏輯，可以得出結論：

1. 樹結構為二叉排序樹（且不能出現相等的情況）

2. 重排的方法可以保證該樹為紅黑樹

所以新增一個kv對的邏輯就比較簡單了

遍歷樹，將kv對作為葉子節點存在對應的位置

使用說明

TreeMap 的優點

1.紅黑樹，先天支持排序TreeMap根絕key進行比較排序

• 支持自定義實現的比較器

• key實現Comparable介面HashMap無排序功能

2. 存儲空間少

• Treemap紅黑樹中一個節點對應一個kv對，沒有冗餘無效的Node節點

• HashMap的數組中，可能存在較多的空位

TreeMap 的缺點

1. 查詢的時間複雜度

正常來講，TreeMap 的查詢時間複雜度為O(logN),而HashMap為O(1)

所以Map的元素越多，TreeMap根據key查詢的效率會更低；

另一方面，HashMap在糟糕的情況下，可能退化為鏈表

2. 修改導致重排

TreeMap 每次新增or刪除一個kv對，都可能導致紅黑樹的重排HashMap

當新增一個kv對，使得Map中的個數大於閥值時，需要對數組進行重新擴容

使用場景

通過上面的優缺點對比，可以看出TreeMap和HashMap兩者的使用場景差別算是比較大的

對Map中的kv對有排序需求時，選擇TreeMap, 這種場景下，盡量保證以下幾點

• Map 元素基本保持不變（即很少添加和刪除）

• 主要用於遍歷迭代獲取數據

• 不存在碰撞的情況（即兩個不同的key，根據比較器獲取值不能為0）

小結

紅黑樹相關可以作為獨立的一個知識點，這裡不詳細展開，基本上通過上面的分析，可以得出下面幾個點

1. TreeMap 底層結構為紅黑樹

2. 紅黑樹的Node排序是根據Key進行比較

3. 每次新增刪除節點，都可能導致紅黑樹的重排

4. 紅黑樹中不支持兩個or已上的Node節點對應紅黑值相等