這是筆者一個(gè)好友面試阿里時(shí)，被問及的一個(gè)問題，應(yīng)該不少人看到這個(gè)問題都會(huì)一面懵逼。因?yàn)?，大部分的文章都是分析鏈表是怎么轉(zhuǎn)換成紅黑樹的，但是并沒有說明為什么當(dāng)鏈表長度為8的時(shí)候才做轉(zhuǎn)換動(dòng)作。筆者第一反應(yīng)也是一樣，只能初略的猜測是因?yàn)闀r(shí)間和空間的權(quán)衡。
要弄明白這個(gè)問題，我們首先要明白為什么要轉(zhuǎn)換，這個(gè)問題比較簡單，因?yàn)镸ap中桶的元素初始化是鏈表保存的，其查找性能是O(n)，而樹結(jié)構(gòu)能將查找性能提升到O(log(n))。當(dāng)鏈表長度很小的時(shí)候，即使遍歷，速度也非?？?，但是當(dāng)鏈表長度不斷變長，肯定會(huì)對查詢性能有一定的影響，所以才需要轉(zhuǎn)成樹。至于為什么閾值是8，我想，去源碼中找尋答案應(yīng)該是最可靠的途徑。
8這個(gè)閾值定義在HashMap中，如下所示，這段注釋只說明了8是bin（bin就是bucket，即HashMap中hashCode值一樣的元素保存的地方）從鏈表轉(zhuǎn)成樹的閾值，但是并沒有說明為什么是8：
/**
*?The?bin?count?threshold?for?using?a?tree?rather?than?list?for?a
*?bin.??Bins?are?converted?to?trees?when?adding?an?element?to?a
*?bin?with?at?least?this?many?nodes.?The?value?must?be?greater
*?than?2?and?should?be?at?least?8?to?mesh?with?assumptions?in
*?tree?removal?about?conversion?back?to?plain?bins?upon?shrinkage.
*/
staticfinalintTREEIFY_THRESHOLD?=8;
我們繼續(xù)往下看，在HashMap中有一段Implementation notes，筆者摘錄了幾段重要的描述，第一段如下所示，大概含義是當(dāng)bin變得很大的時(shí)候，就會(huì)被轉(zhuǎn)換成TreeNodes中的bin，其結(jié)構(gòu)和TreeMap相似，也就是紅黑樹：
This?map?usually?actsasa?binned?(bucketed)?hash?table,?but
whenbinsgettoo?large,?they?are?transformedintobinsofTreeNodes,
eachstructured?similarlytothoseinjava.util.TreeMap
繼續(xù)往下看，TreeNodes占用空間是普通Nodes的兩倍，所以只有當(dāng)bin包含足夠多的節(jié)點(diǎn)時(shí)才會(huì)轉(zhuǎn)成TreeNodes，而是否足夠多就是由TREEIFY_THRESHOLD的值決定的。當(dāng)bin中節(jié)點(diǎn)數(shù)變少時(shí)，又會(huì)轉(zhuǎn)成普通的bin。并且我們查看源碼的時(shí)候發(fā)現(xiàn)，鏈表長度達(dá)到8就轉(zhuǎn)成紅黑樹，當(dāng)長度降到6就轉(zhuǎn)成普通bin。
這樣就解析了為什么不是一開始就將其轉(zhuǎn)換為TreeNodes，而是需要一定節(jié)點(diǎn)數(shù)才轉(zhuǎn)為TreeNodes，說白了就是trade-off，空間和時(shí)間的權(quán)衡：
Because?TreeNodes?are?about?twice?the?size?of?regular?nodes,?we
usethemonlywhenbins?contain?enough?nodestowarrantuse
(see?TREEIFY_THRESHOLD).Andwhenthey?become?too?small?(dueto
removalorresizing)?theyareconverted?backtoplain?bins.In
usageswithwell-distributeduserhashCodes,?tree?binsare
rarely?used.??Ideally,underrandom?hashCodes,?the?frequencyof
nodesinbinsfollowsa?Poisson?distribution
(http://en.wikipedia.org/wiki/Poisson_distribution)witha
parameterofabout0.5onaverageforthedefaultresizing
thresholdof0.75,?althoughwithalargevariancebecauseof
resizing?granularity.?Ignoringvariance,?the?expected
occurrencesoflistsizekare(exp(-0.5)*pow(0.5,?k)/factorial(k)).
Thefirstvaluesare:
0:0.60653066
1:0.30326533
2:0.07581633
3:0.01263606
4:0.00157952
5:0.00015795
6:0.00001316
7:0.00000094
8:0.00000006
more:lessthan1inten?million
這段內(nèi)容還說到：當(dāng)hashCode離散性很好的時(shí)候，樹型bin用到的概率非常小，因?yàn)閿?shù)據(jù)均勻分布在每個(gè)bin中，幾乎不會(huì)有bin中鏈表長度會(huì)達(dá)到閾值。但是在隨機(jī)hashCode下，離散性可能會(huì)變差，然而JDK又不能阻止用戶實(shí)現(xiàn)這種不好的hash算法，因此就可能導(dǎo)致不均勻的數(shù)據(jù)分布。不過理想情況下隨機(jī)hashCode算法下所有bin中節(jié)點(diǎn)的分布頻率會(huì)遵循泊松分布，我們可以看到，一個(gè)bin中鏈表長度達(dá)到8個(gè)元素的概率為0.00000006，幾乎是不可能事件。所以，之所以選擇8，不是拍拍屁股決定的，而是根據(jù)概率統(tǒng)計(jì)決定的。由此可見，發(fā)展30年的Java每一項(xiàng)改動(dòng)和優(yōu)化都是非常嚴(yán)謹(jǐn)和科學(xué)的。
畫外音
筆者通過搜索引擎搜索這個(gè)問題，發(fā)現(xiàn)很多下面這個(gè)答案（猜測也是相互轉(zhuǎn)發(fā)）：
紅黑樹的平均查找長度是log(n)，如果長度為8，平均查找長度為log(8)=3，鏈表的平均查找長度為n/2，當(dāng)長度為8時(shí)，平均查找長度為8/2=4，這才有轉(zhuǎn)換成樹的必要；鏈表長度如果是小于等于6，6/2=3，而log(6)=2.6，雖然速度也很快的，但是轉(zhuǎn)化為樹結(jié)構(gòu)和生成樹的時(shí)間并不會(huì)太短。
筆者認(rèn)為這個(gè)答案不夠嚴(yán)謹(jǐn)：3相比4有轉(zhuǎn)換的必要，而2.6相比3就沒有轉(zhuǎn)換的必要？起碼我不敢茍同這個(gè)觀點(diǎn)。
?文章轉(zhuǎn)自公眾號：阿飛的博客?
