Map桶中超過8個才轉為紅黑樹的原因是什么

本篇內容主要講解“Map桶中超過8個才轉為紅黑樹的原因是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Map桶中超過8個才轉為紅黑樹的原因是什么”吧!

JDK 1.8 的 HashMap 和 ConcurrentHashMap 都有這樣一個特點：最開始的 Map 是空的，因為里面沒有任何元素，往里放元素時會計算 hash 值，計算之后，第 1 個 value 會首先占用一個桶（也稱為槽點）位置，后續(xù)如果經過計算發(fā)現(xiàn)需要落到同一個桶中，那么便會使用鏈表的形式往后延長，俗稱“拉鏈法”，如圖所示：

當鏈表長度大于或等于閾值（默認為 8）的時候，如果同時還滿足容量大于或等于 MIN_TREEIFY_CAPACITY（默認為 64）的要求，就會把鏈表轉換為紅黑樹。同樣，后續(xù)如果由于刪除或者其他原因調整了大小，當紅黑樹的節(jié)點小于或等于 6 個以后，又會恢復為鏈表形態(tài)。如下圖：

在圖中我們可以看到，有一些槽點是空的，有一些是拉鏈，有一些是紅黑樹。

那么為什么轉化的這個閾值要默認設置為 8 呢？

• 那首先我們就要知道為什么要轉換，因為轉換是第一步。

每次遍歷一個鏈表，平均查找的時間復雜度是 O(n)，n 是鏈表的長度。紅黑樹有和鏈表不一樣的查找性能，由于紅黑樹有自平衡的特點，可以防止不平衡情況的發(fā)生，所以可以始終將查找的時間復雜度控制在 O(log(n))。最初鏈表還不是很長，所以可能 O(n) 和 O(log(n)) 的區(qū)別不大，但是如果鏈表越來越長，那么這種區(qū)別便會有所體現(xiàn)。所以為了提升查找性能，需要把鏈表轉化為紅黑樹的形式。

• 那為什么不一開始就用紅黑樹，反而要經歷一個轉換的過程呢？

在 JDK 的源碼注釋中已經對這個問題作了解釋：

Because TreeNodes are about twice the size of regular nodes,
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due 
removal or resizing) they are converted back to plain bins.

這段話的意思是：單個 TreeNode 需要占用的空間大約是普通 Node 的兩倍，所以只有當包含足夠多的 Nodes 時才會轉成 TreeNodes，而是否足夠多就是由 TREEIFY_THRESHOLD 的值決定的。而當桶中節(jié)點數(shù)由于移除或者 resize 變少后，又會變回普通的鏈表的形式，以便節(jié)省空間。

通過查看源碼可以發(fā)現(xiàn)，默認是鏈表長度達到 8 就轉成紅黑樹，而當長度降到 6 就轉換回去，這體現(xiàn)了時間和空間平衡的思想，最開始使用鏈表的時候，空間占用是比較少的，而且由于鏈表短，所以查詢時間也沒有太大的問題?？墒钱旀湵碓絹碓介L，需要用紅黑樹的形式來保證查詢的效率。對于何時應該從鏈表轉化為紅黑樹，需要確定一個閾值，這個閾值默認為 8，并且在源碼中也對選擇 8 這個數(shù)字做了說明，原文如下：

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 分布良好，也就是 hash 計算的結果離散好的話，那么紅黑樹這種形式是很少會被用到的，因為各個值都均勻分布，很少出現(xiàn)鏈表很長的情況。在理想情況下，鏈表長度符合泊松分布，各個長度的命中概率依次遞減，當長度為 8 的時候，概率僅為 0.00000006。這是一個小于千萬分之一的概率，通常我們的 Map 里面是不會存儲這么多的數(shù)據(jù)的，所以通常情況下，并不會發(fā)生從鏈表向紅黑樹的轉換。這也是閾值要默認設置為 8 的原因。

出現(xiàn)紅黑樹的情況

盡管通常情況下，并不會發(fā)生從鏈表向紅黑樹的轉換。但是HashMap 決定某一個元素落到哪一個桶里，是和這個對象的 hashCode 有關的，JDK 并不能阻止我們用戶實現(xiàn)自己的哈希算法，如果我們故意把哈希算法變得不均勻，例如：

/**
 * @discription 演示hashmap結構從鏈表向紅黑樹的轉換的情況
 */
public class HashMapDemo {

    public static void main(String[] args) {
        HashMap map = new HashMap<HashMapDemo,Integer>(1);
        for (int i = 0; i < 1000; i++) {
            HashMapDemo tmpHashMap = new HashMapDemo();
            map.put(tmpHashMap, null);
        }
        System.out.println("運行結束");
    }

    @Override
    public int hashCode() {
        return 1;
    }
}

代碼中新建了一個 HashMap，并且不停地往里放入值，所放入的 key 的對象，它的 hashCode 是被重寫過得，并且始終返回 1。這段代碼運行時，如果通過 debug 讓程序暫停在 System.out.println("運行結束") 這行語句，我們觀察 map 內的節(jié)點，可以發(fā)現(xiàn)已經變成了 TreeNode，而不是通常的 Node，這說明內部已經轉為了紅黑樹。

實際上，鏈表長度超過 8 就轉為紅黑樹的設計，更多的是為了防止用戶自己實現(xiàn)了不好的哈希算法時導致鏈表過長，從而導致查詢效率低，而此時轉為紅黑樹更多的是一種保底策略，用來保證極端情況下查詢的效率。

到此，相信大家對“Map桶中超過8個才轉為紅黑樹的原因是什么”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續(xù)學習！