Java中的集合(十一) 實作Map接口的TreeMap
一、TreeMap簡介(基于JDK1.8)
TreeMap是基于紅黑樹資料結構，是一個key-value的有序集合，該映射根據其鍵的自然順序進行排序，或者根據建立映射時提供的 Comparator 進行排序，具體取決于使用的構造方法。因為紅黑樹是平衡的二叉搜尋樹，是以其put、get、remove的時間複雜度都為log(n)。
(一)、TreeMap與Map的關系
(二)、資料結構
紅黑樹操作包括插入、删除、左旋、右旋，這裡有個可視化的紅黑樹操作網站，把這些操作都按動畫做出來了，生動形象。
二、TreeMap的繼承結構
(一)、繼承結構
TreeMap繼承AbstractMap，實作了Map接口。Map是key-value鍵值對接口，是以具有Map接口的特性；
實作了NavigableMap接口，而NavigableMap接口繼承了SortedMap接口，是以TreeMap具有一系列導航的方法，意味TreeMap是有序的鍵值對集合；
實作了Cloneable接口，意味着TreeMap可以被克隆；
實作了Serializable接口，意味着可以被序列化。
(二)、有序的實作
TreeMap實作了NavigableMap接口，NavigableMap是JDK1.6新增的，NavigableMap繼承了SortedMap(這個Map是有序的)，順序一般是指由Comparable接口提供的keys的自然序，或者也可以在建立SortedMap執行個體時，指定一個Comparator來決定。插入SortedMap中的key的類都必須繼承Comparable類(或指定一個comparator)，這樣才能通過k1.compareTo(k2)或comparator.compare(k1, k2)來比較兩個key。
NavigableMap接口在SortedMap的基礎上增加了一些導航方法來傳回與搜尋目标最近的元素。例如下面這些方法：
三、TreeMap的構造方法
四、TreeMap重要成員屬性
TreeMap是基于R-B Tree(紅黑樹)，它包含幾個重要的成員變量： root，size，comparator。
(一)、root
root 是紅黑數的根節點。它是Entry類型。Entry是TreeMap的内部類，實作了Map.Entry接口，是紅黑樹的節點，包含了紅黑樹的6個基本組成部分：key(鍵)、value(值)、left(左孩子)、right(右孩子)、parent(父節點)、color(顔色)。Entry節點根據key進行排序，Entry節點包含的内容為value。
(二)、size
是紅黑數中節點的個數。
(三)、comparator
比較器，紅黑數排序時，根據Entry中的key進行排序；Entry中的key比較大小是根據比較器comparator來進行判斷的。
五、TreeMap的周遊
(一)、通過entrySet()，鍵值對周遊方式
①、首先通過entrySet方法擷取鍵值對Set集合；
②、通過疊代器或者for-each循環周遊獲得的Set集合
1 //假設treeMap中的key是String類型，value是Integer類型
2 Set> set =treeMap.entrySet();3 //疊代器周遊
4 Iterator> it =set.iterator();5 while(it.hasNext()) {6 Map.Entry entry =it.next();7 String str =entry.getKey();8 Integer i =entry.getValue();9 }10
11 //for-each循環周遊
12 for (Map.Entryentry : set) {13 String str =entry.getKey();14 Integer i =entry.getValue();15 }
View Code
(二)、通過keySet()，鍵的周遊
①、首先通過keySet方法擷取鍵的Set集合；
②、通過疊代器或者for-each循環周遊獲得的Set集合
1 Set set =treeMap.keySet();2 Iterator it =set.iterator();3 while(it.hasNext()) {4 String str =it.next();5 }
View Code
(三)、通過value()，值的周遊
①、首先通過entrySet方法擷取值的Set集合；
②、通過疊代器或者for-each循環周遊獲得的Set集合
1 Collection con =treeMap.values();2 Iterator it =con.iterator();3 while(it.hasNext()) {4 Integer i =it.next();5 }
View Code
六、TreeMap常用API
七、TreeMap與HashMap異同
(一)、相同點
兩者均是線程不安全的；增删改查操作的
兩者插入節點時，key重複均覆寫舊值。
(二)、不同點
底層資料結構不同。HashMap是基于數組+連結清單+紅黑樹的資料結構，TreeMap是基于紅黑樹的資料結構。
有序無序。HashMap是無序的，TreeMap是有序的。
null值情況。HashMap允許存儲null，TreeMap的鍵不允許存儲null，但是值可以為null。
操作時間不同。HashMap增删改查操作的時間複雜度為O(1)，TreeMap增删改查的時間複雜度為O(log(n))。
TreeMap要求key必須實作Comparable接口，或者初始化時傳入Comparator比較器。
八、TreeMap與TreeSet的異同
TreeMap 是 Map 接口的實作類，而TreeSet 是 Set 接口的實作類。雖然 TreeMap 和TreeSet 實作的接口規範不同，但 TreeSet 底層是通過 TreeMap 來實作的(如同HashSet底層是是通過HashMap來實作、LinkedHashSet底層基于LinkedHashMap實作一樣)，是以二者的實作方式完全一樣，都是紅黑樹算法。
(一)、相同點
TreeMap和TreeSet都是有序的集合(僅僅key對象有序)。
TreeMap和TreeSet都是非同步的，線程不安全的。可以通過Collections.synchroinzedMap()實作同步。
内部對元素的操作時間複雜度都是O(logN)，而HashMap/HashSet/HashTable則為O(1)。
(二)、不同點
最主要的差別就是TreeSet和TreeMap分别實作Set和Map接口。
TreeSet不能存儲重複的元素，TreeMap除了鍵不能重複，但是值可以重複。
TreeSet隻存儲一個對象(單列集合)，而TreeMap存儲兩個對象Key和Value(僅僅key對象有序，雙列集合)。