Map大家族的那點(diǎn)事兒(3) ：TreeMap
2018-09-05 來源：importnew
原文出處： SylvanasSun's Blog
TreeMap
TreeMap是基于紅黑樹（一種自平衡的二叉查找樹）實(shí)現(xiàn)的一個(gè)保證有序性的Map，在繼承關(guān)系結(jié)構(gòu)圖中可以得知TreeMap實(shí)現(xiàn)了NavigableMap接口，而該接口又繼承了SortedMap接口，我們先來看看這兩個(gè)接口定義了一些什么功能。
SortedMap
首先是SortedMap接口，實(shí)現(xiàn)該接口的實(shí)現(xiàn)類應(yīng)當(dāng)按照自然排序保證key的有序性，所謂自然排序即是根據(jù)key的compareTo()函數(shù)（需要實(shí)現(xiàn)Comparable接口）或者在構(gòu)造函數(shù)中傳入的Comparator實(shí)現(xiàn)類來進(jìn)行排序，集合視圖遍歷元素的順序也應(yīng)當(dāng)與key的順序一致。SortedMap接口還定義了以下幾個(gè)有效利用有序性的函數(shù)：
package java.util;
public interface SortedMap<K,V> extends Map<K,V> {
/**
* 用于在此Map中對(duì)key進(jìn)行排序的比較器，如果為null，則使用key的compareTo()函數(shù)進(jìn)行比較。
*/
Comparator<? super K> comparator();
/**
* 返回一個(gè)key的范圍為從fromKey到toKey的局部視圖（包括fromKey，不包括toKey，包左不包右），
* 如果fromKey和toKey是相等的，則返回一個(gè)空視圖。
* 返回的局部視圖同樣是此Map的集合視圖，所以對(duì)它的操作是會(huì)與Map互相影響的。
*/
SortedMap<K,V> subMap(K fromKey, K toKey);
/**
* 返回一個(gè)嚴(yán)格地小于toKey的局部視圖。
*/
SortedMap<K,V> headMap(K toKey);
/**
* 返回一個(gè)大于或等于fromKey的局部視圖。
*/
SortedMap<K,V> tailMap(K fromKey);
/**
* 返回當(dāng)前Map中的第一個(gè)key（最�。�。
*/
K firstKey();
/**
* 返回當(dāng)前Map中的最后一個(gè)key（最大）。
*/
K lastKey();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
}
NavigableMap
然后是SortedMap的子接口NavigableMap，該接口擴(kuò)展了一些用于導(dǎo)航（Navigation）的方法，像函數(shù)lowerEntry(key)會(huì)根據(jù)傳入的參數(shù)key返回一個(gè)小于key的最大的一對(duì)鍵值對(duì)，例如，我們?nèi)缦抡{(diào)用lowerEntry(6)，那么將返回key為5的鍵值對(duì)，如果沒有key為5，則會(huì)返回key為4的鍵值對(duì)，以此類推，直到返回null（實(shí)在找不到的情況下）。
public static void main(String[] args) {
NavigableMap<Integer, Integer> 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)的方法和以逆序、升序排序的集合視圖，這些方法利用有序性實(shí)現(xiàn)了相比SortedMap接口更加靈活的操作。
package java.util;
public interface NavigableMap<K,V> extends SortedMap<K,V> {
/**
* 返回一個(gè)小于指定key的最大的一對(duì)鍵值對(duì)，如果找不到則返回null。
*/
Map.Entry<K,V> lowerEntry(K key);
/**
* 返回一個(gè)小于指定key的最大的一個(gè)key，如果找不到則返回null。
*/
K lowerKey(K key);
/**
* 返回一個(gè)小于或等于指定key的最大的一對(duì)鍵值對(duì)，如果找不到則返回null。
*/
Map.Entry<K,V> floorEntry(K key);
/**
* 返回一個(gè)小于或等于指定key的最大的一個(gè)key，如果找不到則返回null。
*/
K floorKey(K key);
/**
* 返回一個(gè)大于或等于指定key的最小的一對(duì)鍵值對(duì)，如果找不到則返回null。
*/
Map.Entry<K,V> ceilingEntry(K key);
/**
* 返回一個(gè)大于或等于指定key的最小的一個(gè)key，如果找不到則返回null。
*/
K ceilingKey(K key);
/**
* 返回一個(gè)大于指定key的最小的一對(duì)鍵值對(duì)，如果找不到則返回null。
*/
Map.Entry<K,V> higherEntry(K key);
/**
* 返回一個(gè)大于指定key的最小的一個(gè)key，如果找不到則返回null。
*/
K higherKey(K key);
/**
* 返回該Map中最小的鍵值對(duì)，如果Map為空則返回null。
*/
Map.Entry<K,V> firstEntry();
/**
* 返回該Map中最大的鍵值對(duì)，如果Map為空則返回null。
*/
Map.Entry<K,V> lastEntry();
/**
* 返回并刪除該Map中最小的鍵值對(duì)，如果Map為空則返回null。
*/
Map.Entry<K,V> pollFirstEntry();
/**
* 返回并刪除該Map中最大的鍵值對(duì)，如果Map為空則返回null。
*/
Map.Entry<K,V> pollLastEntry();
/**
* 返回一個(gè)以當(dāng)前Map降序（逆序）排序的集合視圖
*/
NavigableMap<K,V> descendingMap();
/**
* 返回一個(gè)包含當(dāng)前Map中所有key的集合視圖，該視圖中的key以升序（正序）排序。
*/
NavigableSet<K> navigableKeySet();
/**
* 返回一個(gè)包含當(dāng)前Map中所有key的集合視圖，該視圖中的key以降序（逆序）排序。
*/
NavigableSet<K> descendingKeySet();
/**
* 與SortedMap.subMap基本一致，區(qū)別在于多的兩個(gè)參數(shù)fromInclusive和toInclusive，
* 它們代表是否包含from和to，如果fromKey與toKey相等，并且fromInclusive與toInclusive
* 都為true，那么不會(huì)返回空集合。
*/
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
/**
* 返回一個(gè)小于或等于（inclusive為true的情況下）toKey的局部視圖。
*/
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
/**
* 返回一個(gè)大于或等于（inclusive為true的情況下）fromKey的局部視圖。
*/
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
/**
* 等價(jià)于subMap(fromKey, true, toKey, false)。
*/
SortedMap<K,V> subMap(K fromKey, K toKey);
/**
* 等價(jià)于headMap(toKey, false)。
*/
SortedMap<K,V> headMap(K toKey);
/**
* 等價(jià)于tailMap(fromKey, true)。
*/
SortedMap<K,V> tailMap(K fromKey);
}
NavigableMap接口相對(duì)于SortedMap接口來說靈活了許多，正因?yàn)門reeMap也實(shí)現(xiàn)了該接口，所以在需要數(shù)據(jù)有序而且想靈活地訪問它們的時(shí)候，使用TreeMap就非常合適了。
紅黑樹
上文我們提到TreeMap的內(nèi)部實(shí)現(xiàn)基于紅黑樹，而紅黑樹又是二叉查找樹的一種。二叉查找樹是一種有序的樹形結(jié)構(gòu)，優(yōu)勢(shì)在于查找、插入的時(shí)間復(fù)雜度只有O(log n)，特性如下：
- 任意節(jié)點(diǎn)最多含有兩個(gè)子節(jié)點(diǎn)。
- 任意節(jié)點(diǎn)的左、右節(jié)點(diǎn)都可以看做為一棵二叉查找樹。
- 如果任意節(jié)點(diǎn)的左子樹不為空，那么左子樹上的所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值。
- 如果任意節(jié)點(diǎn)的右子樹不為空，那么右子樹上的所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值。
- 任意節(jié)點(diǎn)的key都是不同的。
盡管二叉查找樹看起來很美好，但事與愿違，二叉查找樹在極端情況下會(huì)變得并不是那么有效率，假設(shè)我們有一個(gè)有序的整數(shù)序列：1,2,3,4,5,6,7,8,9,10,...，如果把這個(gè)序列按順序全部插入到二叉查找樹時(shí)會(huì)發(fā)生什么呢？二叉查找樹會(huì)產(chǎn)生傾斜，序列中的每一個(gè)元素都大于它的根節(jié)點(diǎn)（前一個(gè)元素），左子樹永遠(yuǎn)是空的，那么這棵二叉查找樹就跟一個(gè)普通的鏈表沒什么區(qū)別了，查找操作的時(shí)間復(fù)雜度只有O(n)。
為了解決這個(gè)問題需要引入自平衡的二叉查找樹，所謂自平衡，即是在樹結(jié)構(gòu)將要傾斜的情況下進(jìn)行修正，這個(gè)修正操作被稱為旋轉(zhuǎn)，通過旋轉(zhuǎn)操作可以讓樹趨于平衡。
紅黑樹是平衡二叉查找樹的一種實(shí)現(xiàn)，它的名字來自于它的子節(jié)點(diǎn)是著色的，每個(gè)子節(jié)點(diǎn)非黑即紅，由于只有兩種顏色（兩種狀態(tài)），一般使用boolean來表示，下面為TreeMap中實(shí)現(xiàn)的Entry，它代表紅黑樹中的一個(gè)節(jié)點(diǎn)：
// 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<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> 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<K,V> 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;
}
}
任何平衡二叉查找樹的查找操作都是與二叉查找樹是一樣的，因?yàn)椴檎也僮鞑⒉粫?huì)影響樹的結(jié)構(gòu)，也就不需要進(jìn)行修正，代碼如下：
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// 使用Comparator進(jìn)行比較
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
// 從根節(jié)點(diǎn)開始，不斷比較key的大小進(jìn)行查找
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0) // 小于，轉(zhuǎn)向左子樹
p = p.left;
else if (cmp > 0) // 大于，轉(zhuǎn)向右子樹
p = p.right;
else
return p;
}
return null; // 沒有相等的key，返回null
}
而插入和刪除操作與平衡二叉查找樹的細(xì)節(jié)是息息相關(guān)的，關(guān)于紅黑樹的實(shí)現(xiàn)細(xì)節(jié)，我之前寫過的一篇博客紅黑樹的那點(diǎn)事兒已經(jīng)講的很清楚了，對(duì)這方面不了解的讀者建議去閱讀一下，就不在這里重復(fù)敘述了。
集合視圖
最后看一下TreeMap的集合視圖的實(shí)現(xiàn)，集合視圖一般都是實(shí)現(xiàn)了一個(gè)封裝了當(dāng)前實(shí)例的類，所以對(duì)集合視圖的修改本質(zhì)上就是在修改當(dāng)前實(shí)例，TreeMap也不例外。
TreeMap的headMap()、tailMap()以及subMap()函數(shù)都返回了一個(gè)靜態(tài)內(nèi)部類AscendingSubMap，從名字上也能猜出來，為了支持倒序，肯定也還有一個(gè)DescendingSubMap，它們都繼承于NavigableSubMap，一個(gè)繼承AbstractMap并實(shí)現(xiàn)了NavigableMap的抽象類：
abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, java.io.Serializable {
private static final long serialVersionUID = -2102997345730753016L;
final TreeMap<K,V> m;
/**
* (fromStart, lo, loInclusive) 與 (toEnd, hi, hiInclusive)代表了兩個(gè)三元組，
* 如果fromStart為true，那么范圍的下限（絕對(duì)）為map（被封裝的TreeMap）的起始key，
* 其他值將被忽略。
* 如果loInclusive為true，lo將會(huì)被包含在范圍內(nèi)，否則lo是在范圍外的。
* toEnd與hiInclusive與上述邏輯相似，只不過考慮的是上限。
*/
final K lo, hi;
final boolean fromStart, toEnd;
final boolean loInclusive, hiInclusive;
NavigableSubMap(TreeMap<K,V> 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不包含在范圍內(nèi)）
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不包含在范圍內(nèi)）
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是否在該視圖的范圍之內(nèi)
final boolean inRange(Object key, boolean inclusive) {
return inclusive ? inRange(key) : inClosedRange(key);
}
/*
* 以abs開頭的函數(shù)為關(guān)系操作的絕對(duì)版本。
*/
/*
* 獲得最小的鍵值對(duì)：
* 如果fromStart為true，那么直接返回當(dāng)前map實(shí)例的第一個(gè)鍵值對(duì)即可，
* 否則，先判斷l(xiāng)o是否包含在范圍內(nèi)，
* 如果是，則獲得當(dāng)前map實(shí)例中大于或等于lo的最小的鍵值對(duì)，
* 如果不是，則獲得當(dāng)前map實(shí)例中大于lo的最小的鍵值對(duì)。
* 如果得到的結(jié)果e超過了范圍的上限，那么返回null。
*/
final TreeMap.Entry<K,V> absLowest() {
TreeMap.Entry<K,V> e =
(fromStart ? m.getFirstEntry() :
(loInclusive ? m.getCeilingEntry(lo) :
m.getHigherEntry(lo)));
return (e == null || tooHigh(e.key)) ? null : e;
}
// 與absLowest()相反
final TreeMap.Entry<K,V> absHighest() {
TreeMap.Entry<K,V> e =
(toEnd ? m.getLastEntry() :
(hiInclusive ? m.getFloorEntry(hi) :
m.getLowerEntry(hi)));
return (e == null || tooLow(e.key)) ? null : e;
}
// 下面的邏輯就都很簡(jiǎn)單了，注意會(huì)先判斷key是否越界，
// 如果越界就返回絕對(duì)值。
final TreeMap.Entry<K,V> absCeiling(K key) {
if (tooLow(key))
return absLowest();
TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entry<K,V> absHigher(K key) {
if (tooLow(key))
return absLowest();
TreeMap.Entry<K,V> e = m.getHigherEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entry<K,V> absFloor(K key) {
if (tooHigh(key))
return absHighest();
TreeMap.Entry<K,V> e = m.getFloorEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
final TreeMap.Entry<K,V> absLower(K key) {
if (tooHigh(key))
return absHighest();
TreeMap.Entry<K,V> e = m.getLowerEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
/** 返回升序遍歷的絕對(duì)上限 */
final TreeMap.Entry<K,V> absHighFence() {
return (toEnd ? null : (hiInclusive ?
m.getHigherEntry(hi) :
m.getCeilingEntry(hi)));
}
/** 返回降序遍歷的絕對(duì)下限 */
final TreeMap.Entry<K,V> absLowFence() {
return (fromStart ? null : (loInclusive ?
m.getLowerEntry(lo) :
m.getFloorEntry(lo)));
}
// 剩下的就是實(shí)現(xiàn)NavigableMap的方法以及一些抽象方法
// 和NavigableSubMap中的集合視圖函數(shù)。
// 大部分操作都是靠當(dāng)前實(shí)例map的方法和上述用于判斷邊界的方法提供支持
.....
}
一個(gè)局部視圖最重要的是要能夠判斷出傳入的key是否屬于該視圖的范圍內(nèi)，在上面的代碼中可以發(fā)現(xiàn)NavigableSubMap提供了非常多的輔助函數(shù)用于判斷范圍，接下來我們看看NavigableSubMap的迭代器是如何實(shí)現(xiàn)的：
/**
* Iterators for SubMaps
*/
abstract class SubMapIterator<T> implements Iterator<T> {
TreeMap.Entry<K,V> lastReturned;
TreeMap.Entry<K,V> next;
final Object fenceKey;
int expectedModCount;
SubMapIterator(TreeMap.Entry<K,V> first,
TreeMap.Entry<K,V> fence) {
expectedModCount = m.modCount;
lastReturned = null;
next = first;
// UNBOUNDED是一個(gè)虛擬值（一個(gè)Object對(duì)象），表示無邊界。
fenceKey = fence == null ? UNBOUNDED : fence.key;
}
// 只要next不為null并且沒有超過邊界
public final boolean hasNext() {
return next != null && next.key != fenceKey;
}
final TreeMap.Entry<K,V> nextEntry() {
TreeMap.Entry<K,V> e = next;
// 已經(jīng)遍歷到頭或者越界了
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
// modCount是一個(gè)記錄操作數(shù)的計(jì)數(shù)器
// 如果與expectedModCount不一致
// 則代表當(dāng)前map實(shí)例在遍歷過程中已被修改過了（從其他線程）
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 向后移動(dòng)next指針
// successor()返回指定節(jié)點(diǎn)的繼任者
// 它是節(jié)點(diǎn)e的右子樹的最左節(jié)點(diǎn)
// 也就是比e大的最小的節(jié)點(diǎn)
// 如果e沒有右子樹，則會(huì)試圖向上尋找
next = successor(e);
lastReturned = e; // 記錄最后返回的節(jié)點(diǎn)
return e;
}
final TreeMap.Entry<K,V> prevEntry() {
TreeMap.Entry<K,V> e = next;
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 向前移動(dòng)next指針
// predecessor()返回指定節(jié)點(diǎn)的前任
// 它與successor()邏輯相反。
next = predecessor(e);
lastReturned = e;
return e;
}
final void removeAscending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
// 被刪除的節(jié)點(diǎn)被它的繼任者取代
// 執(zhí)行完刪除后，lastReturned實(shí)際指向了它的繼任者
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<Map.Entry<K,V>> {
SubMapEntryIterator(TreeMap.Entry<K,V> first,
TreeMap.Entry<K,V> fence) {
super(first, fence);
}
public Map.Entry<K,V> next() {
return nextEntry();
}
public void remove() {
removeAscending();
}
}
final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
TreeMap.Entry<K,V> fence) {
super(last, fence);
}
public Map.Entry<K,V> next() {
return prevEntry();
}
public void remove() {
removeDescending();
}
}
到目前為止，我們已經(jīng)針對(duì)集合視圖討論了許多，想必大家也能夠理解集合視圖的概念了，由于SortedMap與NavigableMap的緣故，TreeMap中的集合視圖是非常多的，包括各種局部視圖和不同排序的視圖，有興趣的讀者可以自己去看看源碼，后面的內(nèi)容不會(huì)再對(duì)集合視圖進(jìn)行過多的解釋了。
標(biāo)簽： 代碼
版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。
最新資訊
熱門推薦