本篇內(nèi)容主要講解“Map桶中超過8個才轉(zhuǎn)為紅黑樹的原因是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Map桶中超過8個才轉(zhuǎn)為紅黑樹的原因是什么”吧!
創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站制作、成都網(wǎng)站建設(shè)與策劃設(shè)計,廣東網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:廣東等地區(qū)。廣東做網(wǎng)站價格咨詢:13518219792
JDK 1.8 的 HashMap 和 ConcurrentHashMap 都有這樣一個特點：最開始的 Map 是空的，因為里面沒有任何元素，往里放元素時會計算 hash 值，計算之后，第 1 個 value 會首先占用一個桶（也稱為槽點）位置，后續(xù)如果經(jīng)過計算發(fā)現(xiàn)需要落到同一個桶中，那么便會使用鏈表的形式往后延長，俗稱“拉鏈法”，如圖所示：
當(dāng)鏈表長度大于或等于閾值（默認(rèn)為 8）的時候，如果同時還滿足容量大于或等于 MIN_TREEIFY_CAPACITY（默認(rèn)為 64）的要求，就會把鏈表轉(zhuǎn)換為紅黑樹。同樣，后續(xù)如果由于刪除或者其他原因調(diào)整了大小，當(dāng)紅黑樹的節(jié)點小于或等于 6 個以后，又會恢復(fù)為鏈表形態(tài)。如下圖：
在圖中我們可以看到，有一些槽點是空的，有一些是拉鏈，有一些是紅黑樹。
那首先我們就要知道為什么要轉(zhuǎn)換，因為轉(zhuǎn)換是第一步。
每次遍歷一個鏈表，平均查找的時間復(fù)雜度是 O(n)，n 是鏈表的長度。紅黑樹有和鏈表不一樣的查找性能，由于紅黑樹有自平衡的特點，可以防止不平衡情況的發(fā)生，所以可以始終將查找的時間復(fù)雜度控制在 O(log(n))。最初鏈表還不是很長，所以可能 O(n) 和 O(log(n)) 的區(qū)別不大，但是如果鏈表越來越長，那么這種區(qū)別便會有所體現(xiàn)。所以為了提升查找性能，需要把鏈表轉(zhuǎn)化為紅黑樹的形式。
那為什么不一開始就用紅黑樹，反而要經(jīng)歷一個轉(zhuǎn)換的過程呢？
在 JDK 的源碼注釋中已經(jīng)對這個問題作了解釋：
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 的兩倍，所以只有當(dāng)包含足夠多的 Nodes 時才會轉(zhuǎn)成 TreeNodes，而是否足夠多就是由 TREEIFY_THRESHOLD 的值決定的。而當(dāng)桶中節(jié)點數(shù)由于移除或者 resize 變少后，又會變回普通的鏈表的形式，以便節(jié)省空間。
通過查看源碼可以發(fā)現(xiàn)，默認(rèn)是鏈表長度達(dá)到 8 就轉(zhuǎn)成紅黑樹，而當(dāng)長度降到 6 就轉(zhuǎn)換回去，這體現(xiàn)了時間和空間平衡的思想，最開始使用鏈表的時候，空間占用是比較少的，而且由于鏈表短，所以查詢時間也沒有太大的問題?？墒钱?dāng)鏈表越來越長，需要用紅黑樹的形式來保證查詢的效率。對于何時應(yīng)該從鏈表轉(zhuǎn)化為紅黑樹，需要確定一個閾值，這個閾值默認(rèn)為 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 計算的結(jié)果離散好的話，那么紅黑樹這種形式是很少會被用到的，因為各個值都均勻分布，很少出現(xiàn)鏈表很長的情況。在理想情況下，鏈表長度符合泊松分布，各個長度的命中概率依次遞減，當(dāng)長度為 8 的時候，概率僅為 0.00000006。這是一個小于千萬分之一的概率，通常我們的 Map 里面是不會存儲這么多的數(shù)據(jù)的，所以通常情況下，并不會發(fā)生從鏈表向紅黑樹的轉(zhuǎn)換。這也是閾值要默認(rèn)設(shè)置為 8 的原因。
盡管通常情況下，并不會發(fā)生從鏈表向紅黑樹的轉(zhuǎn)換。但是HashMap 決定某一個元素落到哪一個桶里，是和這個對象的 hashCode 有關(guān)的，JDK 并不能阻止我們用戶實現(xiàn)自己的哈希算法，如果我們故意把哈希算法變得不均勻，例如：
重慶分公司
重慶分公司
/**
* @discription 演示hashmap結(jié)構(gòu)從鏈表向紅黑樹的轉(zhuǎn)換的情況
*/
public class HashMapDemo {
public static void main(String[] args) {
HashMap map = new HashMap(1);
for (int i = 0; i < 1000; i++) {
HashMapDemo tmpHashMap = new HashMapDemo();
map.put(tmpHashMap, null);
}
System.out.println("運(yùn)行結(jié)束");
}
@Override
public int hashCode() {
return 1;
}
} 代碼中新建了一個 HashMap，并且不停地往里放入值，所放入的 key 的對象，它的 hashCode 是被重寫過得，并且始終返回 1。這段代碼運(yùn)行時，如果通過 debug 讓程序暫停在 System.out.println("運(yùn)行結(jié)束") 這行語句，我們觀察 map 內(nèi)的節(jié)點，可以發(fā)現(xiàn)已經(jīng)變成了 TreeNode，而不是通常的 Node，這說明內(nèi)部已經(jīng)轉(zhuǎn)為了紅黑樹。
實際上，鏈表長度超過 8 就轉(zhuǎn)為紅黑樹的設(shè)計，更多的是為了防止用戶自己實現(xiàn)了不好的哈希算法時導(dǎo)致鏈表過長，從而導(dǎo)致查詢效率低，而此時轉(zhuǎn)為紅黑樹更多的是一種保底策略，用來保證極端情況下查詢的效率。
到此，相信大家對“Map桶中超過8個才轉(zhuǎn)為紅黑樹的原因是什么”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！
