java集合系列——Map之TreeMap介紹（九）

一.TreeMap的簡介

TreeMap是一個有序的key-value集合，基于紅黑樹（Red-Black tree）的 NavigableMap實作。該映射根據其鍵的自然順序進行排序，或者根據建立映射時提供的 Comparator進行排序，具體取決于使用的構造方法。

下面簡單介紹一下 紅黑樹：

1. 根節點是黑色

2. 每個節點都隻能是紅色或者黑色

3. 每個葉節點（NIL節點，空節點）是黑色的。

4. 如果一個節點是紅色的，則它兩個子節點都是黑色的，也就是說在一條路徑上不能出現兩個紅色的節點。

5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

二.TreeMap的繼承關系

類 TreeMap<K,V>

java.lang.Object
  繼承者 java.util.AbstractMap<K,V>
      繼承者 java.util.TreeMap<K,V>
類型參數：
K - 此映射維護的鍵的類型
V - 映射值的類型
           

繼承AbstactMap類，則TreeMap是一個Map，具體key-value特性的集合！

實作了Navigable接口，意味着它支援一系列的導航方法，如有序的key傳回。

實作了Cloneable接口，意味着它能被克隆。

實作了Serializable接口，意味着它支援序列化。

三.TreeMap的API

Tree API

1：構造方法

TreeMap() 
          使用鍵的自然順序構造一個新的、空的樹映射。
TreeMap(Comparator<? super K> comparator) 
          構造一個新的、空的樹映射，該映射根據給定比較器進行排序。
TreeMap(Map<? extends K,? extends V> m) 
          構造一個與給定映射具有相同映射關系的新的樹映射，該映射根據其鍵的自然順序 進行排序。
TreeMap(SortedMap<K,? extends V> m) 
          構造一個與指定有序映射具有相同映射關系和相同排序順序的新的樹映射。
           

2：方法

Map.Entry<K,V> ceilingEntry(K key) 
          傳回一個鍵-值映射關系，它與大于等于給定鍵的最小鍵關聯；如果不存在這樣的鍵，則傳回 null。
 K  ceilingKey(K key) 
          傳回大于等于給定鍵的最小鍵；如果不存在這樣的鍵，則傳回 null。
 void   clear() 
          從此映射中移除所有映射關系。
 Object clone() 
          傳回此 TreeMap 執行個體的淺表副本。
 Comparator<? super K>  comparator() 
          傳回對此映射中的鍵進行排序的比較器；如果此映射使用鍵的自然順序，則傳回 null。
 boolean    containsKey(Object key) 
          如果此映射包含指定鍵的映射關系，則傳回 true。
 boolean    containsValue(Object value) 
          如果此映射為指定值映射一個或多個鍵，則傳回 true。
 NavigableSet<K>    descendingKeySet() 
          傳回此映射中所包含鍵的逆序 NavigableSet 視圖。
 NavigableMap<K,V>  descendingMap() 
          傳回此映射中所包含映射關系的逆序視圖。
 Set<Map.Entry<K,V>>    entrySet() 
          傳回此映射中包含的映射關系的 Set 視圖。
 Map.Entry<K,V> firstEntry() 
          傳回一個與此映射中的最小鍵關聯的鍵-值映射關系；如果映射為空，則傳回 null。
 K  firstKey() 
          傳回此映射中目前第一個（最低）鍵。
 Map.Entry<K,V> floorEntry(K key) 
          傳回一個鍵-值映射關系，它與小于等于給定鍵的最大鍵關聯；如果不存在這樣的鍵，則傳回 null。
 K  floorKey(K key) 
          傳回小于等于給定鍵的最大鍵；如果不存在這樣的鍵，則傳回 null。
 V  get(Object key) 
          傳回指定鍵所映射的值，如果對于該鍵而言，此映射不包含任何映射關系，則傳回 null。
 SortedMap<K,V> headMap(K toKey) 
          傳回此映射的部分視圖，其鍵值嚴格小于 toKey。
 NavigableMap<K,V>  headMap(K toKey, boolean inclusive) 
          傳回此映射的部分視圖，其鍵小于（或等于，如果 inclusive 為 true）toKey。
 Map.Entry<K,V> higherEntry(K key) 
          傳回一個鍵-值映射關系，它與嚴格大于給定鍵的最小鍵關聯；如果不存在這樣的鍵，則傳回 null。
 K  higherKey(K key) 
          傳回嚴格大于給定鍵的最小鍵；如果不存在這樣的鍵，則傳回 null。
 Set<K> keySet() 
          傳回此映射包含的鍵的 Set 視圖。
 Map.Entry<K,V> lastEntry() 
          傳回與此映射中的最大鍵關聯的鍵-值映射關系；如果映射為空，則傳回 null。
 K  lastKey() 
          傳回映射中目前最後一個（最高）鍵。
 Map.Entry<K,V> lowerEntry(K key) 
          傳回一個鍵-值映射關系，它與嚴格小于給定鍵的最大鍵關聯；如果不存在這樣的鍵，則傳回 null。
 K  lowerKey(K key) 
          傳回嚴格小于給定鍵的最大鍵；如果不存在這樣的鍵，則傳回 null。
 NavigableSet<K>    navigableKeySet() 
          傳回此映射中所包含鍵的 NavigableSet 視圖。
 Map.Entry<K,V> pollFirstEntry() 
          移除并傳回與此映射中的最小鍵關聯的鍵-值映射關系；如果映射為空，則傳回 null。
 Map.Entry<K,V> pollLastEntry() 
          移除并傳回與此映射中的最大鍵關聯的鍵-值映射關系；如果映射為空，則傳回 null。
 V  put(K key, V value) 
          将指定值與此映射中的指定鍵進行關聯。
 void   putAll(Map<? extends K,? extends V> map) 
          将指定映射中的所有映射關系複制到此映射中。
 V  remove(Object key) 
          如果此 TreeMap 中存在該鍵的映射關系，則将其删除。
 int    size() 
          傳回此映射中的鍵-值映射關系數。
 NavigableMap<K,V>  subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) 
          傳回此映射的部分視圖，其鍵的範圍從 fromKey 到 toKey。
 SortedMap<K,V> subMap(K fromKey, K toKey) 
          傳回此映射的部分視圖，其鍵值的範圍從 fromKey（包括）到 toKey（不包括）。
 SortedMap<K,V> tailMap(K fromKey) 
          傳回此映射的部分視圖，其鍵大于等于 fromKey。
 NavigableMap<K,V>  tailMap(K fromKey, boolean inclusive) 
          傳回此映射的部分視圖，其鍵大于（或等于，如果 inclusive 為 true）fromKey。
 Collection<V>  values() 
          傳回此映射包含的值的 Collection 視圖。
           

