一.TreeMap的簡(jiǎn)介 TreeMap是一個(gè)有序的key-value集合，基于紅黑樹（Red-Black tree）的 NavigableMap實(shí)現(xiàn)。該映射根據(jù)其鍵的自然順序進(jìn)行排序，或者根據(jù)創(chuàng)建映射時(shí)提供的 Comparator進(jìn)行排序，具體取決于使用的構(gòu)造方法。
下面簡(jiǎn)單介紹一下 紅黑樹： 1. 根節(jié)點(diǎn)是黑色 2. 每個(gè)節(jié)點(diǎn)都只能是紅色或者黑色 3. 每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的。 4. 如果一個(gè)節(jié)點(diǎn)是紅色的，則它兩個(gè)子節(jié)點(diǎn)都是黑色的，也就是說(shuō)在一條路徑上不能出現(xiàn)兩個(gè)紅色的節(jié)點(diǎn)。 5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
二.TreeMap的繼承關(guān)系
類 TreeMap<K,V>java.lang.Object 繼承者 java.util.AbstractMap<K,V> 繼承者 java.util.TreeMap<K,V>類型參數(shù)：K - 此映射維護(hù)的鍵的類型V - 映射值的類型繼承AbstactMap類，則TreeMap是一個(gè)Map，具體key-value特性的集合！
實(shí)現(xiàn)了Navigable接口，意味著它支持一系列的導(dǎo)航方法，如有序的key返回。
實(shí)現(xiàn)了Cloneable接口，意味著它能被克隆。
實(shí)現(xiàn)了Serializable接口，意味著它支持序列化。
三.TreeMap的API Tree API
1：構(gòu)造方法
TreeMap() 使用鍵的自然順序構(gòu)造一個(gè)新的、空的樹映射。TreeMap(Comparator<? super K> comparator) 構(gòu)造一個(gè)新的、空的樹映射，該映射根據(jù)給定比較器進(jìn)行排序。TreeMap(Map<? extends K,? extends V> m) 構(gòu)造一個(gè)與給定映射具有相同映射關(guān)系的新的樹映射，該映射根據(jù)其鍵的自然順序 進(jìn)行排序。TreeMap(SortedMap<K,? extends V> m) 構(gòu)造一個(gè)與指定有序映射具有相同映射關(guān)系和相同排序順序的新的樹映射。2：方法
Map.Entry<K,V> ceilingEntry(K key) 返回一個(gè)鍵-值映射關(guān)系，它與大于等于給定鍵的最小鍵關(guān)聯(lián)；如果不存在這樣的鍵，則返回 null。 K ceilingKey(K key) 返回大于等于給定鍵的最小鍵；如果不存在這樣的鍵，則返回 null。 void clear() 從此映射中移除所有映射關(guān)系。 Object clone() 返回此 TreeMap 實(shí)例的淺表副本。 Comparator<? super K> comparator() 返回對(duì)此映射中的鍵進(jìn)行排序的比較器；如果此映射使用鍵的自然順序，則返回 null。 boolean containsKey(Object key) 如果此映射包含指定鍵的映射關(guān)系，則返回 true。 boolean containsValue(Object value) 如果此映射為指定值映射一個(gè)或多個(gè)鍵，則返回 true。 NavigableSet<K> descendingKeySet() 返回此映射中所包含鍵的逆序 NavigableSet 視圖。 NavigableMap<K,V> descendingMap() 返回此映射中所包含映射關(guān)系的逆序視圖。 Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射關(guān)系的 Set 視圖。 Map.Entry<K,V> firstEntry() 返回一個(gè)與此映射中的最小鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果映射為空，則返回 null。 K firstKey() 返回此映射中當(dāng)前第一個(gè)（最低）鍵。 Map.Entry<K,V> floorEntry(K key) 返回一個(gè)鍵-值映射關(guān)系，它與小于等于給定鍵的最大鍵關(guān)聯(lián)；如果不存在這樣的鍵，則返回 null。 K floorKey(K key) 返回小于等于給定鍵的最大鍵；如果不存在這樣的鍵，則返回 null。 V get(Object key) 返回指定鍵所映射的值，如果對(duì)于該鍵而言，此映射不包含任何映射關(guān)系，則返回 null。 SortedMap<K,V> headMap(K toKey) 返回此映射的部分視圖，其鍵值嚴(yán)格小于 toKey。 NavigableMap<K,V> headMap(K toKey, boolean inclusive) 返回此映射的部分視圖，其鍵小于（或等于，如果 inclusive 為 true）toKey。 Map.Entry<K,V> higherEntry(K key) 返回一個(gè)鍵-值映射關(guān)系，它與嚴(yán)格大于給定鍵的最小鍵關(guān)聯(lián)；如果不存在這樣的鍵，則返回 null。 K higherKey(K key) 返回嚴(yán)格大于給定鍵的最小鍵；如果不存在這樣的鍵，則返回 null。 Set<K> keySet() 返回此映射包含的鍵的 Set 視圖。 Map.Entry<K,V> lastEntry() 返回與此映射中的最大鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果映射為空，則返回 null。 K lastKey() 返回映射中當(dāng)前最后一個(gè)（最高）鍵。 Map.Entry<K,V> lowerEntry(K key) 返回一個(gè)鍵-值映射關(guān)系，它與嚴(yán)格小于給定鍵的最大鍵關(guān)聯(lián)；如果不存在這樣的鍵，則返回 null。 K lowerKey(K key) 返回嚴(yán)格小于給定鍵的最大鍵；如果不存在這樣的鍵，則返回 null。 NavigableSet<K> navigableKeySet() 返回此映射中所包含鍵的 NavigableSet 視圖。 Map.Entry<K,V> pollFirstEntry() 移除并返回與此映射中的最小鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果映射為空，則返回 null。 Map.Entry<K,V> pollLastEntry() 移除并返回與此映射中的最大鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果映射為空，則返回 null。 V put(K key, V value) 將指定值與此映射中的指定鍵進(jìn)行關(guān)聯(lián)。 void putAll(Map<? extends K,? extends V> map) 將指定映射中的所有映射關(guān)系復(fù)制到此映射中。 V remove(Object key) 如果此 TreeMap 中存在該鍵的映射關(guān)系，則將其刪除。 int size() 返回此映射中的鍵-值映射關(guān)系數(shù)。 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基本相同，這里不做分析，可以查看參考文章。里面有詳細(xì)的介紹！
五.總結(jié)
1、TreeMap是根據(jù)key進(jìn)行排序的，它的排序和定位需要依賴比較器或覆寫Comparable接口，也因此不需要key覆寫hashCode方法和equals方法，就可以排除掉重復(fù)的key，而HashMap的key則需要通過(guò)覆寫hashCode方法和equals方法來(lái)確保沒有重復(fù)的key。
2、TreeMap的查詢、插入、刪除效率均沒有HashMap高，一般只有要對(duì)key排序時(shí)才使用TreeMap。
3、TreeMap的key不能為null，而HashMap的key可以為null。
4、TreeMap不是同步的。如果多個(gè)線程同時(shí)訪問(wèn)一個(gè)映射，并且其中至少一個(gè)線程從結(jié)構(gòu)上修改了該映射，則其必須 外部同步。
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));參考文章： 1：【數(shù)據(jù)結(jié)構(gòu)與算法】二叉排序樹C實(shí)現(xiàn)（含完整源碼） 2：紅黑樹(一)之 原理和算法詳細(xì)介紹 3： TreeMap源碼剖析 4：TreeMap詳細(xì)介紹(源碼解析)和使用示例
歡迎訪問(wèn)我的csdn博客，我們一同成長(zhǎng)！
“不管做什么，只要堅(jiān)持下去就會(huì)看到不一樣！在路上，不卑不亢!”
博客首頁(yè)：http://blog.csdn.net/u010648555
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
