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

2019-11-06 07:02:51

字體：大中小

來源：轉載

供稿：網友

一.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詳細介紹(源碼解析)和使用示例

歡迎訪問我的csdn博客，我們一同成長！

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

博客首頁：http://blog.csdn.net/u010648555