容器源码分析之TreeMap(十)
生活随笔
收集整理的這篇文章主要介紹了
容器源码分析之TreeMap(十)
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
1.TreeMap的結(jié)構(gòu)
我們知道，TreeMap的內(nèi)部實(shí)現(xiàn)就是一個(gè)紅黑樹。
關(guān)于紅黑樹的介紹，建議大家先看看這里
紅黑樹的原理和算法詳細(xì)介紹
2.TreeMap的繼承關(guān)系
-
3.TreeMap的成員變量
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable {// Key的比較器，用作排序 private final Comparator<? super K> comparator; //樹的根節(jié)點(diǎn) private transient Entry<K,V> root; //樹的大小 private transient int size = 0; //修改計(jì)數(shù)器 private transient int modCount = 0; //返回map的Entry視圖 private transient EntrySet entrySet; private transient KeySet<K> navigableKeySet; private transient NavigableMap<K,V> descendingMap; //定義紅黑樹的顏色 private static final boolean RED = false; private static final boolean BLACK = true; }-
4.TreeMap構(gòu)造方法
允許用戶自定義比較器
public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator; }允許用已有的map構(gòu)造一個(gè)TreeMap
public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); } public void putAll(Map<? extends K, ? extends V> map) {int mapSize = map.size(); //判斷map是否SortedMap，不是則采用AbstractMap的putAll if (size==0 && mapSize!=0 && map instanceof SortedMap){ Comparator<?> c = ((SortedMap<?,?>)map).comparator(); //同為null或者不為null，類型相同，則進(jìn)入有序map的構(gòu)造 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; } } super.putAll(map); }讓我們來看一下buildFrmoSorted函數(shù)
/** * size: map里鍵值對(duì)的數(shù)量 * it: 傳入的map的entries迭代器 * str: 如果不為空，則從流里讀取key-value * defaultVal：見名知意，不為空，則value都用這個(gè)值 */ private void buildFromSorted(int size, Iterator<?> it,java.io.ObjectInputStream str,V defaultVal) throws java.io.IOException, ClassNotFoundException {this.size = size; root = buildFromSorted(0, 0, size-1, computeRedLevel(size), it, str, defaultVal); }computeRedLevel(size)
private static int computeRedLevel(int sz) {int level = 0; for (int m = sz - 1; m >= 0; m = m / 2 - 1) level++; return level; }這個(gè)函數(shù)是干什么的呢？
它的作用是用來計(jì)算完全二叉樹的層數(shù)。什么意思呢，先來看一下下面的圖：
把根結(jié)點(diǎn)索引看為0，那么高度為2的樹的最后一個(gè)節(jié)點(diǎn)的索引為2，類推高度為3的最后一個(gè)節(jié)點(diǎn)為6，滿足m = (m + 1) * 2。那么計(jì)算這個(gè)高度有什么好處呢，如上圖，如果一個(gè)樹有9個(gè)節(jié)點(diǎn)，那么我們構(gòu)造紅黑樹的時(shí)候，只要把前面3層的結(jié)點(diǎn)都設(shè)置為黑色，第四層的節(jié)點(diǎn)設(shè)置為紅色，則構(gòu)造完的樹，就是紅黑樹，滿足前面提到的紅黑樹的5個(gè)條件。而實(shí)現(xiàn)的關(guān)鍵就是找到要構(gòu)造樹的完全二叉樹的層數(shù)。值得注意的是完全二叉樹的層是從0開始計(jì)算的。
現(xiàn)在看這個(gè)函數(shù)應(yīng)該很容易懂
/** level是當(dāng)前樹的層數(shù)，從0開始* lo是子樹第一個(gè)元素的索引* hi是子樹的最后一個(gè)元素的索引* redLevel是上述紅節(jié)點(diǎn)所在的層數(shù)，從零開始的* it: 傳入的map的entries迭代器 * str: 如果不為空，則從流里讀取key-value * defaultVal：見名知意，不為空，則value都用這個(gè)值 */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 {//第一個(gè)索引大于最后的索引，說明構(gòu)造完成if (hi < lo) return null;//中間位置int mid = (lo + hi) >>> 1;Entry<K,V> left = null;if (lo < mid)//遞歸構(gòu)造左邊的節(jié)點(diǎn)left = buildFromSorted(level+1, lo, mid - 1, redLevel,it, str, defaultVal);// 構(gòu)造key，valueK key;V value;if (it != null) {if (defaultVal==null) {Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();key = (K)entry.getKey();value = (V)entry.getValue();} else {key = (K)it.next();value = defaultVal;}} else { // use streamkey = (K) str.readObject();value = (defaultVal != null ? defaultVal : (V) str.readObject());}Entry<K,V> middle = new Entry<>(key, value, null);//設(shè)置紅節(jié)點(diǎn)if (level == redLevel)middle.color = RED;//如果存在左節(jié)點(diǎn)，那么讓左節(jié)點(diǎn)和該節(jié)點(diǎn)產(chǎn)生關(guān)系，只要不是葉子結(jié)點(diǎn)，都存在左節(jié)點(diǎn)if (left != null) {middle.left = left;left.parent = middle;}//遞歸地構(gòu)造右結(jié)點(diǎn)if (mid < hi) {Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,it, str, defaultVal);middle.right = right;right.parent = middle;}return middle;}5.TreeMap的重要方法
get方法
public V get(Object key) {Entry<K,V> p = getEntry(key);return (p==null ? null : p.value);} final Entry<K,V> getEntry(Object key) {// 如果有比較器，那么通過調(diào)用比較器來比較key的方法if (comparator != null)return getEntryUsingComparator(key);if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;//二叉樹的查找方法Entry<K,V> p = root;while (p != null) {int cmp = k.compareTo(p.key);if (cmp < 0)p = p.left;else if (cmp > 0)p = p.right;elsereturn p;}return null;}getEntryUsingComparator方法用的是構(gòu)造器的方法，換湯不換藥，就不介紹了。
put方法
//put方法實(shí)現(xiàn)了如果存在key，放回舊值，如果找不到就放進(jìn)去，返回nullpublic V put(K key, V value) {Entry<K,V> t = root;if (t == null) {//類型檢查compare(key, key); root = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;//存在比較器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;elsereturn t.setValue(value);} while (t != null);}//不存在比較器else {//這里也可以看到TreeMap的key在沒有構(gòu)造器的情況下不能為nullif (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")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;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;//對(duì)紅黑樹進(jìn)行修復(fù)fixAfterInsertion(e);size++;modCount++;return null;}put的邏輯非常清晰，我們知道每次修改樹的結(jié)構(gòu)都會(huì)破壞紅黑樹的性質(zhì)。
fixAfterInsertion對(duì)插入結(jié)點(diǎn)后的紅黑樹進(jìn)行修復(fù)，維護(hù)其平衡，我們接著來看看它是如何實(shí)現(xiàn)的（在繼續(xù)看之前，建議大家了解一下左旋轉(zhuǎn)和右旋轉(zhuǎn)的操作）。
這里就稍微解釋一下：
第一步：找到插入的位置。
第二步：將插入的節(jié)點(diǎn)著色為”紅色”。
為什么著色成紅色，而不是黑色呢？為什么呢？在回答之前，我們需要重新溫習(xí)一下紅黑樹的特性：
- (1) 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。
- (2) 根節(jié)點(diǎn)是黑色。
- (3) 每個(gè)葉子節(jié)點(diǎn)是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空的葉子節(jié)點(diǎn)！]
- (4) 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
(5) 從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
將插入的節(jié)點(diǎn)著色為紅色，不會(huì)違背”特性(5)”！少違背一條特性，就意味著我們需要處理的情況越少。接下來，就要努力的讓這棵樹滿足其它性質(zhì)即可；滿足了的話，它就又是一顆紅黑樹了。
第三步: 通過一系列的旋轉(zhuǎn)或著色等操作，使之重新成為一顆紅黑樹。
只有對(duì)于”特性(4)”，是有可能違背的！
那接下來，想辦法使之”滿足特性(4)”，就可以將樹重新構(gòu)造成紅黑樹了。
看代碼的時(shí)候，建議一邊對(duì)著這個(gè)博客去看：
紅黑樹的添加
至于左旋轉(zhuǎn)和右旋轉(zhuǎn)就不拿出來分析了。有點(diǎn)抽象，不好說。
remove方法
public V remove(Object key) { //獲取Entry Entry<K,V> p = getEntry(key); if (p == null) return null; V oldValue = p.value; //刪除的關(guān)鍵方法 deleteEntry(p); return oldValue; }在看deleteEntry之前，我們先來看一下successor方法，為其做準(zhǔn)備，
這個(gè)方法的作用是根據(jù)key找到比一個(gè)最小的比t(參數(shù))的key大的Entry。
刪除的思路是兩步，刪了然后再修復(fù)
private void deleteEntry(Entry<K,V> p) {modCount++;size--;//p的左右子樹都不為空，找到右子樹中最小的結(jié)點(diǎn)，將key、value賦給p，然后p指向后繼結(jié)點(diǎn)//轉(zhuǎn)化成了下面的情況if (p.left != null && p.right != null) {Entry<K,V> s = successor(p);p.key = s.key;p.value = s.value;p = s;} // 存在一個(gè)孩子或者沒有孩子的情況//直接刪除就好了Entry<K,V> replacement = (p.left != null ? p.left : p.right);if (replacement != null) {// Link replacement to parentreplacement.parent = p.parent;if (p.parent == null)root = replacement;else if (p == p.parent.left)p.parent.left = replacement;elsep.parent.right = replacement;// Null out links so they are OK to use by fixAfterDeletion.p.left = p.right = p.parent = null;// Fix replacementif (p.color == BLACK)fixAfterDeletion(replacement);} else if (p.parent == null) { // return if we are the only node.root = null;} else { // No children. Use self as phantom replacement and unlink.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;}}}fixAfterDeletion的源碼，還是和上面添加操作一樣，對(duì)著紅黑樹的原理看會(huì)比較簡(jiǎn)單：
下面就不做解釋了
總結(jié)： TreeMap這一章對(duì)于數(shù)據(jù)結(jié)構(gòu)的要求比較高，因?yàn)橛昧思t黑樹，比HashMap的實(shí)現(xiàn)多了排序的功能，所以他的操作都是十分復(fù)雜的，希望大家能夠靜下心來，多去了解一下為什么要這么做。
總結(jié)
以上是生活随笔為你收集整理的容器源码分析之TreeMap(十)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 容器源码解析之LinkedHashMap
- 下一篇： 容器源码分析之HashSet (三)