1 TreeMap
1.1 底層結(jié)構(gòu)
TreeMap底層使用的數(shù)據(jù)結(jié)構(gòu)是紅黑樹
2 四個(gè)關(guān)注點(diǎn)
| 關(guān)注點(diǎn) | 結(jié)論 |
|---|---|
| TreeMap是否允許空 | Key和Value都允許為空 |
| TreeMap是否允許重復(fù)數(shù)據(jù) | Key重復(fù)會(huì)覆蓋桩撮，Value允許重復(fù) |
| TreeMap是否有序 | 無序 |
| TreeMap是否線程安全 | 非線程安全 |
3 TreeMap源碼解析
3.1 類的繼承關(guān)系
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
說明：繼承了抽象類AbstractMap，AbstractMap實(shí)現(xiàn)了Map接口扼菠，實(shí)現(xiàn)了部分方法。不能進(jìn)行實(shí)例化堵幽，實(shí)現(xiàn)了NavigableMap,Cloneable,Serializable接口玲献，其中NavigableMap是繼承自SortedMap的接口，定義了一系列規(guī)范倔既。
3.2 類的屬性
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
// 比較器呢蔫，用于控制Map中的元素順序
private final Comparator<? super K> comparator;
// 根節(jié)點(diǎn)
private transient Entry<K,V> root;
// 樹中結(jié)點(diǎn)個(gè)數(shù)
private transient int size = 0;
// 對樹進(jìn)行結(jié)構(gòu)性修改的次數(shù)
private transient int modCount = 0;
}
說明：重點(diǎn)是比較器Comparator切心，此接口實(shí)現(xiàn)了對插入元素進(jìn)行排序。
3.3 類的構(gòu)造函數(shù)
1. TreeMap()型構(gòu)造函數(shù)
public TreeMap() {
comparator = null;
}
2. TreeMap(Comparator<? super K>)型構(gòu)造函數(shù)
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
說明：用戶自定義了比較器片吊，可以按照用戶的邏輯進(jìn)行比較绽昏，確定元素的訪問順序。
3. TreeMap(Map<? extends K, ? extends V>)型構(gòu)造函數(shù)
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();
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;
}
}
super.putAll(map);
}
4. TreeMap(SortedMap<K, ? extends V>)型構(gòu)造函數(shù)
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) {
}
}
說明：傳入SortedMap型參數(shù)俏脊，實(shí)現(xiàn)SortedMap接口的類都會(huì)實(shí)現(xiàn)comparator方法而涉，用于返回比較器。
3.4 核心函數(shù)分析
1. put函數(shù)
public V put(K key, V value) {
// 記錄根節(jié)點(diǎn)
Entry<K,V> t = root;
// 根節(jié)點(diǎn)為空
if (t == null) {
// 比較key
compare(key, key); // type (and possibly null) check
// 新生根節(jié)點(diǎn)
root = new Entry<>(key, value, null);
// 大小加1
size = 1;
// 修改次數(shù)加1
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 獲取比較器
Comparator<? super K> cpr = comparator;
// 比較器不為空
if (cpr != null) {
// 找到元素合適的插入位置
do {
// parent賦值
parent = t;
// 比較key與元素的key值联予，在Comparator類的compare方法中可以實(shí)現(xiàn)我們自己的比較邏輯
cmp = cpr.compare(key, t.key);
// 小于結(jié)點(diǎn)key值啼县，向左子樹查找
if (cmp < 0)
t = t.left;
// 大于結(jié)點(diǎn)key值，向右子樹查找
else if (cmp > 0)
t = t.right;
// 表示相等沸久，直接更新結(jié)點(diǎn)的值
else
return t.setValue(value);
} while (t != null);
}
// 比較器為空
else {
// key為空季眷，拋出異常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 取得K實(shí)現(xiàn)的比較器
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);
}
// 新生一個(gè)結(jié)點(diǎn)
Entry<K,V> e = new Entry<>(key, value, parent);
// 根據(jù)比較結(jié)果決定存為左結(jié)點(diǎn)或右結(jié)點(diǎn)
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 插入后進(jìn)行修正
fixAfterInsertion(e);
// 大小加1
size++;
// 進(jìn)行了結(jié)構(gòu)性修改
modCount++;
return null;
}
說明：插入一個(gè)元素時(shí)，若用戶自定義比較器卷胯，則會(huì)按照用戶自定義的邏輯確定元素的插入位置子刮，否則，將會(huì)使用K自身實(shí)現(xiàn)的比較器確定插入位置。
2. getEntry函數(shù)
final Entry<K,V> getEntry(Object key) {
// 判斷比較器是否為空
if (comparator != null)
// 根據(jù)自定義的比較器來返回結(jié)果
return getEntryUsingComparator(key);
// 比較器為空
// key為空挺峡，拋出異常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 取得K自身實(shí)現(xiàn)了比較接口
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
// 根據(jù)Comparable接口的compareTo函數(shù)來查找元素
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;
}
說明：當(dāng)我們調(diào)用get函數(shù)時(shí)葵孤，實(shí)際上是委托g(shù)etEntry函數(shù)獲取元素，對于用戶自定義實(shí)現(xiàn)的Comparator比較器而言橱赠，是使用getEntryUsingComparator函數(shù)來完成獲取邏輯尤仍。
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
// 向下轉(zhuǎn)型
K k = (K) key;
// 取得比較器
Comparator<? super K> cpr = comparator;
// 比較器不為空
if (cpr != null) {
Entry<K,V> p = root;
// 開始遍歷樹節(jié)點(diǎn)找到對應(yīng)的結(jié)點(diǎn)
while (p != null) {
int cmp = cpr.compare(k, p.key);
// 小于結(jié)點(diǎn)key值，向左子樹查找
if (cmp < 0)
p = p.left;
// 大于結(jié)點(diǎn)key值狭姨，向右子樹查找
else if (cmp > 0)
p = p.right;
// 相等宰啦，找到，直接返回
else
return p;
}
}
return null;
}
說明：會(huì)根據(jù)用戶定義在compare函數(shù)里面的邏輯進(jìn)行元素的查找饼拍。
3. deleteEntry函數(shù)
private void deleteEntry(Entry<K,V> p) {
// 結(jié)構(gòu)性修改
modCount++;
// 大小減1
size--;
// p的左右子結(jié)點(diǎn)均不為空
if (p.left != null && p.right != null) {
// 找到p結(jié)點(diǎn)的后繼
Entry<K,V> s = successor(p);
// 將p的值用其后繼結(jié)點(diǎn)的key-value替換赡模，并且用s指向其后繼
p.key = s.key;
p.value = s.value;
p = s;
}
// 開始進(jìn)行修正，具體的修正過程我們會(huì)在之后的數(shù)據(jù)結(jié)構(gòu)專區(qū)進(jìn)行講解
// 現(xiàn)在可以看成是為了保持紅黑樹的特性师抄，提高性能
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
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;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (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;
}
}
}
說明：deleteEntry函數(shù)會(huì)在remove函數(shù)中被調(diào)用漓柑，它完成了移除元素的主要工作，刪除該結(jié)點(diǎn)后會(huì)對紅黑樹進(jìn)行修正叨吮，此部分內(nèi)容以后會(huì)詳細(xì)講解辆布，同時(shí)，在此函數(shù)中需要調(diào)用successor函數(shù)挤安，即找到該結(jié)點(diǎn)的后繼結(jié)點(diǎn)谚殊。具體函數(shù)代碼如下
// 找到后繼
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
// t為null丧鸯，直接返回null
if (t == null)
return null;
// 右孩子不為空
else if (t.right != null) {
// 找到右孩子的最底層的左孩子蛤铜，返回
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else { // 右孩子為空
// 保存t的父節(jié)點(diǎn)
Entry<K,V> p = t.parent;
// 保存t結(jié)點(diǎn)
Entry<K,V> ch = t;
// 進(jìn)行回溯，找到后繼丛肢，直到p == null || ch != p.right
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
說明：當(dāng)結(jié)點(diǎn)的右子樹為空的時(shí)候围肥，進(jìn)行回溯可以找到該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。
