系列文章目錄
Java集合類源碼分析（一）：Java集合類總覽
Java集合類源碼分析（二）：List接口之ArrayList實作類
Java集合類源碼分析（三）：List接口之ArrayList實作類
Java集合類源碼分析（四）：List接口之Vector實作類
Java集合類源碼分析（五）：Map接口之HashMap實作類
Java集合類源碼分析（六）：Map接口之HashTable實作類
Java集合類源碼分析（七）：Map接口之LinkedHashMap實作類
Java集合類源碼分析（八）：Map接口之TreeMap實作類
一、概念要點
TreeMap是基于紅黑樹實作的，紅黑樹是一種特殊的二叉排序樹，關于二叉排序樹及紅黑樹後續另寫博文講解。紅黑樹通過一些限制，使其不會出現二叉樹排序樹中極端的一邊倒的情況，相對二叉排序樹而言，這自然提高了查詢的效率。
紅黑樹的基本概念提一下：
- 每個節點都隻能是紅色或者黑色
- 根節點是黑色
- 每個葉節點（NIL節點，空節點）是黑色的。
- 如果一個結點是紅的，則它兩個子節點都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點。
-
從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
正是這些性質的限制，使得紅黑樹中任一節點到其子孫葉子節點的最長路徑不會長于最短路徑的2倍，是以它是一種接近平衡的二叉樹。
二、TreeMap繼承結構圖
三、關鍵代碼分析
1. 存儲結構
TreeMap的排序是基于對key的排序實作的，它的每一個Entry代表紅黑樹的一個節點，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;
}
}
2.構造方法
/**
* 采用無參構造方法，不指定比較器，這時候，排序的實作要依賴key.compareTo()方法，
* 是以key必須實作Comparable接口，并覆寫其中的compareTo方法
*/
public TreeMap() {
comparator = null;
}
/**
* 采用帶比較器的構造方法，這時候，排序依賴該比較器，key可以不用實作Comparable接口。
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* 該構造方法同樣不指定比較器，調用putAll方法将Map中的所有元素加入到TreeMap中
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
/**
* 首先将比較器指定為m的比較器，這取決于生成m時調用構造方法是否傳入了指定的構造器，而後調用buildFromSorted方法，
* 将SortedMap中的元素插入到TreeMap中，由于SortedMap中的元素師有序的，實際上它是根據SortedMap建立的TreeMap，
* 将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) {
}
}
3.操作方法
/**
* 将map中的全部節點添加到TreeMap中
* 如果Map裡的元素是排好序的，就調用buildFromSorted方法來拷貝Map中的元素，
* 而如果Map中的元素不是排好序的，就調用AbstractMap的putAll(map)方法，将Map中的元素一個個put（插入）到TreeMap中的，
* 主要因為Map中的元素是無序存放的，是以要一個個插入到紅黑樹中，使其有序存放，并滿足紅黑樹的性質。
*/
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;
}
}
// 調用AbstractMap中的putAll();
// AbstractMap中的putAll()又會調用到TreeMap的put()
super.putAll(map);
}
final Entry<K,V> getEntry(Object key) {
// 判斷比較器是否為空
if (comparator != null)
// 根據自定義的比較器來傳回結果
return getEntryUsingComparator(key);
// 比較器為空
// key為空，抛出異常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 取得K自身實作了比較接口
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
// 根據Comparable接口的compareTo函數來查找元素
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;
}
/**
* 插入操作即對應TreeMap的put方法，put操作實際上隻需按照二叉排序樹的插入步驟來操作即可，插入到指定位置後，再做調整，
* 使其保持紅黑樹的特性
*/
public V put(K key, V value) {
Entry<K,V> t = root;
// 若紅黑樹為空，則插入根節點
if (t == null) {
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);
}
// 為（key-value）建立節點
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 插入新的節點後，調用fixAfterInsertion調整紅黑樹。
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
/**
* 删除操作及對應TreeMap的deleteEntry方法，deleteEntry方法同樣也隻需按照二叉排序樹的操作步驟實作即可，
* 删除指定節點後，再對樹進行調整即可
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) {
Entry<K,V> s = successor (p);
p.key = s.key;
p.value = s.value;
p = s;
}
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null;
} else {
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
四、TreeMap關注要點
- TreeMap是根據key進行排序的，它的排序和定位需要依賴比較器或覆寫Comparable接口，也是以不需要key覆寫hashCode方法和equals方法，就可以排除掉重複的key，而HashMap的key則需要通過覆寫hashCode方法和equals方法來確定沒有重複的key。
- TreeMap的查詢、插入、删除效率均沒有HashMap高，一般隻有要對key排序時才使用TreeMap。
-
TreeMap的key不能為null，而HashMap的key可以為null。
參考：【Java集合源碼剖析】TreeMap源碼剖析
![LinkedList類注釋翻譯、源碼分析[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)