為什麼Map桶中個數超過8才轉為紅黑樹技术頭條網

2019-11-26 23:01:37 咪小懶

這是筆者一個好友面試阿里時，被問及的一個問題，應該不少人看到這個問題都會一面懵逼。因為，大部分的文章都是分析鏈表是怎麼轉換成紅黑樹的，但是並沒有說明為什麼當鏈表長度為8的時候才做轉換動作。筆者第一反應也是一樣，只能初略的猜測是因為時間和空間的權衡。

要弄明白這個問題，我們首先要明白為什麼要轉換，這個問題比較簡單，因為Map中桶的元素初始化是鏈表保存的，其查找性能是O(n)，而樹結構能將查找性能提升到O(log(n))。當鏈表長度很小的時候，即使遍歷，速度也非常快，但是當鏈表長度不斷變長，肯定會對查詢性能有一定的影響，所以才需要轉成樹。至於為什麼閾值是8，我想，去源碼中找尋答案應該是最可靠的途徑。

8這個閾值定義在HashMap中，如下所示，這段註釋只說明瞭8是bin（bin就是bucket，即HashMap中hashCode值一樣的元素保存的地方）從鏈表轉成樹的閾值，但是並沒有說明為什麼是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;

我們繼續往下看，在HashMap中有一段Implementation notes，筆者摘錄了幾段重要的描述，第一段如下所示，大概含義是當bin變得很大的時候，就會被轉換成TreeNodes中的bin，其結構和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

繼續往下看，TreeNodes佔用空間是普通Nodes的兩倍，所以只有當bin包含足夠多的節點時才會轉成TreeNodes，而是否足夠多就是由TREEIFY_THRESHOLD的值決定的。當bin中節點數變少時，又會轉成普通的bin。並且我們查看源碼的時候發現，鏈表長度達到8就轉成紅黑樹，當長度降到6就轉成普通bin。

這樣就解析了為什麼不是一開始就將其轉換為TreeNodes，而是需要一定節點數才轉為TreeNodes，說白了就是trade-off，空間和時間的權衡：

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

這段內容還說到：當hashCode離散性很好的時候，樹型bin用到的概率非常小，因為數據均勻分佈在每個bin中，幾乎不會有bin中鏈表長度會達到閾值。但是在隨機hashCode下，離散性可能會變差，然而JDK又不能阻止用戶實現這種不好的hash算法，因此就可能導致不均勻的數據分佈。不過理想情況下隨機hashCode算法下所有bin中節點的分佈頻率會遵循

泊松分佈，我們可以看到，一個bin中鏈表長度達到8個元素的概率為0.00000006，幾乎是不可能事件。所以，之所以選擇8，不是拍拍屁股決定的，而是根據概率統計決定的。由此可見，發展30年的Java每一項改動和優化都是非常嚴謹和科學的。