前言
關(guān)于Java的HashMap的資料真的太多了，用被研究“爛”了形容也一點(diǎn)不過(guò)分??，此篇文章就幾個(gè)疑難問(wèn)題加上自己這兩天的研究，做個(gè)總結(jié)。
1.原理實(shí)現(xiàn)細(xì)節(jié)總結(jié)
1.hashMap在Jdk1.7和1.8略有不一樣，1.7是數(shù)組+鏈表，1.8是數(shù)組+鏈表+紅黑樹(shù)。
2.通過(guò)系統(tǒng)提供或者自定義的hashCode()算法算出key的hashCode&table.lenth - 1算出index，插入數(shù)組當(dāng)中，時(shí)間復(fù)雜度為O(1)。
3.不同的hashCode通過(guò)&運(yùn)算得到的index可能相同，我們稱(chēng)之為hash collision(哈希沖突/碰撞)。如果出現(xiàn)碰撞，相同index的bucket將變成鏈表或者紅黑樹(shù)，1.8中當(dāng)相同位置的節(jié)點(diǎn)大于8時(shí)會(huì)從鏈表變成紅黑樹(shù)，相反如果又變成6或者更小時(shí)會(huì)退化成鏈表。
4.loadfactor默認(rèn)0.75，假設(shè)數(shù)組容量為16，那么當(dāng)size為12時(shí)，數(shù)組擴(kuò)容成32。之前不管是鏈表還是樹(shù)上的節(jié)點(diǎn)都會(huì)重新計(jì)算index進(jìn)行遷移。
5.hashMap中即使會(huì)涉及到一些鏈表和二叉樹(shù)搜索樹(shù)的遍歷，但get和put的時(shí)間復(fù)雜度也可以近似看成O(1)。
6.當(dāng)數(shù)組容量小于64的時(shí)候，當(dāng)鏈表大于8的時(shí)候也不會(huì)樹(shù)化，而是優(yōu)先擴(kuò)容。
2.為什么loadfactor是0.75
查遍網(wǎng)上資料，好像沒(méi)有官方解釋。然后看到很多文章都是亂說(shuō)的，什么泊松分布之類(lèi)的，都是文不對(duì)題。
里面第三個(gè)答案好像是現(xiàn)在公認(rèn)的比較可信的說(shuō)法。
第一次看到這個(gè)還是有點(diǎn)懵逼，這個(gè)ln(2)是怎么算出來(lái)的。
昨晚我自己在書(shū)房推了一遍，這里需要用到離散概率和無(wú)窮比無(wú)窮求極限的一些大學(xué)數(shù)學(xué)基礎(chǔ)知識(shí)。
當(dāng)數(shù)組的容量趨向于無(wú)窮大時(shí)，負(fù)載因子約等于0.7，小于這個(gè)值，意為"不太容易"發(fā)生hash碰撞，所以各個(gè)語(yǔ)言的hashMap的loadfactor也略有不同。
3.樹(shù)化問(wèn)題
既然遍歷鏈表的復(fù)雜度是O(n)，而紅黑樹(shù)因?yàn)橛凶云胶獾奶攸c(diǎn)復(fù)雜度是O(log(n))，為什么不直接用紅黑樹(shù)呢？
因?yàn)閱蝹€(gè) TreeNode需要占用的空間大約是普通 Node的兩倍，這個(gè)很好理解，TreeNode中有顏色屬性，父節(jié)點(diǎn)，左右子節(jié)點(diǎn)等屬性，所以只有當(dāng)包含足夠多的Nodes 時(shí)才會(huì)轉(zhuǎn)成 TreeNodes，而是否足夠多就是由TREEIFY_THRESHOLD的值決定的。而當(dāng)桶中節(jié)點(diǎn)數(shù)由于移除或者resize變少后，又會(huì)變回普通的鏈表的形式，以便節(jié)省空間。通過(guò)查看源碼可以發(fā)現(xiàn)，默認(rèn)是鏈表長(zhǎng)度達(dá)到 8 就轉(zhuǎn)成紅黑樹(shù)，而當(dāng)長(zhǎng)度降到 6 就轉(zhuǎn)換回去，這體現(xiàn)了時(shí)間和空間平衡的思想，最開(kāi)始使用鏈表的時(shí)候，空間占用是比較少的，而且由于鏈表短，所以查詢時(shí)間也沒(méi)有太大的問(wèn)題?？墒钱?dāng)鏈表越來(lái)越長(zhǎng)，需要用紅黑樹(shù)的形式來(lái)保證查詢的效率。對(duì)于何時(shí)應(yīng)該從鏈表轉(zhuǎn)化為紅黑樹(shù)，需要確定一個(gè)閾值，這個(gè)閾值默認(rèn)為 8，并且在源碼中也對(duì)選擇 8 這個(gè)數(shù)字做了說(shuō)明，原文如下：
![]()
image.png
大概意思:
如果 hashCode 分布良好，也就是 hash 計(jì)算的結(jié)果離散好的話，那么紅黑樹(shù)這種形式是很少會(huì)被用到的，因?yàn)楦鱾€(gè)值都均勻分布，很少出現(xiàn)鏈表很長(zhǎng)的情況。在理想情況下，在loadfactor等于0.75的情況下，鏈表長(zhǎng)度符合泊松分布，各個(gè)長(zhǎng)度的命中概率依次遞減，當(dāng)長(zhǎng)度為 8 的時(shí)候，概率僅為 0.00000006。這是一個(gè)小于千萬(wàn)分之一的概率，通常我們的 Map 里面是不會(huì)存儲(chǔ)這么多的數(shù)據(jù)的，所以通常情況下，并不會(huì)發(fā)生從鏈表向紅黑樹(shù)的轉(zhuǎn)換。但，頂不住我們故意把算法變得不均勻，例如下面的代碼:
@Override
public int hashCode() {
return 1;
}
這樣一旦size過(guò)大，hashMap必樹(shù)化。
事實(shí)上，鏈表長(zhǎng)度超過(guò) 8 就轉(zhuǎn)為紅黑樹(shù)的設(shè)計(jì)，更多的是為了防止用戶自己實(shí)現(xiàn)了不好的哈希算法時(shí)導(dǎo)致鏈表過(guò)長(zhǎng)，從而導(dǎo)致查詢效率低，而此時(shí)轉(zhuǎn)為紅黑樹(shù)更多的是一種保底策略，用來(lái)保證極端情況下查詢的效率。通常如果 hash 算法正常的話，那么鏈表的長(zhǎng)度也不會(huì)很長(zhǎng)，那么紅黑樹(shù)也不會(huì)帶來(lái)明顯的查詢時(shí)間上的優(yōu)勢(shì)，反而會(huì)增加空間負(fù)擔(dān)。所以通常情況下，并沒(méi)有必要轉(zhuǎn)為紅黑樹(shù)，所以就選擇了概率非常小，小于千萬(wàn)分之一概率，也就是長(zhǎng)度為 8 的概率，把長(zhǎng)度 8 作為轉(zhuǎn)化的默認(rèn)閾值。
所以如果平時(shí)開(kāi)發(fā)中發(fā)現(xiàn) HashMap 或是 ConcurrentHashMap 內(nèi)部出現(xiàn)了紅黑樹(shù)的結(jié)構(gòu)，這個(gè)時(shí)候往往就說(shuō)明我們的哈希算法出了問(wèn)題，需要留意是不是我們實(shí)現(xiàn)了效果不好的 hashCode 方法，并對(duì)此進(jìn)行改進(jìn)，以便減少?zèng)_突。
4.JDK1.7頭插問(wèn)題
JDK1.7的hashMap在擴(kuò)容時(shí)的數(shù)據(jù)遷移時(shí)，遍歷節(jié)點(diǎn)，之后采用頭倒序的方式進(jìn)行遷移，也就是后遍歷到的節(jié)點(diǎn)，會(huì)插到新數(shù)組節(jié)點(diǎn)的頭部，這樣在多線程的情況會(huì)出現(xiàn)循環(huán)鏈表的情況。
下面這篇文章：
我覺(jué)得講的是講得比詳細(xì)，也是比較通俗易懂的，這邊不做過(guò)多的解釋了。
我想談?wù)劦氖顷P(guān)于這個(gè)"bug"的看法:
首先hashMap本身就是線程不安全的，官方本身就不建議你這樣使用。
關(guān)于這個(gè)bug的討論就好比你在一個(gè)錯(cuò)誤的情況討論一個(gè)錯(cuò)誤的事情。
雖然我個(gè)人認(rèn)為這不是一個(gè)bug，但是JDK還是在1.8修復(fù)了這個(gè)問(wèn)題，改成了尾插。但hashMap在1.8的多線程中同樣會(huì)有別的問(wèn)題。
最后再來(lái)說(shuō)說(shuō)為什么1.7會(huì)設(shè)計(jì)成頭插？
有一種說(shuō)法是：緩存的時(shí)間局部性原則 (新插入的數(shù)據(jù)可能會(huì)更早用到)。這一點(diǎn)在操作系統(tǒng)中有很常見(jiàn)的應(yīng)用，例如LRU算法。
5.JDK1.8不安全問(wèn)題
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) // 如果沒(méi)有hash碰撞則直接插入元素
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當(dāng)中發(fā)生的問(wèn)題，第6行代碼，如果沒(méi)有hash碰撞則會(huì)直接插入元素。如果線程A和線程B同時(shí)進(jìn)行put操作，剛好這兩條不同的數(shù)據(jù)hash值一樣，并且該位置數(shù)據(jù)為null，所以這線程A、B都會(huì)進(jìn)入第6行代碼中。假設(shè)一種情況，線程A進(jìn)入后還未進(jìn)行數(shù)據(jù)插入時(shí)掛起，而線程B正常執(zhí)行，從而正常插入數(shù)據(jù)，然后線程A獲取CPU時(shí)間片，此時(shí)線程A不用再進(jìn)行hash判斷了，問(wèn)題出現(xiàn)：線程A會(huì)把線程B插入的數(shù)據(jù)給覆蓋，發(fā)生線程不安全。
6.總結(jié)
學(xué)無(wú)止境
感謝
面試題：為什么 Map 桶中超過(guò) 8 個(gè)才轉(zhuǎn)為紅黑樹(shù)？
為何hashmap默認(rèn)的負(fù)載因子是0.75？應(yīng)該是空間和時(shí)間的折中，背后的統(tǒng)計(jì)原理是什么呢？
