疑問：
1)解決hash沖突的幾種方式
2)Map中的Entry根據(jù)key和value向上和向上排序
HashMap是基于數(shù)組和鏈表來實(shí)現(xiàn)的,在查詢和插入商膊、刪除上都有相當(dāng)快的速度,
因?yàn)樗峭ㄟ^計算散列碼來決定存儲位置的。
HashMap中主要是通過key的hashcode來計算hash值的,如果存儲的對象多了,
可能會出現(xiàn)相同的hashcode值,也就是所謂的hash沖突,解決hash沖突的辦法有很多,
而hashMap則是通過鏈表來解決的理肺。
hashmap中hash值不同的放入到數(shù)組中,稱為hash數(shù)組,數(shù)組中的元素是鏈表的頭節(jié)點(diǎn);
hash相同的則插入到對應(yīng)的鏈表的尾部
具體的結(jié)構(gòu),jdk1.8中,hashmap內(nèi)部維護(hù)了一個Node的實(shí)體類,用于儲存節(jié)點(diǎn)的信息,
包括key猜嘱、hash值泌辫、value值以及指向下一個節(jié)點(diǎn)的引用next。
這個Node類繼承于Map的Enrty的內(nèi)部類,所以具有獲取key,value,以及替換舊值的
作用,此外Map中的Entry還可以進(jìn)行比對key以及value的比較。
hash數(shù)組則是一個Node數(shù)組,數(shù)組每一個元素都是Node鏈表的頭結(jié)點(diǎn),
特點(diǎn)：
1)插入和刪除移動速度都很快
2)線程不安全
3)數(shù)組長度達(dá)到64 鏈表長度達(dá)到8 就會轉(zhuǎn)變?yōu)榧t黑樹
HashMap是一個散列表,通過鍵值對的形式對元素進(jìn)行存儲,HashMap是線程不安全的,key-value都是可以為null的,但是元素是無序的,影響HashMap的主要兩個參數(shù)是初始容量.加載因子
容量是哈希表中桶的數(shù)量,加載因子是哈希表在其容量自動增加之前可以達(dá)到的一種尺度,當(dāng)哈希表中的桶數(shù)量超出了加載因子與當(dāng)前容量的乘積時,就會進(jìn)行擴(kuò)容操作
HashMap整體是一個數(shù)組,不過數(shù)組的每一項(xiàng)都是由一個單鏈表組成,下標(biāo)由hash值構(gòu)成,在jdk8中,當(dāng)數(shù)組長度達(dá)到64并且單鏈表的長度達(dá)到8之后,鏈表會轉(zhuǎn)化成紅黑樹的結(jié)構(gòu),這時的HashMap則變成了數(shù)組+紅黑樹的結(jié)構(gòu)
HashMap繼承于Map,我們先從HashMap的Node開始,static class Node<K,V> implements Map.Entry<K,V>,Node實(shí)現(xiàn)了Map中的Entry接口,我們來看Entry中的抽象方法
getKey()獲取當(dāng)前節(jié)點(diǎn)的key值
getValue()獲取當(dāng)前節(jié)點(diǎn)的Value
setValue()為當(dāng)前節(jié)點(diǎn)的value值進(jìn)行賦值操作
comparingByKey()通過keyzhi比較當(dāng)前節(jié)點(diǎn)與指定節(jié)點(diǎn)的大小,用來進(jìn)行排序操作
comparingByValue()通過value值比較當(dāng)前節(jié)點(diǎn)與指定節(jié)點(diǎn)的大小,用來進(jìn)行排序操作
comparingByKey(Comparator<? super K> cmp)使用自定義的比較器通過key值來比較當(dāng)前節(jié)點(diǎn)與指定節(jié)點(diǎn)的大小 用來進(jìn)行排序操作
comparingByValue(Comparator<? super K> cmp)使用自定義的比較器通過value值來比較當(dāng)前節(jié)點(diǎn)與指定節(jié)點(diǎn)的大小 用來進(jìn)行排序操作
Node中有幾個成員變量和重寫的方法
final int hash不可變常量 hash
final K key不可變常量key
V value變量value
Node<K,V> next變量下一節(jié)點(diǎn)
構(gòu)造器
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
jdk1.8之后,HashMap引入了紅黑樹,所以這里同樣需要樹節(jié)點(diǎn)TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V>
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V>
TreeNode最終繼承于HashMap.Node,且為final類型不可被繼承.
TreeNode parent父節(jié)點(diǎn)
TreeNode left左子葉節(jié)點(diǎn)
TreeNode right右子葉節(jié)點(diǎn)
TreeNode prev前一節(jié)點(diǎn)
下面我們來看HashMap中的方法
構(gòu)造器
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
第一個構(gòu)造器,入?yún)橹付ǔ跏既萘亢图虞d因子,并計算擴(kuò)容閥值threshold,默認(rèn)為容量*加載因子即threshold = 16,當(dāng)HashMap中的總元素數(shù)量達(dá)到這個閥值時,會通過resize()進(jìn)行擴(kuò)容操作
第二個構(gòu)造器,入?yún)橹付ǔ跏杖萘?默認(rèn)加載因子為0.75f
第三個構(gòu)造器,只是設(shè)置了默認(rèn)的加載因子
第四個構(gòu)造器,入?yún)橐粋€map集合,通過putMapEntries加入到當(dāng)前集合中,并設(shè)置加載因子為默認(rèn)值.
put
// table 為儲存Node的數(shù)組,即HashMap真正存儲元素的數(shù)組
transient Node<K,V>[] table;
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put()會直接調(diào)用putVal(),在putVal()中會,初始化幾個變量,這里暫且不管,往下看判斷體, 將數(shù)組table賦值給tab 并檢測當(dāng)前數(shù)組是否是空數(shù)組 如果當(dāng)前數(shù)組是空數(shù)組的話,則通過擴(kuò)容方法resize()獲取一個數(shù)組,并計算數(shù)組的長度,賦值給n,
HashMap#resize():
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
開始同樣現(xiàn)將table賦值給oldTab,然后計算出當(dāng)前數(shù)組的容量,獲取到當(dāng)前數(shù)組的擴(kuò)容閥值,并初始化新數(shù)組的容量和擴(kuò)容閥值哩俭。
第一個if判斷語句,判斷當(dāng)前數(shù)組的容量是否大于0,在我們創(chuàng)建完HashMap對象之后,并沒有直接的創(chuàng)建Node[],所以這里不會進(jìn)入判斷體,
然后進(jìn)入else if中,當(dāng)前數(shù)組的擴(kuò)容閥值為16,會將當(dāng)前的擴(kuò)容閥值賦值給newCap作為新數(shù)組的總?cè)萘?
繼續(xù)往下看下一個if,此時的newThr == 0,進(jìn)入判斷體,首先根據(jù)加載因子loadFactor和新數(shù)組容量newCap得出新數(shù)組的擴(kuò)容閥值，然后在判斷要不要使用這個擴(kuò)容閥值:
static final int MAXIMUM_CAPACITY = 1 << 30;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
newCap = 16
ft = 12
MAXIMUM_CAPACITY = 1 * 2^30
所以條件成立,newThr = ft = 12
因此到這里可以小結(jié)一下:這里的判斷是為了計算出新數(shù)組的容量和擴(kuò)容閥值
繼續(xù)往下看,將得到的擴(kuò)容閥值賦值給原擴(kuò)容閥值threshold,并創(chuàng)建一個容量為newCap的Node[],將新數(shù)組賦值給原始數(shù)組table,前面有說oldTab = null,所以判斷體就不會進(jìn)入了,直接返回newTab;
回到putVal(),我們通過resize()獲取到了一個新的數(shù)組,并獲取到其長度賦值給n,n = 12;
繼續(xù)下一個判斷,通過n-1與hash的與運(yùn)算獲取到一個數(shù)組的下標(biāo)值,因?yàn)榇藭r的數(shù)組是空數(shù)組,所以此時的該下標(biāo)所對應(yīng)的node節(jié)點(diǎn)為null,所以會進(jìn)入到判斷體.根據(jù)hash蹄殃、key携茂、value創(chuàng)建一個新的node節(jié)點(diǎn),并放入當(dāng)前數(shù)組的該下標(biāo)中,最后修改次數(shù)+1,元素數(shù)量size+1,并判斷是否大于擴(kuò)容閥值,如果大于則通過resize()進(jìn)行擴(kuò)容操作
倘若這里需要進(jìn)行擴(kuò)容操作,我們進(jìn)去看看了,
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
首先這個判斷條件是成立的,在進(jìn)入羨慕的判斷條件,如果當(dāng)前數(shù)組的容量大于等于MAXIMUM_CAPACITY = 2 ^ 30,那么進(jìn)入判斷,很顯然,這個條件很難達(dá)成,直接進(jìn)入else if,oldCap = 16,左移一位是32,newCap = 32,默認(rèn)數(shù)組容量DEFAULT_INITIAL_CAPACITY = 16,所以判斷成立,oldThr = 12,左移一位是newThr = 24,得到新數(shù)組的擴(kuò)容閥值,然后創(chuàng)建一個新的Node[],并將newCap = 32作為新數(shù)組的長度,將新創(chuàng)建的數(shù)組賦值給table = newTable,
進(jìn)入下一個判斷語句,此時的oldTable不為空,所以進(jìn)入判斷體,這個判斷體主要是將原始數(shù)組的數(shù)據(jù)遍歷加入到新建數(shù)組中,
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
首先是進(jìn)入一個for循環(huán),遍歷數(shù)組中的每一個節(jié)點(diǎn)桶(主要是節(jié)點(diǎn)桶的頭結(jié)點(diǎn)),如果當(dāng)前節(jié)點(diǎn)桶不為null,則取出頭結(jié)點(diǎn),并將原始數(shù)組的當(dāng)前節(jié)點(diǎn)桶設(shè)置為null,如果節(jié)點(diǎn)桶中只有一個頭結(jié)點(diǎn),即頭結(jié)點(diǎn)無下一節(jié)點(diǎn),根據(jù)頭結(jié)點(diǎn)的hash值和容量得到一個新的節(jié)點(diǎn)下標(biāo),并將此頭結(jié)點(diǎn)加入到此下標(biāo)中;如果頭結(jié)點(diǎn)有下一節(jié)點(diǎn),這里暫且不考慮紅黑樹的情況,那么進(jìn)入else里面
else中是一個while循環(huán),因?yàn)槊恳粋€節(jié)點(diǎn)桶都是一個單鏈表,所以這里的while循環(huán)主要是遍歷原始數(shù)組中的一個桶的單鏈表,循環(huán)加入到新建數(shù)組中,關(guān)于擴(kuò)容下標(biāo)的計算從網(wǎng)上找到了一篇介紹,如果感興趣可以看一下https://www.cnblogs.com/shianliang/p/9204942.html
回到puVal(),此時到這里第一條數(shù)據(jù)算是添加完成了,開篇又說,HashMap在jdk1.8中加入了紅黑樹,我們來看看樹化的條件和過程,同樣還是putVal()：
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
在添加數(shù)據(jù)的時候,如果要添加的數(shù)據(jù)所對應(yīng)的下標(biāo)在數(shù)組中有數(shù)據(jù),此時就需要將此數(shù)據(jù)添加到鏈表/樹中,就會進(jìn)入到上面的else語句中,首先拿到數(shù)組中此下標(biāo)對應(yīng)的頭結(jié)點(diǎn)e,然后開啟一個死循環(huán)遍歷鏈表(如果此時桶中的是樹,則不會進(jìn)入這個else,下面會說到往樹中添加數(shù)據(jù)的過程),拿到頭結(jié)點(diǎn)e之后,開始遍歷頭結(jié)點(diǎn)所在的單鏈表,知道遍歷到鏈表的尾部,然后通過newNode創(chuàng)建一個新的節(jié)點(diǎn),加入到鏈表的尾部,然后判斷鏈表的長度是否大于等于 8,即binCount >= TREEIFY_THRESHOLD - 1 = 7,(因?yàn)楸闅v鏈表是從0開始的,所以最終是鏈表的長度不得大于等于8)如果大于等于的話,則開始通過treeifyBin()開始樹化。
static final int MIN_TREEIFY_CAPACITY = 64;
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
首先得到數(shù)組的長度,如果數(shù)組的長度小于MIN_TREEIFY_CAPACITY,那么就直接進(jìn)行擴(kuò)容操作,而不是進(jìn)行樹化,所以這里我們可以知道
擴(kuò)容的條件有兩個: 1)數(shù)組的長度達(dá)到了擴(kuò)容閥值,2)桶中的鏈表長度達(dá)到了8,并且數(shù)組的長度小于64
樹化的條件是：桶中單鏈表的長度達(dá)到了8,并且數(shù)組的長度大于等于64
我們來看else if,這里面同樣是一個while循環(huán),判讀語句中拿到鏈表的頭結(jié)點(diǎn),因?yàn)闃涔?jié)點(diǎn)TreeNode繼承于HashMap.Node,所以這里邊先將鏈表的頭結(jié)點(diǎn)e轉(zhuǎn)化為一個樹節(jié)點(diǎn)p,然后開始遍歷頭結(jié)點(diǎn),開始給各個樹節(jié)點(diǎn)添加前后節(jié)點(diǎn)的引用(看起來更像是一樣雙鏈表),桶內(nèi)的樹節(jié)點(diǎn)全部添加為前后引用之后,真正的樹化就要開始了：
if ((tab[index] = hd) != null)
hd.treeify(tab);
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
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;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
treeify的入?yún)樾枰粯浠逆湵淼念^結(jié)點(diǎn)所轉(zhuǎn)換為的樹節(jié)點(diǎn),然后開始一個for循環(huán),條件為x != null,next則為每次循環(huán)x的下一節(jié)點(diǎn)引用
先說一下紅黑樹的五個性質(zhì):
- 每個結(jié)點(diǎn)要么是紅的诅岩，要么是黑的讳苦。
- 根結(jié)點(diǎn)是黑的带膜。
- 每個葉結(jié)點(diǎn)，即空結(jié)點(diǎn)（NIL）是黑的鸳谜。
- 父節(jié)點(diǎn)和子節(jié)點(diǎn)都不能同時是紅色的膝藕，即：不能有兩個連續(xù)的紅色節(jié)點(diǎn)
- 對每個結(jié)點(diǎn)，從該結(jié)點(diǎn)到其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)咐扭。
關(guān)于紅黑樹可以看我這篇文章 TreeMap 源碼分析
繼續(xù)往下說,循環(huán)內(nèi):
首先得到x的下一節(jié)點(diǎn)并賦值給next,并初始化當(dāng)前節(jié)點(diǎn)x的左右子葉節(jié)點(diǎn),第一遍循環(huán)root節(jié)點(diǎn)肯定是為空的,所以將x節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)root,并將其父節(jié)點(diǎn)設(shè)置為null,顏色設(shè)置為黑色,這是第一次循環(huán),第二次循環(huán),進(jìn)入到了else語句中,首先獲取到當(dāng)前節(jié)點(diǎn)的key值和hash值芭挽，下面是一個死循環(huán)：
在死循環(huán)內(nèi)首先得到根節(jié)點(diǎn),并將根節(jié)點(diǎn)的hash值和當(dāng)前節(jié)點(diǎn)的hash值做對比,如果比根節(jié)點(diǎn)大則在根節(jié)點(diǎn)的右子樹上,比 根節(jié)點(diǎn)小則在左子樹上,紅黑樹中,左子樹總比右子樹要小,然后依次遍歷-對比判斷 最后將當(dāng)前節(jié)點(diǎn)放到合適的樹節(jié)點(diǎn)的左右子樹中。
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
上面的代碼正如我們所說的,遍歷整個紅黑樹并將當(dāng)前節(jié)點(diǎn)放入到指定合適的左右子樹中,因?yàn)槲覀冞€沒有為當(dāng)且插入的節(jié)點(diǎn)進(jìn)行著色操作,所以需要通過balanceInsertion進(jìn)行著色,基于紅黑樹的五個特性我們在插入一個樹節(jié)點(diǎn)并且為其著色之后,可能需要重新調(diào)整紅黑樹,為什么呢,其他的不說,開始我們自發(fā)的將單鏈表的頭結(jié)點(diǎn)設(shè)置為了根節(jié)點(diǎn),如果單鏈表的其他節(jié)點(diǎn)均小于頭結(jié)點(diǎn),那么在樹中的表現(xiàn)為,根節(jié)點(diǎn)的左子樹很深,而右子樹則沒有,紅黑樹是一種平衡樹,根據(jù)第五條特性可以看出,所以需要對紅黑樹進(jìn)行調(diào)整,同樣需要balanceInsertion來操作蝗肪。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
入?yún)楦?jié)點(diǎn)和當(dāng)前節(jié)點(diǎn),首先設(shè)置當(dāng)前節(jié)點(diǎn)是紅色,里面是一個for循環(huán),先看循環(huán)中的第一個判讀體
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
如果當(dāng)前樹節(jié)點(diǎn)的父子樹節(jié)點(diǎn)為空,因?yàn)楫?dāng)前節(jié)點(diǎn)已在紅黑樹中,那么只有一種可能,當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn),顏色著色為黑色,并返回當(dāng)前節(jié)點(diǎn),
如果當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色,并當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)為空,所以當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)的子樹節(jié)點(diǎn),所以不需要調(diào)整紅黑樹,直接返回就行
所以上面的判斷是祛除當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)或者當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)的子樹節(jié)點(diǎn)的情況,如果根節(jié)點(diǎn)只有一個子樹節(jié)點(diǎn),那么此時的紅黑樹違反第五條特性,但是怎么調(diào)整都是這樣,就會陷入一個死循環(huán)中,所以排除了這種情況.
通過上面的判斷,可以知曉循環(huán)體中的變量的意義:
xp當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
xpp當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的父節(jié)點(diǎn),即祖父節(jié)點(diǎn)
xppl當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的左子樹節(jié)點(diǎn) 即當(dāng)前節(jié)點(diǎn)的叔父節(jié)點(diǎn)
xppr當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的右子樹節(jié)點(diǎn) 即當(dāng)前節(jié)點(diǎn)的叔父節(jié)點(diǎn)
接著往下看
if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
首先要確定一點(diǎn)就是,能進(jìn)入當(dāng)前循環(huán)的都是父節(jié)點(diǎn)是紅色的,如果是黑色的,在上個判斷 體中的else中就攔截掉了,看當(dāng)前的判斷判斷條件是如果xp是xpp的左子樹節(jié)點(diǎn),即xppl,然后進(jìn)入下一個判斷
如果當(dāng)前節(jié)點(diǎn)的叔父節(jié)點(diǎn)xppr不為空,并且顏色為紅色,那么就進(jìn)行如下設(shè)置:叔父節(jié)點(diǎn)xppr設(shè)置為黑色,xp設(shè)置為黑色,xpp設(shè)置為紅色,然后將祖父節(jié)點(diǎn)xpp設(shè)置為當(dāng)前節(jié)點(diǎn),進(jìn)行下一次的遍歷循環(huán),開始判斷祖父節(jié)點(diǎn)變?yōu)榧t色之后是否合乎紅黑樹的特性,如果祖父節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色的話,那就沒有異常,直接返回根節(jié)點(diǎn)即可,如果祖父節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色,因?yàn)樽娓腹?jié)點(diǎn)也是紅色的,違反了第四個特性,需要對紅黑樹進(jìn)行調(diào)整,下面就涉及到了紅黑樹的左右旋的操作,限于篇幅這里就不過多介紹了,
如果xp == xppl,xp.color = red
如果xppr.color == red,那么xpp.color != red, 則設(shè)置xpp.color == red并且xppl,xppr != red;
如果xppr.color != red
- 如果當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的右子樹節(jié)點(diǎn),左旋父節(jié)點(diǎn),使父節(jié)點(diǎn)位于當(dāng)前節(jié)點(diǎn)的左子樹上,然后將父節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)進(jìn)行如下處理：
設(shè)置當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的顏色為黑色,祖父節(jié)點(diǎn)為紅色,右旋祖父節(jié)點(diǎn)- 如果當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的左子樹節(jié)點(diǎn):
設(shè)置當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的顏色為黑色,祖父節(jié)點(diǎn)為紅色,右旋祖父節(jié)點(diǎn)
如果父節(jié)點(diǎn)位于祖父節(jié)點(diǎn)的右子樹上,道理是一樣的.
回到treeify,樹化完成之后還有最后一步moveRootToFront,因?yàn)?code>HashMap中的紅黑樹是與雙鏈表糅合在一起的,具體表現(xiàn)為,數(shù)組table獲取當(dāng)前下標(biāo)的節(jié)點(diǎn),是鏈表的頭結(jié)點(diǎn),單不一定是樹的根節(jié)點(diǎn),因此需要將樹的根節(jié)點(diǎn)與鏈表的頭結(jié)點(diǎn)設(shè)置為同一個
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
代碼很簡單我就不細(xì)說了,大致的說一下,首先從數(shù)組table中獲取到當(dāng)前下標(biāo)的節(jié)點(diǎn),即頭結(jié)點(diǎn),如果頭結(jié)點(diǎn)與root節(jié)點(diǎn)不相同,則需要將root節(jié)點(diǎn)設(shè)置為頭結(jié)點(diǎn),首先將頭結(jié)點(diǎn)的前后節(jié)點(diǎn)取出來,并使這兩個節(jié)點(diǎn)相互關(guān)聯(lián),然后將根節(jié)點(diǎn)的next指針指向原先的頭結(jié)點(diǎn),原先頭結(jié)點(diǎn)的prev指針指向根節(jié)點(diǎn),并設(shè)置根節(jié)點(diǎn)的prev指針指向空,最終使根節(jié)點(diǎn)變成了頭結(jié)點(diǎn)
到這里樹化就完成了,雖然有點(diǎn)爛尾,具體有關(guān)紅黑樹的可以去看TreeMap 源碼分析
樹化完成之后,如果我們想要往樹中添加一個節(jié)點(diǎn)的話,同樣需要通過putVal來添加,其中有這么一條判斷語句
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
其中p為根節(jié)點(diǎn),插入過程中會循環(huán)遍歷比較插入節(jié)點(diǎn)的hash值和遍歷到的節(jié)點(diǎn)的hash值,然后插入到樹中,插入之后,會檢查樹的平衡性,可能需要調(diào)整樹的結(jié)構(gòu)
回到putVal()袜爪，上面說了將元素添加到紅黑樹的過程,如果此時的數(shù)組桶中的是單鏈表那么：
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
會通過for循環(huán)得到尾節(jié)點(diǎn),將新建的節(jié)點(diǎn)添加到尾節(jié)點(diǎn)即可。
此外還有一種情況就是,如果當(dāng)前節(jié)點(diǎn)對應(yīng)key值在鏈表中存在,那么會走如下的判斷:
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
取出當(dāng)前key對應(yīng)原始value值薛闪，然后將傳入的value值放入到里面,然后調(diào)用了afterNodeAccess(),最后返回了原始元素值,afterNodeAccess()在HashMap中是一個空實(shí)現(xiàn),具體的實(shí)現(xiàn)在LinkedHashMap中,這里不再多說,我會在LinkedHashMap中說到.
