歡迎關(guān)注筆者的公眾號：【阿飛的博客】壶唤，首發(fā)都在這里！Ｗ厮闸盔！
這是筆者一個好友面試阿里時，被問及的一個問題琳省，應(yīng)該不少人看到這個問題都會一面懵逼迎吵。因為，大部分的文章都是分析鏈表是怎么轉(zhuǎn)換成紅黑樹的针贬，但是并沒有說明為什么當(dāng)鏈表長度為8的時候才做轉(zhuǎn)換動作击费。筆者第一反應(yīng)也是一樣，只能初略的猜測是因為時間和空間的權(quán)衡坚踩。
要弄明白這個問題荡灾，我們首先要明白為什么要轉(zhuǎn)換瓤狐，這個問題比較簡單瞬铸，因為Map中桶的元素初始化是鏈表保存的，其查找性能是O(n)础锐，而樹結(jié)構(gòu)能將查找性能提升到O(log(n))嗓节。當(dāng)鏈表長度很小的時候，即使遍歷皆警，速度也非忱剐快，但是當(dāng)鏈表長度不斷變長信姓，肯定會對查詢性能有一定的影響鸵隧，所以才需要轉(zhuǎn)成樹。至于為什么閾值是8意推，我想豆瘫，去源碼中找尋答案應(yīng)該是最可靠的途徑。
8這個閾值定義在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.
*/
static final int TREEIFY_THRESHOLD = 8;
我們繼續(xù)往下看昵宇，在HashMap中有一段Implementation notes磅崭，筆者摘錄了幾段重要的描述，第一段如下所示瓦哎，大概含義是當(dāng)bin變得很大的時候砸喻，就會被轉(zhuǎn)換成TreeNodes中的bin，其結(jié)構(gòu)和TreeMap相似杭煎，也就是紅黑樹：
This map usually acts as a binned (bucketed) hash table, but
when bins get too large, they are transformed into bins of TreeNodes,
each structured similarly to those in java.util.TreeMap
繼續(xù)往下看恩够，TreeNodes占用空間是普通Nodes的兩倍，所以只有當(dāng)bin包含足夠多的節(jié)點時才會轉(zhuǎn)成TreeNodes羡铲，而是否足夠多就是由TREEIFY_THRESHOLD的值決定的蜂桶。當(dāng)bin中節(jié)點數(shù)變少時，又會轉(zhuǎn)成普通的bin也切。并且我們查看源碼的時候發(fā)現(xiàn)扑媚，鏈表長度達到8就轉(zhuǎn)成紅黑樹，當(dāng)長度降到6就轉(zhuǎn)成普通bin雷恃。
這樣就解析了為什么不是一開始就將其轉(zhuǎn)換為TreeNodes疆股，而是需要一定節(jié)點數(shù)才轉(zhuǎn)為TreeNodes，說白了就是trade-off倒槐，空間和時間的權(quán)衡：
Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins. In
usages with well-distributed user hashCodes, tree bins are
rarely used. Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of
resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5)*pow(0.5, k)/factorial(k)).
The first values are:
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: less than 1 in ten million
這段內(nèi)容還說到：當(dāng)hashCode離散性很好的時候旬痹，樹型bin用到的概率非常小，因為數(shù)據(jù)均勻分布在每個bin中讨越，幾乎不會有bin中鏈表長度會達到閾值两残。但是在隨機hashCode下，離散性可能會變差把跨，然而JDK又不能阻止用戶實現(xiàn)這種不好的hash算法人弓，因此就可能導(dǎo)致不均勻的數(shù)據(jù)分布。不過理想情況下隨機hashCode算法下所有bin中節(jié)點的分布頻率會遵循泊松分布着逐，我們可以看到崔赌，一個bin中鏈表長度達到8個元素的概率為0.00000006，幾乎是不可能事件耸别。所以健芭，之所以選擇8，不是拍拍屁股決定的秀姐，而是根據(jù)概率統(tǒng)計決定的慈迈。由此可見，發(fā)展30年的Java每一項改動和優(yōu)化都是非常嚴謹和科學(xué)的囊扳。
- 畫外音
筆者通過搜索引擎搜索這個問題吩翻，發(fā)現(xiàn)很多下面這個答案（猜測也是相互轉(zhuǎn)發(fā)）：
紅黑樹的平均查找長度是log(n)兜看，如果長度為8，平均查找長度為log(8)=3狭瞎，鏈表的平均查找長度為n/2细移，當(dāng)長度為8時，平均查找長度為8/2=4熊锭，這才有轉(zhuǎn)換成樹的必要弧轧；鏈表長度如果是小于等于6，6/2=3碗殷，而log(6)=2.6精绎，雖然速度也很快的，但是轉(zhuǎn)化為樹結(jié)構(gòu)和生成樹的時間并不會太短锌妻。
筆者認為這個答案不夠嚴謹：3相比4有轉(zhuǎn)換的必要代乃，而2.6相比3就沒有轉(zhuǎn)換的必要？起碼我不敢茍同仿粹。
