TreeMap源码
原博
1.介紹
所有已實現的接口：
Serializable, Cloneable, Map<K,V>, NavigableMap<K,V>, SortedMap<K,V>
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable- TreeMap 是一個有序的key-value集合，它是通過紅黑樹實現的。
- 該映射根據其鍵的自然順序進行排序，或者根據創建映射時提供的 Comparator 進行排序，具體取決于使用的構造方法。
- TreeMap 繼承于AbstractMap，所以它是一個Map，即一個key-value集合。
- TreeMap 實現了NavigableMap接口，意味著它支持一系列的導航方法。比如返回有序的key集合。
- TreeMap 實現了Cloneable接口，意味著它能被克隆。
- TreeMap 實現了java.io.Serializable接口，意味著它支持序列化。
此實現為 containsKey、get、put 和 remove 操作提供受保證的 log(n) 時間開銷。
此實現不是同步的。
2.構造方法
TreeMap()：使用鍵的自然順序構造一個新的、空的樹映射。
TreeMap(Comparator<? super K>?comparator)：構造一個新的、空的樹映射，該映射根據給定比較器進行排序。
TreeMap(Map<? extends K,? extends V>?m)：??構造一個與給定映射具有相同映射關系的新的樹映射，該映射根據其鍵的自然順序 進行排序。
TreeMap(SortedMap<K,? extends V>?m)：構造一個與指定有序映射具有相同映射關系和相同排序順序的新的樹映射。
3.TreeMap和Map的關系
TreeMap的本質是R-B Tree(紅黑樹)，它包含幾個重要的成員變量： root, size, comparator。
- root 是紅黑數的根節點。它是Entry類型。
- Entry是紅黑數的節點，它包含了紅黑數的6個基本組成成分：key(鍵)、value(值)、left(左孩子)、right(右孩子)、parent(父節點)、color(顏色)。
- Entry節點根據key進行排序，Entry節點包含的內容為value。
- 紅黑數排序時，根據Entry中的key進行排序。
- Entry中的key比較大小是根據比較器comparator來進行判斷的。
- size是紅黑數中節點的個數。
4.源碼分析
4.1TreeMap的紅黑樹相關內容
4.1.1數據結構
//紅黑樹的節點顏色--紅色 private static final boolean RED = false;//紅黑樹的節點顏色--黑色 private static final boolean BLACK = true;// “紅黑樹的節點”對應的類。 static final class Entry<K,V> implements Map.Entry<K,V> { ... }Entry包含了6個部分內容：
- key(鍵)
- value(值)
- left(左孩子)
- right(右孩子)
- parent(父節點)
- color(顏色)
Entry節點根據key進行排序，Entry節點包含的內容為value。
4.1.2 相關操作
//左旋 private void rotateLeft(Entry<K,V> p) { ... }//右旋 private void rotateRight(Entry<K,V> p) { ... }//插入操作 public V put(K key, V value) { ... }/*插入修正操作 紅黑樹執行插入操作之后，要執行“插入修正操作”。 目的是：保紅黑樹在進行插入節點之后，仍然是一顆紅黑樹*/ private void fixAfterInsertion(Entry<K,V> x) { ... }//刪除操作 private void deleteEntry(Entry<K,V> p) { ... }/*刪除修正操作 紅黑樹執行刪除之后，要執行“刪除修正操作”。 目的是保證：紅黑樹刪除節點之后，仍然是一顆紅黑樹*/ private void fixAfterDeletion(Entry<K,V> x) { ... }4.2構造函數
4.2.1 默認構造函數
使用默認構造函數構造TreeMap時，使用java的默認的比較器比較Key的大小，從而對TreeMap進行排序。
public TreeMap() {comparator = null; }4.2.2 帶比較器的構造函數
public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator; }4.2.3?帶Map的構造函數，Map會成為TreeMap的子集
public TreeMap(Map<? extends K, ? extends V> m) {comparator = null;putAll(m); }該構造函數會調用putAll()將m中的所有元素添加到TreeMap中。
putAll()源碼如下：
public void putAll(Map<? extends K, ? extends V> m) {for (Map.Entry<? extends K, ? extends V> e : m.entrySet())put(e.getKey(), e.getValue()); }從中，我們可以看出putAll()就是將m中的key-value逐個的添加到TreeMap中。
4.2.4?帶SortedMap的構造函數，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) {} }該構造函數不同于上一個構造函數，在上一個構造函數中傳入的參數是Map，Map不是有序的，所以要逐個添加。
而該構造函數的參數是SortedMap是一個有序的Map，我們通過buildFromSorted()來創建對應的Map。
buildFromSorted涉及到的代碼如下：
// 根據已經一個排好序的map創建一個TreeMap// 將map中的元素逐個添加到TreeMap中，并返回map的中間元素作為根節點。private final Entry<K,V> buildFromSorted(int level, int lo, int hi,int redLevel,Iterator it,java.io.ObjectInputStream str,V defaultVal)throws java.io.IOException, ClassNotFoundException {if (hi < lo) return null;// 獲取中間元素int mid = (lo + hi) / 2;Entry<K,V> left = null;// 若lo小于mid，則遞歸調用獲取(middel的)左孩子。if (lo < mid)left = buildFromSorted(level+1, lo, mid - 1, redLevel,it, str, defaultVal);// 獲取middle節點對應的key和valueK key;V value;if (it != null) {if (defaultVal==null) {Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();key = entry.getKey();value = entry.getValue();} else {key = (K)it.next();value = defaultVal;}} else { // use streamkey = (K) str.readObject();value = (defaultVal != null ? defaultVal : (V) str.readObject());}// 創建middle節點Entry<K,V> middle = new Entry<K,V>(key, value, null);// 若當前節點的深度=紅色節點的深度，則將節點著色為紅色。if (level == redLevel)middle.color = RED;// 設置middle為left的父親，left為middle的左孩子if (left != null) {middle.left = left;left.parent = middle;}if (mid < hi) {// 遞歸調用獲取(middel的)右孩子。Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,it, str, defaultVal);// 設置middle為left的父親，left為middle的左孩子middle.right = right;right.parent = middle;}return middle;}要理解buildFromSorted，重點說明以下幾點：
- buildFromSorted是通過遞歸將SortedMap中的元素逐個關聯。
- buildFromSorted返回middle節點(中間節點)作為root。
- buildFromSorted添加到紅黑樹中時，只將level == redLevel的節點設為紅色。
- 第level級節點，實際上是buildFromSorted轉換成紅黑樹后的最底端(假設根節點在最上方)的節點
- 只將紅黑樹最底端的階段著色為紅色，其余都是黑色。
4.3?TreeMap的Entry相關函數
TreeMap的 firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry() 原理都是類似的；
下面以firstEntry()來進行詳細說明
我們先看看firstEntry()和getFirstEntry()的代碼：
public Map.Entry<K,V> firstEntry() {return exportEntry(getFirstEntry()); }final Entry<K,V> getFirstEntry() {Entry<K,V> p = root;if (p != null)while (p.left != null)p = p.left;return p; }從中，我們可以看出 firstEntry() 和 getFirstEntry() 都是用于獲取第一個節點。
- firstEntry() 是對外接口；
- getFirstEntry() 是內部接口。
- firstEntry() 是通過 getFirstEntry() 來實現的。
那為什么外界不能直接調用 getFirstEntry()，而需要多此一舉的調用 firstEntry() 呢?
這么做的目的是：防止用戶修改返回的Entry。
- getFirstEntry()返回的Entry是可以被修改的，
- 但是經過firstEntry()返回的Entry不能被修改，只可以讀取Entry的key值和value值。
下面我們看看到底是如何實現的。
4.3.1?getFirstEntry()
getFirstEntry()返回的是Entry節點，而Entry是紅黑樹的節點，它的源碼如下：
// 返回“紅黑樹的第一個節點” final Entry<K,V> getFirstEntry() {Entry<K,V> p = root;if (p != null)while (p.left != null)p = p.left;return p; }從中，我們可以調用Entry的getKey()、getValue()來獲取key和value值，以及調用setValue()來修改value的值。
4.3.2?firstEntry()返回的是exportEntry(getFirstEntry())
下面我們看看exportEntry()干了些什么？
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {return e == null? null :new AbstractMap.SimpleImmutableEntry<K,V>(e); }實際上，exportEntry() 是新建一個AbstractMap.SimpleImmutableEntry類型的對象，并返回。
SimpleImmutableEntry的實現在AbstractMap.java中.
下面我們看看AbstractMap.SimpleImmutableEntry是如何實現的，代碼如下：
public static class SimpleImmutableEntry<K,V> implements Entry<K,V>, java.io.Serializable {private static final long serialVersionUID = 7138329143949025153L;private final K key;private final V value;public SimpleImmutableEntry(K key, V value) {this.key = key;this.value = value;}public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {this.key = entry.getKey();this.value = entry.getValue();}public K getKey() {return key;}public V getValue() {return value;}public V setValue(V value) {throw new UnsupportedOperationException();}public boolean equals(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry e = (Map.Entry)o;return eq(key, e.getKey()) && eq(value, e.getValue());}public int hashCode() {return (key == null ? 0 : key.hashCode()) ^(value == null ? 0 : value.hashCode());}public String toString() {return key + "=" + value;} }從中，我們可以看出SimpleImmutableEntry實際上是簡化的key-value節點。
它只提供了getKey()、getValue()方法類獲取節點的值；但不能修改value的值，因為調用 setValue() 會拋出異常UnsupportedOperationException();
之前的問題：
為什么外界不能直接調用 getFirstEntry()，而需要多此一舉的調用 firstEntry() 呢?
4.4?TreeMap的key相關函數
TreeMap的firstKey()、lastKey()、lowerKey()、higherKey()、floorKey()、ceilingKey()原理都是類似的；
下面以ceilingKey()來進行詳細說明。
ceilingKey(K key)的作用：返回大于/等于key的最小的鍵值對所對應的KEY，沒有的話返回null。
它的代碼如下：
public K ceilingKey(K key) {return keyOrNull(getCeilingEntry(key)); }ceilingKey()是通過getCeilingEntry()實現的。keyOrNull()的代碼很簡單，它是獲取節點的key，沒有的話，返回null。
static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {return e == null? null : e.key; }getCeilingEntry(K key)：獲取TreeMap中大于/等于key的最小的節點，若不存在(即TreeMap中所有節點的鍵都比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 存在左孩子，則設 p=“p的左孩子”；// 否則，返回pif (cmp < 0) {if (p.left != null)p = p.left;elsereturn p;// 情況二：若“p的key” < key。} else if (cmp > 0) {// 若 p 存在右孩子，則設 p=“p的右孩子”if (p.right != null) {p = p.right;} else {// 若 p 不存在右孩子，則找出 p 的后繼節點，并返回// 注意：這里返回的 “p的后繼節點”有2種可能性：第一，null；第二，TreeMap中大于key的最小的節點。// 理解這一點的核心是，getCeilingEntry是從root開始遍歷的。// 若getCeilingEntry能走到這一步，那么，它之前“已經遍歷過的節點的key”都 > key。// 能理解上面所說的，那么就很容易明白，為什么“p的后繼節點”有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。} elsereturn p;}return null; }4.5 TreeMap其它函數
4.5.1? 順序遍歷和逆序遍歷
TreeMap的順序遍歷和逆序歷原理非常簡單。
由于TreeMap中的元素是從小到大的順序排列的。因此：
- 順序遍歷，就是從第一個元素開始，逐個向后遍歷；
- 而倒序遍歷則恰恰相反，它是從最后一個元素開始，逐個往前遍歷。
我們可以通過 keyIterator() 和 descendingKeyIterator()來說明！
- keyIterator()：返回順序的KEY的集合，
- descendingKeyIterator()：返回逆序的KEY的集合。
keyIterator() 的代碼如下：
Iterator<K> keyIterator() {return new KeyIterator(getFirstEntry()); }說明：從中我們可以看出keyIterator() 是返回以“第一個節點(getFirstEntry)” 為其實元素的迭代器。
KeyIterator的代碼如下：
final class KeyIterator extends PrivateEntryIterator<K> {KeyIterator(Entry<K,V> first) {super(first);}public K next() {return nextEntry().key;} }說明：KeyIterator繼承于PrivateEntryIterator。當我們通過next()不斷獲取下一個元素的時候，就是執行的順序遍歷了。
descendingKeyIterator()的代碼如下：
Iterator<K> descendingKeyIterator() {return new DescendingKeyIterator(getLastEntry()); }說明：從中我們可以看出descendingKeyIterator() 是返回以“最后一個節點(getLastEntry)” 為其實元素的迭代器。
再看看DescendingKeyIterator的代碼：
5.TreeMap遍歷方式
5.1?遍歷TreeMap的鍵值對
5.2 遍歷TreeMap的鍵
5.3 遍歷TreeMap的值
?
?
?
總結
- 上一篇： MySQL必知必会——了解SQL/SQL
- 下一篇： 算法练习day4——190321（小和、