這個問題在面試的程序中被問到了，之前在學習程序中也想到過這個問題，但是沒有仔細的追究，面試被問到，我也只是從查找時間和空間上的一種權衡，簡答的說了一下，面試官讓我回去仔細查一查，好吧，我只好回來再查查了，尷尬了，
直接分析原始碼：
/**
* 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;
上面定義的是閾值為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每一項改動和優化都是非常嚴謹和科學的，
-
筆者通過搜索引擎搜索這個問題，發現很多下面這個答案（猜測也是相互轉發）：紅黑樹的平均查找長度是log(n)，如果長度為8，平均查找長度為log(8)=3，鏈表的平均查找長度為n/2，當長度為8時，平均查找長度為8/2=4，這才有轉換成樹的必要；鏈表長度如果是小于等于6，6/2=3，而log(6)=2.6，雖然速度也很快的，但是轉化為樹結構和生成樹的時間并不會太短，
筆者認為這個答案不夠嚴謹：3相比4有轉換的必要，而2.6相比3就沒有轉換的必要？起碼我不敢茍同這個觀點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/98841.html
標籤：其他