摘要：概要這一章，我們對TreeMap進行學習。我們先對TreeMap有個整體認識，然后再學習它的源碼，最后再通過實例來學會使用TreeMap。內(nèi)容包括：第1部分 TreeMap介紹第2部分 TreeMap數(shù)據(jù)結(jié)構(gòu)第3部分 TreeMap源碼解析(基于JDK1.6.0_45)第4部分 TreeMap遍歷方式第5部分 TreeMap示例第1部分 TreeMap介紹TreeMap 簡介TreeMap 是一個
概要
這一章，我們對TreeMap進行學習。
我們先對TreeMap有個整體認識，然后再學習它的源碼，最后再通過實例來學會使用TreeMap。內(nèi)容包括：
第1部分 TreeMap介紹
第2部分 TreeMap數(shù)據(jù)結(jié)構(gòu)
第3部分 TreeMap源碼解析(基于JDK1.6.0_45)
第4部分 TreeMap遍歷方式
第5部分 TreeMap示例
第1部分 TreeMap介紹
TreeMap 簡介
TreeMap 是一個有序的key-value集合，它是通過紅黑樹實現(xiàn)的。
TreeMap 繼承于AbstractMap，所以它是一個Map，即一個key-value集合。
TreeMap 實現(xiàn)了NavigableMap接口，意味著它支持一系列的導航方法。比如返回有序的key集合。
TreeMap 實現(xiàn)了Cloneable接口，意味著它能被克隆。
TreeMap 實現(xiàn)了java.io.Serializable接口，意味著它支持序列化。
TreeMap基于紅黑樹（Red-Black tree）實現(xiàn)。該映射根據(jù)其鍵的自然順序進行排序，或者根據(jù)創(chuàng)建映射時提供的 Comparator 進行排序，具體取決于使用的構(gòu)造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的時間復雜度是 log(n) 。
另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。
TreeMap的構(gòu)造函數(shù)
// 默認構(gòu)造函數(shù)。使用該構(gòu)造函數(shù)，TreeMap中的元素按照自然排序進行排列。 TreeMap() // 創(chuàng)建的TreeMap包含Map TreeMap(Map<? extends K, ? extends V> copyFrom) // 指定Tree的比較器 TreeMap(Comparator<? super K> comparator) // 創(chuàng)建的TreeSet包含copyFrom TreeMap(SortedMap<K, ? extends V> copyFrom)
TreeMap的API
Entry<K, V> ceilingEntry(K key) K ceilingKey(K key) void clear() Object clone() Comparator<? super K> comparator() boolean containsKey(Object key) NavigableSet<K> descendingKeySet() NavigableMap<K, V> descendingMap() Set<Entry<K, V>> entrySet() Entry<K, V> firstEntry() K firstKey() Entry<K, V> floorEntry(K key) K floorKey(K key) V get(Object key) NavigableMap<K, V> headMap(K to, boolean inclusive) SortedMap<K, V> headMap(K toExclusive) Entry<K, V> higherEntry(K key) K higherKey(K key) boolean isEmpty() Set<K> keySet() Entry<K, V> lastEntry() K lastKey() Entry<K, V> lowerEntry(K key) K lowerKey(K key) NavigableSet<K> navigableKeySet() Entry<K, V> pollFirstEntry() Entry<K, V> pollLastEntry() V put(K key, V value) V remove(Object key) int size() SortedMap<K, V> subMap(K fromInclusive, K toExclusive) NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive) NavigableMap<K, V> tailMap(K from, boolean inclusive) SortedMap<K, V> tailMap(K fromInclusive)
第2部分 TreeMap數(shù)據(jù)結(jié)構(gòu)
TreeMap的繼承關(guān)系
java.lang.Object
? java.util.AbstractMap<K, V>
? java.util.TreeMap<K, V>
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}TreeMap與Map關(guān)系如下圖：
從圖中可以看出：
(01) TreeMap實現(xiàn)繼承于AbstractMap，并且實現(xiàn)了NavigableMap接口。
(02) TreeMap的本質(zhì)是R-B Tree(紅黑樹)，它包含幾個重要的成員變量： root, size, comparator。
root 是紅黑數(shù)的根節(jié)點。它是Entry類型，Entry是紅黑數(shù)的節(jié)點，它包含了紅黑數(shù)的6個基本組成成分：key(鍵)、value(值)、left(左孩子)、right(右孩子)、parent(父節(jié)點)、color(顏色)。Entry節(jié)點根據(jù)key進行排序，Entry節(jié)點包含的內(nèi)容為value。
紅黑數(shù)排序時，根據(jù)Entry中的key進行排序；Entry中的key比較大小是根據(jù)比較器comparator來進行判斷的。
size是紅黑數(shù)中節(jié)點的個數(shù)。
第3部分 TreeMap源碼解析(基于JDK1.6.0_45)
為了更了解TreeMap的原理，下面對TreeMap源碼代碼作出分析。我們先給出源碼內(nèi)容，后面再對源碼進行詳細說明，當然，源碼內(nèi)容中也包含了詳細的代碼注釋。讀者閱讀的時候，建議先看后面的說明，先建立一個整體印象；之后再閱讀源碼。
package java.util;
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
// 比較器。用來給TreeMap排序
private final Comparator<? super K> comparator;
// TreeMap是紅黑樹實現(xiàn)的，root是紅黑書的根節(jié)點
private transient Entry<K,V> root = null;
// 紅黑樹的節(jié)點總數(shù)
private transient int size = 0;
// 記錄紅黑樹的修改次數(shù)
private transient int modCount = 0;
// 默認構(gòu)造函數(shù)
public TreeMap() {
comparator = null;
}
// 帶比較器的構(gòu)造函數(shù)
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
// 帶Map的構(gòu)造函數(shù)，Map會成為TreeMap的子集
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
// 帶SortedMap的構(gòu)造函數(shù)，SortedMap會成為TreeMap的子集
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) {
}
}
public int size() {
return size;
}
// 返回TreeMap中是否保護“鍵(key)”
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
// 返回TreeMap中是否保護"值(value)"
public boolean containsValue(Object value) {
// getFirstEntry() 是返回紅黑樹的第一個節(jié)點
// successor(e) 是獲取節(jié)點e的后繼節(jié)點
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
// 獲取“鍵(key)”對應(yīng)的“值(value)”
public V get(Object key) {
// 獲取“鍵”為key的節(jié)點(p)
Entry<K,V> p = getEntry(key);
// 若節(jié)點(p)為null，返回null；否則，返回節(jié)點對應(yīng)的值
return (p==null ? null : p.value);
}
public Comparator<? super K> comparator() {
return comparator;
}
// 獲取第一個節(jié)點對應(yīng)的key
public K firstKey() {
return key(getFirstEntry());
}
// 獲取最后一個節(jié)點對應(yīng)的key
public K lastKey() {
return key(getLastEntry());
}
// 將map中的全部節(jié)點添加到TreeMap中
public void putAll(Map<? extends K, ? extends V> map) {
// 獲取map的大小
int mapSize = map.size();
// 如果TreeMap的大小是0,且map的大小不是0,且map是已排序的“key-value對”
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator c = ((SortedMap)map).comparator();
// 如果TreeMap和map的比較器相等；
// 則將map的元素全部拷貝到TreeMap中，然后返回！
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
// 調(diào)用AbstractMap中的putAll();
// AbstractMap中的putAll()又會調(diào)用到TreeMap的put()
super.putAll(map);
}
// 獲取TreeMap中“鍵”為key的節(jié)點
final Entry<K,V> getEntry(Object key) {
// 若“比較器”為null，則通過getEntryUsingComparator()獲取“鍵”為key的節(jié)點
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
// 將p設(shè)為根節(jié)點
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
// 若“p的key” < key，則p=“p的左孩子”
if (cmp < 0)
p = p.left;
// 若“p的key” > key，則p=“p的左孩子”
else if (cmp > 0)
p = p.right;
// 若“p的key” = key，則返回節(jié)點p
else
return p;
}
return null;
}
// 獲取TreeMap中“鍵”為key的節(jié)點(對應(yīng)TreeMap的比較器不是null的情況)
final Entry<K,V> getEntryUsingComparator(Object key) {
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
// 將p設(shè)為根節(jié)點
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
// 若“p的key” < key，則p=“p的左孩子”
if (cmp < 0)
p = p.left;
// 若“p的key” > key，則p=“p的左孩子”
else if (cmp > 0)
p = p.right;
// 若“p的key” = key，則返回節(jié)點p
else
return p;
}
}
return null;
}
// 獲取TreeMap中不小于key的最小的節(jié)點；
// 若不存在(即TreeMap中所有節(jié)點的鍵都比key大)，就返回null
final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
// 情況一：若“p的key” > key。
// 若 p 存在左孩子，則設(shè) p=“p的左孩子”；
// 否則，返回p
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
// 情況二：若“p的key” < key。
} else if (cmp > 0) {
// 若 p 存在右孩子，則設(shè) p=“p的右孩子”
if (p.right != null) {
p = p.right;
} else {
// 若 p 不存在右孩子，則找出 p 的后繼節(jié)點，并返回
// 注意：這里返回的 “p的后繼節(jié)點”有2種可能性：第一，null；第二，TreeMap中大于key的最小的節(jié)點。
// 理解這一點的核心是，getCeilingEntry是從root開始遍歷的。
// 若getCeilingEntry能走到這一步，那么，它之前“已經(jīng)遍歷過的節(jié)點的key”都 > key。
// 能理解上面所說的，那么就很容易明白，為什么“p的后繼節(jié)點”又2種可能性了。
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
// 情況三：若“p的key” = key。
} else
return p;
}
return null;
}
// 獲取TreeMap中不大于key的最大的節(jié)點；
// 若不存在(即TreeMap中所有節(jié)點的鍵都比key小)，就返回null
// getFloorEntry的原理和getCeilingEntry類似，這里不再多說。
final Entry<K,V> getFloorEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else if (cmp < 0) {
if (p.left != null) {
p = p.left;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
}
// 獲取TreeMap中大于key的最小的節(jié)點。
// 若不存在，就返回null。
// 請參照getCeilingEntry來對getHigherEntry進行理解。
final Entry<K,V> getHigherEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
// 獲取TreeMap中小于key的最大的節(jié)點。
// 若不存在，就返回null。
// 請參照getCeilingEntry來對getLowerEntry進行理解。
final Entry<K,V> getLowerEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else {
if (p.left != null) {
p = p.left;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
// 將“key, value”添加到TreeMap中
// 理解TreeMap的前提是掌握“紅黑樹”。
// 若理解“紅黑樹中添加節(jié)點”的算法，則很容易理解put。
public V put(K key, V value) {
Entry<K,V> t = root;
// 若紅黑樹為空，則插入根節(jié)點
if (t == null) {
// TBD:
// 5045147: (coll) Adding null to an empty TreeSet should
// throw NullPointerException
//
// compare(key, key); // type check
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
// 在二叉樹(紅黑樹是特殊的二叉樹)中，找到(key, value)的插入位置。
// 紅黑樹是以key來進行排序的，所以這里以key來進行查找。
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 新建紅黑樹的節(jié)點(e)
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 紅黑樹插入節(jié)點后，不再是一顆紅黑樹；
// 這里通過fixAfterInsertion的處理，來恢復紅黑樹的特性。
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
// 刪除TreeMap中的鍵為key的節(jié)點，并返回節(jié)點的值
public V remove(Object key) {
// 找到鍵為key的節(jié)點
Entry<K,V> p = getEntry(key);
if (p == null)
retu