四.源碼

源碼和16基本相同，這裡不做分析，可以檢視參考文章。裡面有詳細的介紹！

五.總結

1、TreeMap是根據key進行排序的，它的排序和定位需要依賴比較器或覆寫Comparable接口，也是以不需要key覆寫hashCode方法和equals方法，就可以排除掉重複的key，而HashMap的key則需要通過覆寫hashCode方法和equals方法來確定沒有重複的key。

2、TreeMap的查詢、插入、删除效率均沒有HashMap高，一般隻有要對key排序時才使用TreeMap。

3、TreeMap的key不能為null，而HashMap的key可以為null。

4、TreeMap不是同步的。如果多個線程同時通路一個映射，并且其中至少一個線程從結構上修改了該映射，則其必須 外部同步。

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
           

參考文章：

1：【資料結構與算法】二叉排序樹C實作（含完整源碼）

2：紅黑樹(一)之 原理和算法詳細介紹

3： TreeMap源碼剖析

4：TreeMap詳細介紹(源碼解析)和使用示例

java集合系列——java集合概述（一）

java集合系列——List集合之ArrayList介紹（二）

java集合系列——List集合之LinkedList介紹（三）

java集合系列——List集合之Vector介紹（四）

java集合系列——List集合之Stack介紹（五）

java集合系列——List集合總結（六）

java集合系列——Map介紹（七）

java集合系列——Map之HashMap介紹（八）

java集合系列——Map之TreeMap介紹（九）

java集合系列——Set之HashSet和TreeSet介紹（十）

如果帥氣（美麗）、睿智（聰穎），和我一樣簡單善良的你看到本篇博文中存在問題，請指出，我虛心接受你讓我成長的批評，謝謝閱讀！

祝你今天開心愉快！

歡迎通路我的csdn部落格，我們一同成長！

“不管做什麼，隻要堅持下去就會看到不一樣！在路上，不卑不亢!”

部落格首頁：http://blog.csdn.net/u010648555