HashMap由哪些數(shù)據(jù)結(jié)構(gòu)維持?
查看HashMap源碼可知存放key-value的是一個(gè)Node<K,V>對象數(shù)組滔蝉，Node內(nèi)有4個(gè)成員變量瞎领，key,value,hash,nextNode赞弥。nextNode可能是一個(gè)普通的Node,那么此時(shí)它就是一個(gè)鏈表店读，也可能是Node的子類TreeNode纫普，一個(gè)紅黑樹嫁艇，即HashMap的數(shù)據(jù)結(jié)構(gòu)實(shí)際上是由數(shù)組朗伶、鏈表、紅黑樹來維持步咪。
為什么不使用List<Node<K,V>>來存放key-value數(shù)據(jù)?
如果使用list论皆，插入的時(shí)候需要遍歷所有Node,判斷node的key是否存在。取出的時(shí)候也需要從頭遍歷直到遇到相同的key,才會停止。
而HashMap中Node數(shù)組点晴，插入的下標(biāo)位置是與key的hashcode有關(guān)感凤。
HashMap如何存放key-value？
一般hashcode值常常超過數(shù)組大小size值粒督，所以就要把hashcode轉(zhuǎn)為二進(jìn)制取二進(jìn)制的后幾位陪竿，具體算法是將hashcode二進(jìn)制值位與運(yùn)算&(size-1)，（這個(gè)算法的前提是size只能是2的n次方大小屠橄，這樣size-1的二進(jìn)制值就為0111111...）但是為了盡可能地將node存放在不同數(shù)組下標(biāo)位置上族跛，hashMap中優(yōu)化后的算法如下：
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
通過這個(gè)算法得出的hash值即為node中的hash，而存放在數(shù)組中位置即為hash&(size-1)锐墙。
即使有算法優(yōu)化礁哄，hash還是會出現(xiàn)相同，此時(shí)就會把這個(gè)要存放的node作為起始位置node的nextNode贮匕，形成鏈表結(jié)構(gòu)姐仅。為了防止鏈表無限延伸導(dǎo)致存取node的復(fù)雜度變高，當(dāng)鏈表延伸個(gè)數(shù)等于8時(shí)刻盐，此時(shí)鏈表結(jié)構(gòu)將轉(zhuǎn)換為紅黑樹treeNode。而紅黑樹的節(jié)點(diǎn)小于等于6時(shí)則會轉(zhuǎn)回鏈表結(jié)構(gòu)（發(fā)生場景：hashMap擴(kuò)容后會拆分鏈表和紅黑樹劳翰，此時(shí)可能會發(fā)生）敦锌。
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; //resize()方法會初始化數(shù)組，或擴(kuò)容數(shù)組
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)))) //相同key,則替換node對象
e = p;
else if (p instanceof TreeNode) //node為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 //鏈表長度為8時(shí)轉(zhuǎn)為紅黑樹
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; //修改計(jì)數(shù)器
if (++size > threshold) //大于數(shù)組大小的0.75倍時(shí)開始擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}
HashMap如何進(jìn)行擴(kuò)容的?
前文說到數(shù)組大小要保持2的n次方大小乙墙，此時(shí)直接位運(yùn)算左移1位對數(shù)組擴(kuò)容。
然后根據(jù)新的size大小計(jì)算下標(biāo)存放在相應(yīng)位置生均，有鏈表結(jié)構(gòu)和紅黑樹結(jié)構(gòu)的即nextNode不為空的node會進(jìn)行拆分听想。拆分規(guī)則算法是hash值與原size位與&運(yùn)算不為0，為0的數(shù)組下標(biāo)不變马胧，不為0的數(shù)組下標(biāo)為原下標(biāo)+原數(shù)組長度汉买。原因是運(yùn)算不為0的hash根據(jù)新數(shù)組大小重新計(jì)算下標(biāo)等于原下標(biāo)+原數(shù)組長度。
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode)
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.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;
}
}
}
