本篇分析TreeMap。
TreeMap的定義及說明
定義如下：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{}p
1、繼承了AbstractMap及實現(xiàn)了NavigableMap接口。我們從集合框架那一篇文章中已經(jīng)知道NavigableMap是一個擴展了SortedMap接口的接口。而SortedMap接口主要提供有序的Map實現(xiàn)。所以TreeMap是一個有序的Map。
2、實現(xiàn)了Cloneable，即支持clone。
3、實現(xiàn)了java.io.Serializable，即支持序列化和反序列化。
TreeMap是基于紅黑樹的實現(xiàn)的。根據(jù)其鍵的可比較的自然順序，或者創(chuàng)建時提供的Comparator進行排序，具體取決于使用的構造函數(shù)。
接下來看構造方法：
//比較器，用于維護TreeMap中映射的順序，如果它使用其鍵的自然順序，則為null。
private final Comparator<? super K> comparator;
//構造一個根據(jù)鍵的自然順序排序的TreeMap
public TreeMap() {
//比較器為null
comparator = null;
}
//構造空的，給定比較器的TreeMap
public TreeMap(Comparator<? super K> comparator) {
//使用指定的比較器
this.comparator = comparator;
}
//構造一個與給定映射相同的TreeMap，根據(jù)其鍵的自然順序進行排序
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
//將指定映射中的所有映射復制到此TreeMap。這些映射將替換TreeMap中對當前位于指定映射中的任何鍵的任何映射
putAll(m);
}
//構造一個與m具有相同元素和元素順序的TreeMap
public TreeMap(SortedMap<K, ? extends V> m) {
//返回用于對m中的鍵進行排序的比較器
comparator = m.comparator();
try {
//使用線性時間算法來自排序數(shù)據(jù)
buildFromSorted(m.size(),m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
從構造函數(shù)中我們知道，如果我們沒有指定比較器，則使用鍵的自然順序排序。
TreeMap源碼簡析
按照慣例，去看給TreeMap賦值的put()方法:
//比較器
private final Comparator<? super K> comparator;
//紅黑樹的根節(jié)點
private transient TreeMapEntry<K,V> root;
//TreeMap的大小
private transient int size = 0;
//TreeMap修改次數(shù)
private transient int modCount = 0;
public V put(K key, V value) {
//將根節(jié)點的值賦予t
TreeMapEntry<K,V> t = root;
//判斷根節(jié)點是否為null
if (t == null) {
//根節(jié)點為null，判斷比較器是否為null
if (comparator != null) {
//比較器為null，判斷key是否為null
if (key == null) {
//檢查輸入null值的副作用
comparator.compare(key, key);
}
} else {
//如果比較器不為null，判斷key是否為null
if (key == null) {
//key為null，拋出異常
throw new NullPointerException("key == null");
} else if (!(key instanceof Comparable)) {
//comparator為null，key不為null，但是key對象沒有實現(xiàn)Comparable接口，則拋出異常
throw new ClassCastException(
"Cannot cast" + key.getClass().getName() + " to Comparable.");
}
}
//將此元素作為根節(jié)點
root = new TreeMapEntry<>(key, value, null);
size = 1;
modCount++;
return null;
}
//如果存在根節(jié)點，執(zhí)行以下操作
//key與某個節(jié)點的key所比較的值
int cmp;
//與key相比較的某個節(jié)點
TreeMapEntry<K,V> parent;
//獲取比較器將其賦值與cpr
Comparator<? super K> cpr = comparator;
//判斷比較器是否為null
if (cpr != null) {
//比較器不為null，執(zhí)行循環(huán)
do {
//將t的值賦予parent(第一次循環(huán)為root)
parent = t;
//使用比較器比較要插入的key跟當前節(jié)點的key
cmp = cpr.compare(key, t.key);
//如果key小則將t的值置為當前節(jié)點左孩子的值
if (cmp < 0)
t = t.left;
//如果key大則將t的值置為當前節(jié)點右孩子的值
else if (cmp > 0)
t = t.right;
else
//如果key值相同，則覆蓋當前節(jié)點的值
return t.setValue(value);
} while (t != null);
}
else {
//如果比較器為null，判斷key是否為null
if (key == null)
//key為null，則拋出異常
throw new NullPointerException();
@SuppressWarnings("unchecked")
//此處注意，key需為實現(xiàn)了Comparable的對象，不然會拋出ClassCastException。
Comparable<? super K> k = (Comparable<? super K>) key;
//執(zhí)行循環(huán)
do {
//將t的值賦予parent(第一次循環(huán)為root)
parent = t;
//將key與當前節(jié)點的key做比較
cmp = k.compareTo(t.key);
if (cmp < 0)
//如果key小則將t的值置為當前節(jié)點左孩子的值
t = t.left;
else if (cmp > 0)
//如果key大則將t的值置為當前節(jié)點右孩子的值
t = t.right;
else
//如果key值相同，則覆蓋當前節(jié)點的值
return t.setValue(value);
} while (t != null);
}
//設置一個新的節(jié)點
TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
//如果key比當前節(jié)點的key值小
if (cmp < 0)
//將新元素作為當前節(jié)點的左孩子
parent.left = e;
else
//否則，將新元素作為當前節(jié)點的右孩子
parent.right = e;
//插入修正，以保證插入新元素后還是紅黑樹結構
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
private static final boolean RED = false;
private static final boolean BLACK = true;
//紅黑樹結構
static final class TreeMapEntry<K,V> implements Map.Entry<K,V> {
//key值
K key;
//value值
V value;
//左孩子
TreeMapEntry<K,V> left;
//右孩子
TreeMapEntry<K,V> right;
//父節(jié)點
TreeMapEntry<K,V> parent;
//節(jié)點顏色
boolean color = BLACK;
//初始化
TreeMapEntry(K key, V value, TreeMapEntry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
//其他方法
..........
}
通過上面的分析，我們發(fā)現(xiàn)TreeMap其實是通過操作TreeMapEntry類型的root屬性，以實現(xiàn)對數(shù)據(jù)的插入。也就是說，對TreeMap的操作其實是通過對紅黑樹的操作來完成的。
接下來，我們再分析一些其他的方法：
對TreeMapEntry的操作
對TreeMap的操作的方法有firstEntry()、lastEntry()、pollFirstEntry()、pollLastEntry()、lowerEntry()、floorEntry()、ceilingEntry()、higherEntry()。它們的都是通過對樹的遍歷找到并操作指定的節(jié)點。比如firstEntry()：
//獲取第一個節(jié)點的值
public Map.Entry<K,V> firstEntry() {
return exportEntry(getFirstEntry());
}
//獲取第一個節(jié)點的值
final TreeMapEntry<K,V> getFirstEntry() {
//遍歷樹的左節(jié)點，獲取第一個節(jié)點的值
TreeMapEntry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
//返回一個AbstractMap.SimpleImmutableEntry
static <K,V> Map.Entry<K,V> exportEntry(TreeMapEntry<K,V> e) {
return (e == null) ? null :
new AbstractMap.SimpleImmutableEntry<>(e);
}
//給key和value賦值
public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
在上面的分析中，我們發(fā)現(xiàn)一個陌生的類，AbstractMap.SimpleImmutableEntry。這個類是為了使鍵和值不可變，該類不支持setValue()方法。這么做是為了防止我們修改返回的Entry。
對key操作的相關方法
對key操作的方法有firstKey()、lastKey()、lowerKey()、floorKey()、ceilingKey()、higherKey()，我們看一下firstKey()方法：
public K firstKey() {
return key(getFirstEntry());
}
static <K> K key(TreeMapEntry<K,?> e) {
if (e==null)
throw new NoSuchElementException();
return e.key;
}
即通過獲取節(jié)點的TreeMapEntry對象來獲取其對應的key。
對value操作的相關方法
對value操作的方法有containsValue()、get()、values()等，我們看一下get()方法：
public V get(Object key) {
//獲取擁有指定的key的節(jié)點
TreeMapEntry<K,V> p = getEntry(key);
//返回值
return (p==null ? null : p.value);
}
final TreeMapEntry<K,V> getEntry(Object key) {
//判斷比較器是否為空
if (comparator != null)
return getEntryUsingComparator(key);
//判斷key是否為null
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
//強制轉換獲取key的比較器
Comparable<? super K> k = (Comparable<? super K>) key;
//將root的值賦予t
TreeMapEntry<K,V> p = root;
//遍歷樹并獲取擁有指定key的節(jié)點，沒有返回null
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;
}
我們可以看到，其實還是通過對樹的遍歷獲取指定的節(jié)點，再獲取指定的值。
與樹相關的操作
與操作樹相關的方法有左旋(rotateLeft())、右旋(rotateRight())、插入修正(fixAfterInsertion())、刪除修正(fixAfterDeletion())等等。我們看一下左旋：
private void rotateLeft(TreeMapEntry<K,V> p) {
if (p != null) {
TreeMapEntry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
好了，本篇文章就分析到這，后期看看是否有補充。
