Java集合(一) —— Collection源碼分析
Java集合(二) —— ArrayList源碼分析
Java集合(三) —— LinkedList源碼分析
Java集合(四) —— PriorityQueue源碼分析
Java集合(五) —— HashSet源碼分析
Java集合(六) —— LinkedHashSet源碼分析
Java集合(七) —— TreeSet源碼分析
Java集合(八) —— HashMap源碼分析
Java集合(九) —— LinkedHashMap源碼分析
Java集合(十) —— TreeMap源碼分析
1.總結(jié)
1.TreeMap數(shù)據(jù)結(jié)構(gòu)：紅黑樹
2.有序的key-value映射颤芬，key必須可以自然排序的站蝠，否則就要自定義比較器Comparator作為參數(shù)傳入
3.默認(rèn)key不可以為null卓鹿，因?yàn)橐ㄟ^key排序
2.繼承關(guān)系圖
TreeMap.png
3.源碼分析
3.1成員變量分析
// key的比較器
private final Comparator<? super K> comparator;
// 紅黑樹的根節(jié)點(diǎn)
private transient Entry<K,V> root;
// treeMap的大小
private transient int size = 0;
// 樹修改的次數(shù)
private transient int modCount = 0;
// 鍵值對(duì)集合
private transient EntrySet entrySet;
// 鍵集合
private transient KeySet<K> navigableKeySet;
// 降序的NavigableMap
private transient NavigableMap<K,V> descendingMap;
3.2構(gòu)造方法分析
public TreeMap() {
comparator = null;
}
/**
* 自定義比較器comparator
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
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) {
}
}
沒啥好深究的澜倦，一般都是用默認(rèn)的構(gòu)造方法
3.3常用方法分析
1.put方法
public V put(K key, V value) {
// 將根節(jié)點(diǎn)賦值給t
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // 默認(rèn)要通過比較key進(jìn)行排序，所以key不能為null碘勉，否則空指針異常
// 如果根節(jié)點(diǎn)為null桩卵，則新增元素節(jié)點(diǎn)就是根節(jié)點(diǎn)
// 此時(shí)不用調(diào)整紅黑樹雏节，新增結(jié)束
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 使用自定義比較器進(jìn)行比較
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
// 根節(jié)點(diǎn)作為父節(jié)點(diǎn)
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();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
// k < t.key
if (cmp < 0)
t = t.left;
// k > t.key
else if (cmp > 0)
t = t.right;
// k = t.key钩乍，由于key不能重復(fù)，所以這里更新節(jié)點(diǎn)數(shù)據(jù)
else
return t.setValue(value);
} while (t != null); // 直到找到的子節(jié)點(diǎn)為null孙技，結(jié)束循環(huán)
}
// 創(chuàng)建一個(gè)新的節(jié)點(diǎn)
Entry<K,V> e = new Entry<>(key, value, parent);
// 根據(jù)比較結(jié)果判斷新增節(jié)點(diǎn)應(yīng)該是左孩子還是右孩子
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 調(diào)整紅黑樹的結(jié)構(gòu)
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
- 如果紅黑樹為null牵啦，則之間新建一個(gè)Entry節(jié)點(diǎn)妄痪，并設(shè)置為根節(jié)點(diǎn)root
- 檢查comparator是否為null衫生，不為null則使用comparator比較key的大小，否則使用k.compareTo(t.key)比較彭羹；遍歷紅黑樹泪酱，找到對(duì)應(yīng)的key墓阀，更新value
- 如果沒有找到，則新建一個(gè)Entry節(jié)點(diǎn)添加到樹上经伙，然后執(zhí)行fixAfterInsertion(e)勿锅，確保新增節(jié)點(diǎn)后仍是紅黑樹
- 關(guān)于fixAfterInsertion方法調(diào)整紅黑樹比較復(fù)雜枣氧，這里不再展開作瞄，我會(huì)在數(shù)據(jù)結(jié)構(gòu)中更新紅黑樹的分析
2.putAll方法
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
// 針對(duì)將一個(gè)非空的SortedMap加入空的TreeMap且比較器相同的情況做了優(yōu)化
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
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;
}
}
// 否則，直接遍歷給定map种蝶，將每一個(gè)節(jié)點(diǎn)添加到TreeMap上
super.putAll(map); // 會(huì)循環(huán)調(diào)用put方法
}
3.get(key)方法
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
// 使用指定比較器遍歷紅黑樹
return getEntryUsingComparator(key);
// key為null時(shí)瞒大，拋出空指針異常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
// 從根節(jié)點(diǎn)開始遍歷紅黑樹
while (p != null) {
// 將給定k與樹的節(jié)點(diǎn)的key比較
int cmp = k.compareTo(p.key);
if (cmp < 0) // < 0則遍歷左子樹
p = p.left;
else if (cmp > 0)
p = p.right; // > 0則遍歷右子樹
else
return p; // 相等表示找到節(jié)點(diǎn)
}
return null; // 否則沒有該節(jié)點(diǎn)透敌，返回null
}
4.remove()方法
public V remove(Object key) {
Entry<K,V> p = getEntry(key); // 根據(jù)key查找節(jié)點(diǎn)
if (p == null)
return null;
V oldValue = p.value;
// 刪除節(jié)點(diǎn)
deleteEntry(p);
return oldValue;
}
/**
* p：待刪除節(jié)點(diǎn)
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) { // p有左右節(jié)點(diǎn)
// 得到p的后繼節(jié)點(diǎn)酗电；得到的是p的右子樹的最左節(jié)點(diǎn)(大于當(dāng)前節(jié)點(diǎn)的最小節(jié)點(diǎn))
Entry<K,V> s = successor(p);
// 修改p的key和value，并將p指向s
p.key = s.key;
p.value = s.value;
p = s; // 經(jīng)過上述操作其實(shí)已經(jīng)將p刪除背率，p節(jié)點(diǎn)的內(nèi)容已經(jīng)變?yōu)閟節(jié)點(diǎn)的內(nèi)容
} // p has 2 children
// Start fixup at replacement node, if it exists.
// p == s寝姿，replacement為p(s)的左孩子或右孩子划滋；如果上面進(jìn)入了if代碼塊，這里得到的一定是右孩子
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
// 1.具有孩子節(jié)點(diǎn)的情況
if (replacement != null) {
// 修改replacement的父節(jié)點(diǎn)指向p的父節(jié)點(diǎn)
replacement.parent = p.parent;
if (p.parent == null) // 表示刪除的根節(jié)點(diǎn)
// 孩子節(jié)點(diǎn)成為根節(jié)點(diǎn)
root = replacement;
else if (p == p.parent.left)
// 只有進(jìn)入上面的if代碼塊才可能進(jìn)入這個(gè)代碼塊
// 此時(shí)replacement為p的右孩子根资，將p的父節(jié)點(diǎn)的左孩子指向replacement
p.parent.left = replacement;
else
// 否則嫂冻，p的父節(jié)點(diǎn)的右孩子指向replacement
p.parent.right = replacement;
// 將p節(jié)點(diǎn)刪除
p.left = p.right = p.parent = null;
if (p.color == BLACK)
// 如果p的顏色為黑色塞椎，需要調(diào)整紅黑樹的平衡
fixAfterDeletion(replacement);
} else if (p.parent == null) { // 刪除的是根節(jié)點(diǎn)且只有一個(gè)節(jié)點(diǎn)
root = null;
} else { // 刪除的節(jié)點(diǎn)沒有孩子節(jié)點(diǎn)
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的紅黑樹結(jié)構(gòu)操作比較復(fù)雜案狠，沒有紅黑樹基礎(chǔ)建議先看看紅黑樹的知識(shí)。
如果不深究的話吹零，知道TreeMap的存儲(chǔ)結(jié)構(gòu)灿椅，并且key不可以為null，默認(rèn)以key的升序排序就足夠了操刀。
