前言
上篇文章講解了JDK1.7中的HashMap源碼, 主要采用數(shù)組+鏈表來(lái)實(shí)現(xiàn), 根據(jù)元素的hash計(jì)算出來(lái)的下標(biāo)相同時(shí), 也就是發(fā)生hash沖突的時(shí)候, 就會(huì)把這些元素以鏈表的形式存放在數(shù)組中, 當(dāng)數(shù)組比較小, 發(fā)生hash沖突比較頻繁時(shí), 數(shù)組中鏈表就比較長(zhǎng), 這樣查找的效率就比較低.
JDK1.8中的HashMap主要對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化, 引入了紅黑樹(shù), 當(dāng)鏈表長(zhǎng)度大于8時(shí)把鏈表轉(zhuǎn)換成紅黑樹(shù), 紅黑樹(shù)的操作效率遠(yuǎn)高于鏈表, 這樣就提高了HashMap的效率.
備注: 本人不是計(jì)算機(jī)專(zhuān)業(yè)出身, 對(duì)于紅黑樹(shù)也是一知半解, 感興趣的可以參考這篇文章, 詳細(xì)介紹了紅黑樹(shù)的特性以及一些基本操作.
源碼
JDK1.8源碼中增加了這兩個(gè)參數(shù):
//當(dāng)鏈表長(zhǎng)度大于8時(shí), 將鏈表轉(zhuǎn)換成紅黑樹(shù)
static final int TREEIFY_THRESHOLD = 8;
//當(dāng)紅黑樹(shù)長(zhǎng)度小于等于6時(shí), 將紅黑樹(shù)轉(zhuǎn)換成鏈表
static final int UNTREEIFY_THRESHOLD = 6;
構(gòu)造函數(shù)及其他參數(shù)基本沒(méi)變, 不再細(xì)說(shuō), 下面對(duì)一些優(yōu)化點(diǎn)具體分析.
- hash值計(jì)算數(shù)組下標(biāo)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這里通過(guò)key的hashcode高16位異或低16位來(lái)計(jì)算hash值, 這樣讓hashcode的高位低位都參與到hash計(jì)算上, 減少了hash沖突.
然后通過(guò)hash&(length-1)來(lái)計(jì)算數(shù)組下標(biāo), 我們知道數(shù)組長(zhǎng)度都是2的N次方, hash&(length-1)相當(dāng)于hash%length(前者按位與運(yùn)算效率更高), 這樣元素分布更加均勻.
- Node節(jié)點(diǎn)
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
數(shù)組中每一個(gè)元素都是Node, 有hash, key, value, next四個(gè)屬性, 與JDK1.7中的HashMapEntry一樣.
- put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//onlyIfAbsent: 如果HashMap中已存在該元素, true:不改變?cè)? false: 替換原值
//evict: 插入元素之后是否刪除
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//數(shù)組為空, 通過(guò)resize初始化數(shù)組
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通過(guò)hash值計(jì)算數(shù)組下標(biāo), 如果tab[i]元素為空, 新建一個(gè)元素放在該位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//如果tab[i]元素不為空, 說(shuō)明發(fā)生了hash碰撞
Node<K,V> e; K k;
//如果tab[i]元素的 hash key與插入元素相同, 則直接替換
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果tab[i]元素是紅黑樹(shù), 就在紅黑樹(shù)上插入該元素
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果tab[i]元素是鏈表, 遍歷鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//遍歷到鏈表尾部也沒(méi)找到hash和key相同的元素, 則創(chuàng)建一個(gè)節(jié)點(diǎn)放到鏈表尾部
p.next = newNode(hash, key, value, null);
//如果鏈表長(zhǎng)度大于等于8, 就把鏈表轉(zhuǎn)換成紅黑樹(shù)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//找到hash和key相同的元素, 退出
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果找到hash和key相同的元素
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent 為false或舊值為空, 則替換舊值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果容量超過(guò)最大容量, 需要擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
JDK1.8中put操作與JDK1.7中put操作大致相同, 區(qū)別就是發(fā)生hash碰撞之后, 先判斷對(duì)應(yīng)位置是鏈表還是紅黑樹(shù), 是紅黑樹(shù)就進(jìn)行紅黑樹(shù)的插入操作, 鏈表的話(huà)遍歷鏈表插入, 最后再判斷鏈表長(zhǎng)度大于等于8時(shí)轉(zhuǎn)換成紅黑樹(shù).
- resize
緊接著來(lái)看下數(shù)組初始化及擴(kuò)容的方法resize:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//老數(shù)組容量
int oldThr = threshold;//老數(shù)組擴(kuò)容臨界值
int newCap, newThr = 0;//新數(shù)組容量及擴(kuò)容臨界值
//老數(shù)組容量不為空, 說(shuō)明進(jìn)行擴(kuò)容操作
if (oldCap > 0) {
//如果老數(shù)組容量超過(guò)最大值, 不再擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//當(dāng)老數(shù)組容量大于16時(shí), 數(shù)組容量和臨界值都擴(kuò)展為2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果老數(shù)組容量為0, 擴(kuò)容臨界值不為0, 則臨界值賦給新數(shù)組容量
else if (oldThr > 0)
newCap = oldThr;
else { //如果老數(shù)組容量和臨界值都為0, 則新數(shù)組容量為16, 臨界值為16*0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//再次判斷新數(shù)組擴(kuò)容臨界值是否為0, 為0時(shí)重新計(jì)算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//創(chuàng)建新容量數(shù)組
table = newTab;
// 老數(shù)組不為空, 則遍歷老數(shù)組上每一個(gè)元素, 遷移到新數(shù)組中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//oldTab[j]上只有一個(gè)元素時(shí), 重新計(jì)算在新數(shù)組中的下標(biāo), 放到新數(shù)組中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果當(dāng)前元素是紅黑樹(shù), 執(zhí)行split移動(dòng)到新數(shù)組中
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 如果當(dāng)前元素是單鏈表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//循環(huán)遷移鏈表上的每一個(gè)元素, 這里把之前的一個(gè)鏈表分成了兩個(gè)鏈表, 一個(gè)高位鏈表, 一個(gè)低位鏈表
do {
next = e.next;
//如果((e.hash & oldCap) == 0, 就把當(dāng)前元素放到低位鏈表中
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//如果((e.hash & oldCap) == 1, 就把當(dāng)前元素放到高位鏈表中
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//低位鏈表不為空的話(huà), 把低位鏈表放到新數(shù)組當(dāng)前位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//高位鏈表不為空的話(huà), 把高位鏈表放到新數(shù)組j + oldCap上
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
簡(jiǎn)單總結(jié)一下, 先判斷老數(shù)組容量, 為空時(shí)重新設(shè)置容量和擴(kuò)容臨界值, 初始化數(shù)組, 如果不為空就對(duì)數(shù)組容量和臨界值擴(kuò)大2倍, 然后把老數(shù)組中所有元素遷移到新數(shù)組中, 遷移時(shí)先判斷數(shù)組上元素是紅黑樹(shù)還是鏈表, 紅黑樹(shù)就進(jìn)行紅黑樹(shù)的分離操作, 鏈表的話(huà), 把一個(gè)鏈表分成兩個(gè)鏈表, 放到新數(shù)組不同位置上.
這里把鏈表分成兩個(gè)鏈表的判斷邏輯是e.hash & oldCap是否等于0, 我們知道計(jì)算數(shù)組下標(biāo)是通過(guò)e.hash & (oldCap-1), 這個(gè)鏈表上所有元素這個(gè)下標(biāo)值是一樣的, 但是當(dāng)數(shù)組容量擴(kuò)充為2倍時(shí), e.hash & oldCap那一位就起了關(guān)鍵作用.
舉個(gè)例子, 數(shù)組初始容量是16,有兩個(gè)hash值5和21發(fā)生了碰撞, 放在一個(gè)鏈表上.
5&(16-1): 0000 0101&0000 1111=0000 0101=5
21&(16-1):0001 0101&0000 1111=0000 0101=5
當(dāng)數(shù)組擴(kuò)容為32時(shí), 就不會(huì)發(fā)生hash碰撞了
5&(32-1): 0000 0101&0001 1111=0000 0101=5
21&(32-1):0001 0101&0001 1111=0001 0101=21
通過(guò)例子可以看出, 數(shù)組擴(kuò)充為2倍時(shí), 關(guān)鍵看e.hash & oldCap那一位, 要么是0, 要么是1, 通過(guò)這一位就可以判斷在新數(shù)組中的位置, 0的話(huà)位置不變, 1的話(huà)位置增加了原數(shù)組容量.
這里介紹下數(shù)組遷移時(shí)JDK1.7與1.8的一點(diǎn)區(qū)別:
1.7中是對(duì)鏈表上每一個(gè)元素通過(guò)e.hash & (newCap-1)計(jì)算在新數(shù)組中的下標(biāo), 然后放到新數(shù)組對(duì)應(yīng)下標(biāo)中, 發(fā)生hash沖突后, 新加入的元素會(huì)放到單鏈表頭部, 這樣遷移之后元素發(fā)生了倒置.
1.8中數(shù)組遷移時(shí)(暫不討論紅黑樹(shù)), 根據(jù)e.hash & oldCap等于0或1把一個(gè)單鏈表分成了兩個(gè)單鏈表, 最后放到新數(shù)組不同位置上. 一方面計(jì)算效率更高, 另一方面不會(huì)發(fā)生元素倒置.
- get
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//根據(jù)key的hash值計(jì)算數(shù)組下標(biāo), 獲取數(shù)組對(duì)應(yīng)位置上的首個(gè)元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果首個(gè)元素hash和key與目標(biāo)值相等, 則返回
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果首個(gè)元素與目標(biāo)元素不等, 且有后續(xù)元素, 判斷是否是紅黑樹(shù)
if ((e = first.next) != null) {
//如果是紅黑樹(shù), 在紅黑樹(shù)中查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果是鏈表, 循環(huán)鏈表查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get的方法比較簡(jiǎn)單, 根據(jù)hash值計(jì)算出坐標(biāo)之后, 再判斷對(duì)應(yīng)位置元素, 如果是紅黑樹(shù)就在紅黑樹(shù)中查找, 如果是鏈表, 就循環(huán)鏈表查找.
- remove
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//上面部分跟getNode方法一樣, 就是取出hash和key都相等的元素, 如果不為空, 且value與要?jiǎng)h除的元素相等
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果找到的元素是紅黑樹(shù), 就執(zhí)行紅黑樹(shù)的刪除操作
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//如果找到的元素是鏈表頭部, 刪除該元素, 把下一個(gè)元素放到鏈表頭部
else if (node == p)
tab[index] = node.next;
else//
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
remove方法, 根據(jù)hash值計(jì)算出數(shù)組下標(biāo)之后, 判斷對(duì)應(yīng)元素, 是紅黑樹(shù)就從紅黑樹(shù)種查找目標(biāo)元素并刪除, 如果是鏈表, 就遍歷鏈表查找元素并刪除.
- 紅黑樹(shù)
紅黑樹(shù)是整個(gè)代碼中最難理解的一部分, 如果你看懂了它的原理和算法, 就很好理解了.這里我簡(jiǎn)單分析下, 有些細(xì)節(jié)也沒(méi)看太懂.
- 屬性
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
TreeNode<K,V> left;//當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)
TreeNode<K,V> right;//當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)
TreeNode<K,V> prev; // 當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
boolean red;//當(dāng)前節(jié)點(diǎn)的顏色: 紅/黑
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
這里TreeNode繼承的是LinkedHashMap.Entry, 我們知道HashMap的Node是單鏈表結(jié)構(gòu), 而LinkedHashMap.Entry是環(huán)形鏈表結(jié)構(gòu), 所以TreeNode節(jié)點(diǎn)既有樹(shù)狀結(jié)構(gòu)又有雙鏈表結(jié)構(gòu), 對(duì)紅黑樹(shù)進(jìn)行插入查找操作時(shí), 利用樹(shù)狀結(jié)構(gòu), 分離紅黑樹(shù)時(shí)又是利用鏈表結(jié)構(gòu).
- root
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
root: 查找當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn). 從該節(jié)點(diǎn)一直往上查找父節(jié)點(diǎn), 直到父節(jié)點(diǎn)為空, 即為根節(jié)點(diǎn).
- find
上面HashMap的getNode方法中, 如果元素是紅黑樹(shù)就通過(guò)紅黑樹(shù)的getTreeNode方法查找元素. 這里看下紅黑樹(shù)的getTreeNode方法.
final TreeNode<K,V> getTreeNode(int h, Object k) {
//找到當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn), 然后從根節(jié)點(diǎn)開(kāi)始往下查找
return ((parent != null) ? root() : this).find(h, k, null);
}
//從當(dāng)前節(jié)點(diǎn)開(kāi)始往下查找
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
//獲取當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)
TreeNode<K,V> pl = p.left, pr = p.right, q;
//當(dāng)前節(jié)點(diǎn)的hash大于目標(biāo)元素hash, 向左子節(jié)點(diǎn)查找
if ((ph = p.hash) > h)
p = pl;
////當(dāng)前節(jié)點(diǎn)的hash小于目標(biāo)元素hash, 向右子節(jié)點(diǎn)查找
else if (ph < h)
p = pr;
//如果當(dāng)前節(jié)點(diǎn)hash和key都與目標(biāo)元素相同, 返回當(dāng)前元素
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)//左子節(jié)點(diǎn)為空, 向右子節(jié)點(diǎn)查找
p = pr;
else if (pr == null)//右子節(jié)點(diǎn)為空, 向左子節(jié)點(diǎn)查找
p = pl;
//hash值相等, key不等
//如果目標(biāo)元素的key可比較且與當(dāng)前節(jié)點(diǎn)的key不等價(jià), 如果目標(biāo)元素key小于當(dāng)前節(jié)點(diǎn)key, 向左查找, 否則向右查找
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
//如果目標(biāo)key不可比較或者當(dāng)前節(jié)點(diǎn)key與目前key類(lèi)型不同, 向右子節(jié)點(diǎn)查找
else if ((q = pr.find(h, k, kc)) != null)
return q;
else//右子節(jié)點(diǎn)查不到再向左子節(jié)點(diǎn)查找
p = pl;
} while (p != null);
return null;
}
//比較k和x
static int compareComparables(Class<?> kc, Object k, Object x) {
//如果x為空或x的類(lèi)型不是kc, 返回0, 否則比較兩者, k<x返回負(fù)值, k>x返回正值
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
這段代碼根據(jù)二叉樹(shù)的性質(zhì), 小的在左, 大的在右. 先根據(jù)hash值向左查找或向右查找, hash值相等再根據(jù)key向左查找或向右查找, 依次向下查找, 直到找到hash和key都相等的節(jié)點(diǎn).
- putTreeVal
上面HashMap的putVal方法中, 如果數(shù)組上元素是紅黑樹(shù)就根據(jù)紅黑樹(shù)的putTreeVal方法查找.
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
//先找到當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn)
TreeNode<K,V> root = (parent != null) ? root() : this;
//從根節(jié)點(diǎn)向下查找
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)//向做插入
dir = -1;
else if (ph < h)//向右插入
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))//找到hash和key都相等的元素直接返回
return p;
//hash值相等但key不相等
//如果目標(biāo)Key不可比較或者當(dāng)前節(jié)點(diǎn)key與目標(biāo)key類(lèi)型不同
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
//先向左查找再向右查找, 如果找到則返回
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
//還沒(méi)找到, 因?yàn)槟繕?biāo)key與當(dāng)前節(jié)點(diǎn)key類(lèi)型不同無(wú)法比較, 則用另一種方式比較
dir = tieBreakOrder(k, pk);
}
//當(dāng)前節(jié)點(diǎn)保存到xp中
TreeNode<K,V> xp = p;
//dir<0且當(dāng)前節(jié)點(diǎn)左子節(jié)點(diǎn)為空, 則向左子節(jié)點(diǎn)插入新元素
//dir>0且當(dāng)前節(jié)點(diǎn)右子節(jié)點(diǎn)為空, 則向右子節(jié)點(diǎn)插入新元素
//否則, 左子節(jié)點(diǎn)或右子節(jié)點(diǎn)不為空, 則繼續(xù)向下查找待插入位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
//新建一個(gè)節(jié)點(diǎn)x
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)//新建節(jié)點(diǎn)成為當(dāng)前節(jié)點(diǎn)p的左子節(jié)點(diǎn)
xp.left = x;
else//新建節(jié)點(diǎn)成為當(dāng)前節(jié)點(diǎn)p的右子節(jié)點(diǎn)
xp.right = x;
//指定節(jié)點(diǎn)的prev和next, 由此可見(jiàn), 紅黑樹(shù)中既有樹(shù)狀關(guān)系也有雙鏈表關(guān)系
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//插入新元素之后紅黑樹(shù)的性質(zhì)可能打破, 需要進(jìn)行平衡操作, 最后把紅黑樹(shù)的根放到數(shù)組對(duì)應(yīng)位置
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
static int tieBreakOrder(Object a, Object b) {
int d;
//如果a,b為空, 或ab的類(lèi)名相同, 則通過(guò)System.identityHashCode比較
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
總結(jié)一下putTreeVal的大致流程, 從根部開(kāi)始, 根據(jù)hash值向左查找或向右查找, 如果hash相等key不等, 就比較key的hash值, 如果找到hash和key都相等的元素就直接返回當(dāng)前節(jié)點(diǎn), 未找到就新建一個(gè)元素作為左子節(jié)點(diǎn)或右子節(jié)點(diǎn), 插入元素后可能打破紅黑樹(shù)的性質(zhì), 需要進(jìn)行平衡操作, 平衡操作之后根部元素可能發(fā)生變化, 需要把根部節(jié)點(diǎn)放到數(shù)組對(duì)應(yīng)位置上.
balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x)平衡插入操作, 大致是通過(guò)左旋右旋, 對(duì)節(jié)點(diǎn)重新著色來(lái)修正紅黑樹(shù), 是它滿(mǎn)足紅黑樹(shù)的所有性質(zhì), 具體細(xì)節(jié)有興趣的可以研究下.
balanceInsertion平衡操作之后返回的是新的根節(jié)點(diǎn), 然后通過(guò)moveRootToFront, 把根節(jié)點(diǎn)放到數(shù)組對(duì)應(yīng)位置上, 簡(jiǎn)單看下:
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
//根據(jù)根節(jié)點(diǎn)hash值計(jì)算下標(biāo)
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//如果數(shù)組對(duì)應(yīng)位置上不是這個(gè)根節(jié)點(diǎn), 需要替換
if (root != first) {
Node<K,V> rn;
//將root放到數(shù)組對(duì)應(yīng)位置上
tab[index] = root;
TreeNode<K,V> rp = root.prev;
//改變r(jià)oot前后節(jié)點(diǎn)的指向
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;treeifytreeify
//改變數(shù)組對(duì)應(yīng)位置原節(jié)點(diǎn)與新的根節(jié)點(diǎn)的前后指向
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
- split
上面數(shù)組擴(kuò)容時(shí), 如果元素是紅黑樹(shù), 就通過(guò)split把紅黑樹(shù)分離.
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;//當(dāng)前節(jié)點(diǎn)
// 初始化兩個(gè)雙鏈表
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//這里利用紅黑樹(shù)節(jié)點(diǎn)的鏈表關(guān)系遍歷紅黑樹(shù)
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//通過(guò)e.hash & bit決定當(dāng)前元素放到哪個(gè)鏈表上
if ((e.hash & bit) == 0) {//放低位鏈表
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {//放高位鏈表
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
//低位鏈表長(zhǎng)度小于等于6, 雙鏈表轉(zhuǎn)換成單鏈表放到tab[index]上
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {//否則不轉(zhuǎn)換放到tab[index]上
tab[index] = loHead;
//hiHead != null時(shí)把loHead轉(zhuǎn)換成紅黑樹(shù), hiHead =null說(shuō)明原來(lái)的紅黑樹(shù)沒(méi)有分離, 還是一顆紅黑樹(shù)
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
擴(kuò)容時(shí)紅黑樹(shù)的分離過(guò)程跟鏈表的分離過(guò)程有點(diǎn)類(lèi)似, 先初始化兩個(gè)雙鏈表, 然后利用hash&老數(shù)組length, 如果是0, 放到低位鏈表中, 如果是1, 放到高位鏈表中. 最后判斷鏈表長(zhǎng)度, 小于等于6時(shí)把雙鏈表轉(zhuǎn)換成單鏈表存儲(chǔ), 否則, 判斷紅黑樹(shù)是否分離, 未分離, 還是一顆紅黑樹(shù), 經(jīng)過(guò)分離的話(huà)再把分離出來(lái)的鏈表轉(zhuǎn)換成紅黑樹(shù)存儲(chǔ), 低位鏈表存儲(chǔ)到相同位置, 高位鏈表存儲(chǔ)到當(dāng)前位置+老數(shù)組長(zhǎng)度.
下面看下treeify和untreeify這兩個(gè)方法:
- treeify
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//根據(jù)TreeNode的鏈表關(guān)系遍歷
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//鏈表頭元素成為紅黑樹(shù)的根節(jié)點(diǎn)
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
//左子節(jié)點(diǎn)或右子節(jié)點(diǎn)為空時(shí), 插入新元素
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//插入之后平衡紅黑樹(shù), 退出, 繼續(xù)插入下一個(gè)元素
root = balanceInsertion(root, x);
break;
}
}
}
}
//所有元素插入紅黑樹(shù)之后再把根節(jié)點(diǎn)替換到數(shù)組對(duì)應(yīng)位置
moveRootToFront(tab, root);
}
treeify: 把雙鏈表轉(zhuǎn)換成紅黑樹(shù), 鏈表頭元素成為根節(jié)點(diǎn), 后面的元素根據(jù)hash值判斷成為當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)或者右子節(jié)點(diǎn), 插入之后平衡紅黑樹(shù), 等鏈表上所有元素插入紅黑樹(shù)之后替換數(shù)組上的根節(jié)點(diǎn).
- untreeify
final Node<K,V> untreeify(HashMap<K,V> map) {
//初始化鏈表頭尾元素
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
//把當(dāng)前的TreeNode轉(zhuǎn)換成普通的Node, next為null
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
untreeify: 把每一個(gè)TreeNode節(jié)點(diǎn)轉(zhuǎn)換成普通的節(jié)點(diǎn), 組成新的單鏈表, 最終返回單鏈表頭元素.
還有其他幾個(gè)方法, 左旋rotateLeft, 右旋rotateRight, 插入平衡balanceInsertion, 刪除平衡balanceDeletion這些方法具體細(xì)節(jié)我就不分析了(細(xì)節(jié)太多太復(fù)雜, 沒(méi)看完), 主要是在紅黑樹(shù)插入元素或刪除元素之后通過(guò)進(jìn)行的操作來(lái)保證紅黑樹(shù)的性質(zhì).
