一各薇、概述
TreeMap 是一個有序的key-value集合失乾，它是通過紅黑樹實現(xiàn)的岁诉。
TreeMap 繼承于AbstractMap，所以它是一個Map喉磁，即一個key-value集合谓苟。
TreeMap 實現(xiàn)了NavigableMap接口，意味著它支持一系列的導(dǎo)航方法协怒。比如返回有序的key集合娜谊。
TreeMap 實現(xiàn)了Cloneable接口，意味著它能被克隆斤讥。
TreeMap 實現(xiàn)了java.io.Serializable接口纱皆，意味著它支持序列化。
SortedMap
擴展自Map接口芭商，定義了有序的key-value鍵值對映射集合派草。根據(jù)key排序，使用Comparable或者Comparator進行排序铛楣。
特點：
- key需要支持排序近迁。
submap:
- 1half-open they include their low* endpoint but not their high endpoint (where applicable)
- 1closed range which includes both endpoints
- 1open range which contains neither endpoint
定義API：
比較器相關(guān)：
- comparator():Comparator
視圖相關(guān)：
- subMap(K, K): SortedMap<K, V>
- headMap(K): SortedMap<K, V>
- tailMap(K): SortedMap<K, V>
定位相關(guān)：
- firstKey(): K
- lastKey(): K
NavigableMap
擴展自SortedMap接口，添加搜索相關(guān)API簸州，支持順序遍歷和反序遍歷
定位相關(guān)API（Entry／key）：
- lowerEntry(K): Entry<K, V>
- floorEntry(K): Entry<K, V>
- ceilingEntry(K): Entry<K, V>
- higherEntry(K): Entry<K, V>
- firstEntry(): Entry<K, V>
- lastEntry(): Entry<K, V>
action：
- pollFirstEntry(): Entry<K, V>
- pollLastEntry(): Entry<K, V>
反序列表：
- descendingMap():NavigableMap<K, V>
- descendingKeySet():NavigableSet<K>
視圖相關(guān)：
- navigableKeySet(): NavigableSet<K>
- subMap(K, K):NavigableMap<K, V>
- headMap(K): NavigableMap<K, V>
- tailMap(K): NavigableMap<K, V>
注意點：
NavigableMap中視圖相關(guān)方法與SortedMap中視圖相關(guān)方法不同鉴竭，NavigableMap中返回類型為NavigableMap，SortedMap中返回類型為SortedMap
二岸浑、數(shù)據(jù)結(jié)構(gòu)
TreeMap是通過紅黑樹實現(xiàn)的搏存，TreeMap存儲的是key-value鍵值對，TreeMap的排序是基于對key的排序矢洲。
使用鏈?zhǔn)浇Y(jié)構(gòu)存儲元素璧眠，只記錄root節(jié)點。使用size保存元素數(shù)量。
private transient TreeMapEntry<K,V> root = null;
private transient int size = 0;
保存一個Comparator责静，同于key排序袁滥。
private final Comparator<? super K> comparator;
TreeMapEntry
實現(xiàn)了Map.Entry<K,V>接口，保存基本key灾螃、value信息题翻。
持有父節(jié)點、左子節(jié)點腰鬼、右子節(jié)點的引用嵌赠。
記錄本節(jié)點的顏色（紅黑樹需要）。
K key;
V value;
TreeMapEntry<K,V> left = null;
TreeMapEntry<K,V> right = null;
TreeMapEntry<K,V> parent;
boolean color = BLACK;
紅黑樹（R-B Tree）
R-B Tree垃喊，全稱是Red-Black Tree，又稱為“紅黑樹”袜炕。
基本操作
- 左旋
- 右旋
- 插入
- 插入修正
- 刪除
- 刪除修正
時間復(fù)雜度：基本操作 containsKey本谜、get、put 和 remove 的時間復(fù)雜度是 log(n)
三偎窘、特點
- 有序乌助，可使用Comparator進行排序，或者對key進行默認(rèn)排序陌知。
- Iterator是fail-fast的
- 非線程安全他托。可使用Collections.synchronizedSortedMap()
- 性能穩(wěn)定仆葡∩筒危基本操作 containsKey、get沿盅、put 和 remove 的時間復(fù)雜度是 log(n)
- 對外Entry為snapshots把篓，不可修改。
- 不支持key為null值腰涧，value可以為null韧掩。
四、實現(xiàn)原理
1.基本方法
構(gòu)造函數(shù)
四個：空構(gòu)造函數(shù)窖铡、Comparator構(gòu)造函數(shù)疗锐、Map構(gòu)造函數(shù)、SortedMap構(gòu)造函數(shù)
SortedMap構(gòu)造函數(shù)：獲取SortedMap的Comparator费彼，設(shè)置為自身的Comparator
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
基本操作
添加 - key不能為null滑臊，value不能為null，插入到紅黑樹中
刪除 - getEntry(key)箍铲，然后刪除該節(jié)點
clear - 設(shè)置root為null简珠，size為null
查詢（見下面具體分類）
entry相關(guān)操作
查詢：
getEntry：根據(jù)紅黑樹性質(zhì)查找節(jié)點
final TreeMapEntry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
TreeMapEntry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
firstEntry： 返回最left的節(jié)點
final TreeMapEntry<K,V> getFirstEntry() {
TreeMapEntry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
lastEntry： 返回最right的節(jié)點
final TreeMapEntry<K,V> getLastEntry() {
TreeMapEntry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}
注意：
返回的entry并不是真實的元素，是新生的一個不可修改的entry，避免通過entry修改map結(jié)構(gòu)
static <K,V> Map.Entry<K,V> exportEntry(TreeMapEntry<K,V> e) {
return (e == null) ? null :
new AbstractMap.SimpleImmutableEntry<>(e);
}
key相關(guān)操作
containsKey：使用Comparator比較key
final TreeMapEntry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
TreeMapEntry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
value相關(guān)操作
containValue ：使用了兩個內(nèi)部方法 successor(TreeMapEntry<K,V> t)和predecessor(TreeMapEntry<K,V> t)聋庵，用于返回僅大于／小于當(dāng)前entry的key的entry膘融，通過這兩個方法遍歷map即根據(jù)key的順序來便利map。
public boolean containsValue(Object value) {
for (TreeMapEntry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
2.訪問方式
PrivateEntryIterator
實現(xiàn)Iterator類祭玉，持有next和lastReturned兩個指針氧映。
TreeMapEntry<K,V> next;
TreeMapEntry<K,V> lastReturned;
int expectedModCount;
支持前／后移動和查詢、刪除操作脱货。
調(diào)用主類中的successor(e)和 predecessor(e)方法獲取下一個／上一個entry岛都。
EntryIterator
繼承PrivateEntryIterator
next返回entry
KeyIterator
繼承PrivateEntryIterator
next返回key
ValueIterator
繼承PrivateEntryIterator
next返回value
DescendingKeyIterator
繼承PrivateEntryIterator
next返回prevEntry
重寫remove方法，刪除前一個元素振峻。
3.排序原理
默認(rèn)排序臼疫，Comparable natural ordering of keys
Comparator排序
五、視圖
支持四種視圖扣孟，EntrySet烫堤、KeySet、Values和SubMap凤价，SubMap又可分為順序和逆序兩種鸽斟。
NavigableSubMap
繼承AbstractMap，持有原NavigableMap的引用利诺。記錄lowKey富蓄、highKey或者直到Start、End慢逾，以及邊緣值的包含關(guān)系立倍。
final TreeMap<K,V> m;
final K lo, hi;
final boolean fromStart, toEnd;
final boolean loInclusive, hiInclusive;
API
- 支持大部分NavigableMap方法，通過調(diào)用原map實現(xiàn)侣滩。
- 支持繼續(xù)生成subMap帐萎。（Abstract）方法。
- 包含自己的entrySet胜卤、keySet疆导、values
- 包含自己的Iterator
子類AscendingSubMap和DescendingSubMap，分別表示順序和逆序葛躏。
EntrySet
繼承AbstractSet<Map.Entr<K,V>>
調(diào)用原Map方法實現(xiàn)澈段，Iterator返回EntryIterator
KeySet
繼承AbstractSet<Map.Entr<K,V>>，實現(xiàn)NavigableSet<E>接口舰攒。
調(diào)用原Map方法實現(xiàn)败富，Iterator返回KeyIterator／DescendingKeyIterator
Values
繼承AbstractCollection<V>
調(diào)用原Map方法實現(xiàn)
六、性能
時間復(fù)雜度：基本操作 containsKey摩窃、get兽叮、put 和 remove 的時間復(fù)雜度是 log(n)
證明過程略芬骄。
