知識星球（點選上方公眾號，可快速關註）
來源：SylvanasSun’s Blog ，
sylvanassun.github.io/2018/03/16/2018-03-16-map_family/
TreeMap
TreeMap是基於紅黑樹（一種自平衡的二叉查詢樹）實現的一個保證有序性的Map，在繼承關係結構圖中可以得知TreeMap實現了NavigableMap介面，而該介面又繼承了SortedMap介面，我們先來看看這兩個介面定義了一些什麼功能。
SortedMap
首先是SortedMap介面，實現該介面的實現類應當按照自然排序保證key的有序性，所謂自然排序即是根據key的compareTo()函式（需要實現Comparable介面）或者在建構式中傳入的Comparator實現類來進行排序，集合檢視遍歷元素的順序也應當與key的順序一致。SortedMap介面還定義了以下幾個有效利用有序性的函式：
package java.util;
public interface SortedMap
extends Map { /**
* 用於在此Map中對key進行排序的比較器，如果為null，則使用key的compareTo()函式進行比較。
*/
Comparator super K> comparator();
/**
* 傳回一個key的範圍為從fromKey到toKey的區域性檢視（包括fromKey，不包括toKey，包左不包右），
* 如果fromKey和toKey是相等的，則傳回一個空檢視。
* 傳回的區域性檢視同樣是此Map的集合檢視，所以對它的操作是會與Map互相影響的。
*/
SortedMap
subMap(K fromKey, K toKey); /**
* 傳回一個嚴格地小於toKey的區域性檢視。
*/
SortedMap
headMap(K toKey); /**
* 傳回一個大於或等於fromKey的區域性檢視。
*/
SortedMap
tailMap(K fromKey); /**
* 傳回當前Map中的第一個key（最小）。
*/
K firstKey();
/**
* 傳回當前Map中的最後一個key（最大）。
*/
K lastKey();
Set
keySet(); Collection
values(); Set
> entrySet(); }
NavigableMap
然後是SortedMap的子介面NavigableMap，該介面擴充套件了一些用於導航（Navigation）的方法，像函式lowerEntry(key)會根據傳入的引數key傳回一個小於key的最大的一對鍵值對，例如，我們如下呼叫lowerEntry(6)，那麼將傳回key為5的鍵值對，如果沒有key為5，則會傳回key為4的鍵值對，以此類推，直到傳回null（實在找不到的情況下）。
public static void main(String[] args) {
NavigableMap
map = new TreeMap<>(); for (int i = 0; i < 10; i++)
map.put(i, i);
assert map.lowerEntry(6).getKey() == 5;
assert map.lowerEntry(5).getKey() == 4;
assert map.lowerEntry(0).getKey() == null;
}
NavigableMap定義的都是一些類似於lowerEntry(key)的方法和以逆序、升序排序的集合檢視，這些方法利用有序性實現了相比SortedMap介面更加靈活的操作。
package java.util;
public interface NavigableMap
extends SortedMap { /**
* 傳回一個小於指定key的最大的一對鍵值對，如果找不到則傳回null。
*/
Map.Entry
lowerEntry(K key); /**
* 傳回一個小於指定key的最大的一個key，如果找不到則傳回null。
*/
K lowerKey(K key);
/**
* 傳回一個小於或等於指定key的最大的一對鍵值對，如果找不到則傳回null。
*/
Map.Entry
floorEntry(K key); /**
* 傳回一個小於或等於指定key的最大的一個key，如果找不到則傳回null。
*/
K floorKey(K key);
/**
* 傳回一個大於或等於指定key的最小的一對鍵值對，如果找不到則傳回null。
*/
Map.Entry
ceilingEntry(K key); /**
* 傳回一個大於或等於指定key的最小的一個key，如果找不到則傳回null。
*/
K ceilingKey(K key);
/**
* 傳回一個大於指定key的最小的一對鍵值對，如果找不到則傳回null。
*/
Map.Entry
higherEntry(K key); /**
* 傳回一個大於指定key的最小的一個key，如果找不到則傳回null。
*/
K higherKey(K key);
/**
* 傳回該Map中最小的鍵值對，如果Map為空則傳回null。
*/
Map.Entry
firstEntry(); /**
* 傳回該Map中最大的鍵值對，如果Map為空則傳回null。
*/
Map.Entry
lastEntry(); /**
* 傳回並刪除該Map中最小的鍵值對，如果Map為空則傳回null。
*/
Map.Entry
pollFirstEntry(); /**
* 傳回並刪除該Map中最大的鍵值對，如果Map為空則傳回null。
*/
Map.Entry
pollLastEntry(); /**
* 傳回一個以當前Map降序（逆序）排序的集合檢視
*/
NavigableMap
descendingMap(); /**
* 傳回一個包含當前Map中所有key的集合檢視，該檢視中的key以升序（正序）排序。
*/
NavigableSet
navigableKeySet(); /**
* 傳回一個包含當前Map中所有key的集合檢視，該檢視中的key以降序（逆序）排序。
*/
NavigableSet
descendingKeySet(); /**
* 與SortedMap.subMap基本一致，區別在於多的兩個引數fromInclusive和toInclusive，
* 它們代表是否包含from和to，如果fromKey與toKey相等，並且fromInclusive與toInclusive
* 都為true，那麼不會傳回空集合。
*/
NavigableMap
subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);
/**
* 傳回一個小於或等於（inclusive為true的情況下）toKey的區域性檢視。
*/
NavigableMap
headMap(K toKey, boolean inclusive); /**
* 傳回一個大於或等於（inclusive為true的情況下）fromKey的區域性檢視。
*/
NavigableMap
tailMap(K fromKey, boolean inclusive); /**
* 等價於subMap(fromKey, true, toKey, false)。
*/
SortedMap
subMap(K fromKey, K toKey); /**
* 等價於headMap(toKey, false)。
*/
SortedMap
headMap(K toKey); /**
* 等價於tailMap(fromKey, true)。
*/
SortedMap
tailMap(K fromKey); }
NavigableMap介面相對於SortedMap介面來說靈活了許多，正因為TreeMap也實現了該介面，所以在需要資料有序而且想靈活地訪問它們的時候，使用TreeMap就非常合適了。
紅黑樹
上文我們提到TreeMap的內部實現基於紅黑樹，而紅黑樹又是二叉查詢樹的一種。二叉查詢樹是一種有序的樹形結構，優勢在於查詢、插入的時間複雜度只有O(log n)，特性如下：
-
任意節點最多含有兩個子節點。
-
任意節點的左、右節點都可以看做為一棵二叉查詢樹。
-
如果任意節點的左子樹不為空，那麼左子樹上的所有節點的值均小於它的根節點的值。
-
如果任意節點的右子樹不為空，那麼右子樹上的所有節點的值均大於它的根節點的值。
-
任意節點的key都是不同的。
儘管二叉查詢樹看起來很美好，但事與願違，二叉查詢樹在極端情況下會變得並不是那麼有效率，假設我們有一個有序的整數序列：1,2,3,4,5,6,7,8,9,10,…，如果把這個序列按順序全部插入到二叉查詢樹時會發生什麼呢？二叉查詢樹會產生傾斜，序列中的每一個元素都大於它的根節點（前一個元素），左子樹永遠是空的，那麼這棵二叉查詢樹就跟一個普通的連結串列沒什麼區別了，查詢操作的時間複雜度只有O(n)。
為瞭解決這個問題需要引入自平衡的二叉查詢樹，所謂自平衡，即是在樹結構將要傾斜的情況下進行修正，這個修正操作被稱為旋轉，透過旋轉操作可以讓樹趨於平衡。
紅黑樹是平衡二叉查詢樹的一種實現，它的名字來自於它的子節點是著色的，每個子節點非黑即紅，由於只有兩種顏色（兩種狀態），一般使用boolean來表示，下麵為TreeMap中實現的Entry，它代表紅黑樹中的一個節點：
// Red-black mechanics
private static final boolean RED = false;
private static final boolean BLACK = true;
/**
* Node in the Tree. Doubles as a means to pass key-value pairs back to
* user (see Map.Entry).
*/
static final class Entry
implements Map.Entry { K key;
V value;
Entry
left; Entry
right; Entry
parent; boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry
parent) { this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry,?> e = (Map.Entry,?>)o;
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + “=” + value;
}
}
任何平衡二叉查詢樹的查詢操作都是與二叉查詢樹是一樣的，因為查詢操作並不會影響樹的結構，也就不需要進行修正，程式碼如下：
public V get(Object key) {
Entry
p = getEntry(key); return (p==null ? null : p.value);
}
final Entry
getEntry(Object key) { // 使用Comparator進行比較
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings(“unchecked”)
Comparable super K> k = (Comparable super K>) key;
Entry
p = root; // 從根節點開始，不斷比較key的大小進行查詢
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; // 沒有相等的key，傳回null
}
而插入和刪除操作與平衡二叉查詢樹的細節是息息相關的，關於紅黑樹的實現細節，我之前寫過的一篇部落格紅黑樹的那點事兒已經講的很清楚了，對這方面不瞭解的讀者建議去閱讀一下，就不在這裡重覆敘述了。
集合檢視
最後看一下TreeMap的集合檢視的實現，集合檢視一般都是實現了一個封裝了當前實體的類，所以對集合檢視的修改本質上就是在修改當前實體，TreeMap也不例外。
TreeMap的headMap()、tailMap()以及subMap()函式都傳回了一個靜態內部類AscendingSubMap，從名字上也能猜出來，為了支援倒序，肯定也還有一個DescendingSubMap，它們都繼承於NavigableSubMap，一個繼承AbstractMap並實現了NavigableMap的抽象類：
abstract static class NavigableSubMap
extends AbstractMap implements NavigableMap
, java.io.Serializable { private static final long serialVersionUID = -2102997345730753016L;
final TreeMap
m; /**
* (fromStart, lo, loInclusive) 與 (toEnd, hi, hiInclusive)代表了兩個三元組，
* 如果fromStart為true，那麼範圍的下限（絕對）為map（被封裝的TreeMap）的起始key，
* 其他值將被忽略。
* 如果loInclusive為true，lo將會被包含在範圍內，否則lo是在範圍外的。
* toEnd與hiInclusive與上述邏輯相似，只不過考慮的是上限。
*/
final K lo, hi;
final boolean fromStart, toEnd;
final boolean loInclusive, hiInclusive;
NavigableSubMap(TreeMap
m, boolean fromStart, K lo, boolean loInclusive,
boolean toEnd, K hi, boolean hiInclusive) {
if (!fromStart && !toEnd) {
if (m.compare(lo, hi) > 0)
throw new IllegalArgumentException(“fromKey > toKey”);
} else {
if (!fromStart) // type check
m.compare(lo, lo);
if (!toEnd)
m.compare(hi, hi);
}
this.m = m;
this.fromStart = fromStart;
this.lo = lo;
this.loInclusive = loInclusive;
this.toEnd = toEnd;
this.hi = hi;
this.hiInclusive = hiInclusive;
}
// internal utilities
final boolean tooLow(Object key) {
if (!fromStart) {
int c = m.compare(key, lo);
// 如果key小於lo，或等於lo（需要lo不包含在範圍內）
if (c < 0 || (c == 0 && !loInclusive))
return true;
}
return false;
}
final boolean tooHigh(Object key) {
if (!toEnd) {
int c = m.compare(key, hi);
// 如果key大於hi，或等於hi（需要hi不包含在範圍內）
if (c > 0 || (c == 0 && !hiInclusive))
return true;
}
return false;
}
final boolean inRange(Object key) {
return !tooLow(key) && !tooHigh(key);
}
final boolean inClosedRange(Object key) {
return (fromStart || m.compare(key, lo) >= 0)
&& (toEnd || m.compare(hi, key) >= 0);
}
// 判斷key是否在該檢視的範圍之內
final boolean inRange(Object key, boolean inclusive) {
return inclusive ? inRange(key) : inClosedRange(key);
}
/*
* 以abs開頭的函式為關係操作的絕對版本。
*/
/*
* 獲得最小的鍵值對：
* 如果fromStart為true，那麼直接傳回當前map實體的第一個鍵值對即可，
* 否則，先判斷lo是否包含在範圍內，
* 如果是，則獲得當前map實體中大於或等於lo的最小的鍵值對，
* 如果不是，則獲得當前map實體中大於lo的最小的鍵值對。
* 如果得到的結果e超過了範圍的上限，那麼傳回null。
*/
final TreeMap.Entry
absLowest() { TreeMap.Entry
e = (fromStart ? m.getFirstEntry() :
(loInclusive ? m.getCeilingEntry(lo) :
m.getHigherEntry(lo)));
return (e == null || tooHigh(e.key)) ? null : e;
}
// 與absLowest()相反
final TreeMap.Entry
absHighest() { TreeMap.Entry
e = (toEnd ? m.getLastEntry() :
(hiInclusive ? m.getFloorEntry(hi) :
m.getLowerEntry(hi)));
return (e == null || tooLow(e.key)) ? null : e;
}
// 下麵的邏輯就都很簡單了，註意會先判斷key是否越界，
// 如果越界就傳回絕對值。
final TreeMap.Entry
absCeiling(K key) { if (tooLow(key))
return absLowest();
TreeMap.Entry
e = m.getCeilingEntry(key); return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entry
absHigher(K key) { if (tooLow(key))
return absLowest();
TreeMap.Entry
e = m.getHigherEntry(key); return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entry
absFloor(K key) { if (tooHigh(key))
return absHighest();
TreeMap.Entry
e = m.getFloorEntry(key); return (e == null || tooLow(e.key)) ? null : e;
}
final TreeMap.Entry
absLower(K key) { if (tooHigh(key))
return absHighest();
TreeMap.Entry
e = m.getLowerEntry(key); return (e == null || tooLow(e.key)) ? null : e;
}
/** 傳回升序遍歷的絕對上限 */
final TreeMap.Entry
absHighFence() { return (toEnd ? null : (hiInclusive ?
m.getHigherEntry(hi) :
m.getCeilingEntry(hi)));
}
/** 傳回降序遍歷的絕對下限 */
final TreeMap.Entry
absLowFence() { return (fromStart ? null : (loInclusive ?
m.getLowerEntry(lo) :
m.getFloorEntry(lo)));
}
// 剩下的就是實現NavigableMap的方法以及一些抽象方法
// 和NavigableSubMap中的集合檢視函式。
// 大部分操作都是靠當前實體map的方法和上述用於判斷邊界的方法提供支援
…..
}
一個區域性檢視最重要的是要能夠判斷出傳入的key是否屬於該檢視的範圍內，在上面的程式碼中可以發現NavigableSubMap提供了非常多的輔助函式用於判斷範圍，接下來我們看看NavigableSubMap的迭代器是如何實現的：
/**
* Iterators for SubMaps
*/
abstract class SubMapIterator
implements Iterator { TreeMap.Entry
lastReturned; TreeMap.Entry
next; final Object fenceKey;
int expectedModCount;
SubMapIterator(TreeMap.Entry
first, TreeMap.Entry
fence) { expectedModCount = m.modCount;
lastReturned = null;
next = first;
// UNBOUNDED是一個虛擬值（一個Object物件），表示無邊界。
fenceKey = fence == null ? UNBOUNDED : fence.key;
}
// 只要next不為null並且沒有超過邊界
public final boolean hasNext() {
return next != null && next.key != fenceKey;
}
final TreeMap.Entry
nextEntry() { TreeMap.Entry
e = next; // 已經遍歷到頭或者越界了
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
// modCount是一個記錄運算元的計數器
// 如果與expectedModCount不一致
// 則代表當前map實體在遍歷過程中已被修改過了（從其他執行緒）
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 向後移動next指標
// successor()傳回指定節點的繼任者
// 它是節點e的右子樹的最左節點
// 也就是比e大的最小的節點
// 如果e沒有右子樹，則會試圖向上尋找
next = successor(e);
lastReturned = e; // 記錄最後傳回的節點
return e;
}
final TreeMap.Entry
prevEntry() { TreeMap.Entry
e = next; if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 向前移動next指標
// predecessor()傳回指定節點的前任
// 它與successor()邏輯相反。
next = predecessor(e);
lastReturned = e;
return e;
}
final void removeAscending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 被刪除的節點被它的繼任者取代
// 執行完刪除後，lastReturned實際指向了它的繼任者
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
m.deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = m.modCount;
}
final void removeDescending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
m.deleteEntry(lastReturned);
lastReturned = null;
expectedModCount = m.modCount;
}
}
final class SubMapEntryIterator extends SubMapIterator
> { SubMapEntryIterator(TreeMap.Entry
first, TreeMap.Entry
fence) { super(first, fence);
}
public Map.Entry
next() { return nextEntry();
}
public void remove() {
removeAscending();
}
}
final class DescendingSubMapEntryIterator extends SubMapIterator
> { DescendingSubMapEntryIterator(TreeMap.Entry
last, TreeMap.Entry
fence) { super(last, fence);
}
public Map.Entry
next() { return prevEntry();
}
public void remove() {
removeDescending();
}
}
到目前為止，我們已經針對集合檢視討論了許多，想必大家也能夠理解集合檢視的概念了，由於SortedMap與NavigableMap的緣故，TreeMap中的集合檢視是非常多的，包括各種區域性檢視和不同排序的檢視，有興趣的讀者可以自己去看看原始碼，後面的內容不會再對集合檢視進行過多的解釋了。
系列
【關於投稿】
如果大家有原創好文投稿，請直接給公號傳送留言。
① 留言格式：
【投稿】+《 文章標題》+ 文章連結
② 示例：
【投稿】《不要自稱是程式員，我十多年的 IT 職場總結》：http://blog.jobbole.com/94148/
③ 最後請附上您的個人簡介哈~
看完本文有收穫？請轉發分享給更多人
關註「ImportNew」，提升Java技能
