TreeMap底層實現

1. TreeMap底層實現是紅黑樹，并且樹的節點是內部類Entry類型

2. 紅黑樹的定義

① 每個節點是黑色或紅色；②根節點是黑色；③所有的葉節點是黑色，不是真正的葉節點，而是每個葉節點為NIL的子節點，不知道為什么要定義葉節點NIL，既然每個葉節點都可以有NIL的子節點，有什么好說的呢？？？④紅節點的子節點不能是紅節點；⑤從一個節點到葉子節點的所有路徑包含相同黑節點數。

其實，我們只要記住三點即可。①紅黑樹的根節點是黑色；②紅節點的子節點不能是紅節點；③一個節點到葉子節點的所有路徑包含相同的黑節點數。

?

3. TreeMap類繼承結構圖

?

4. SortedMap接口顧名思義就是定義了一些關于排序有關的方法，這也是TreeMap和HashMap之間有區別的地方，方法說明如下圖。

?

5. NavigableMap顧名思義就是導航Map，也就是能迅速定位到某些key或Map，比如搜索比某個key大的key等，如下圖。

5.1 通過TreeMap中higherKey和CeilingKey的具體實現分析它們之間的區別，ceilingKey內部調用了getCeilingEntry()，higherKey內部則調用了getHigherEntry()，如下圖。

?

?

5.2 所以，higherKey是尋找大于當前key的key，而ceiling尋找大于等于當前key的key。

?

6. TreeMap對象的創建

6.1 默認構造函數——指定內部比較器為null

6.2 指定比較器的構造函數

6.3 傳入一個Map對象(如果是SortedMap實例，會調用SortedMap對象作為參數的構造方法)的構造函數——也指定比較器為null

6.4 傳入一個排序的SortedMap對象的構造函數——得到比較器并賦值

6.5 總結：對于TreeMap，要么指定比較器，要么傳入一個SortedMap對象，間接指定比較器，或者key自身實現comparable接口，比如String和Integer類。

?

7. put方法往TreeMap添加元素

?

8. get方法從TreeMap查詢、取出某元素——二叉樹搜索方式

?

9 remove方法刪除TreeMap中某個元素

?

10. TreeMap其它常用方法

10.1 containsKey——也是調用getEntry方法進行二叉樹搜索

10.2 containsValue——二叉樹中序遍歷方式

10.3 clear方法清空TreeMap——直接把根節點置為null，不像LinkedList把每個節點的前后節點都斷開連接

10.4 TreeMap最有特性的一個方法——descendingMap

?

11 TreeSet——內部是NavigableMap對象

11.1 有四種構造方法，和TreeMap不太一樣

11.2 可以通過descendingSet得到降序的Set

總結

以上是生活随笔為你收集整理的集合之TreeMap源码分析，简单介绍什么是红黑树，SortedMap和NavigableMap之间的关系和区别的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。