HashMap鏈表與紅黑樹轉(zhuǎn)換詳解
鏈表轉(zhuǎn)換為紅黑樹
//此處遍歷鏈表 for (int binCount = 0; ; ++binCount) { //遍歷到鏈表最后一個(gè)節(jié)點(diǎn) if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //如果鏈表元素個(gè)數(shù)大于等于TREEIFY_THRESHOLD if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //紅黑樹轉(zhuǎn)換邏輯 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; }
static final int MIN_TREEIFY_CAPACITY = 64; static final int UNTREEIFY_THRESHOLD = 6; /** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }
可以看到在treeifyBin中并不是簡(jiǎn)單地將鏈表轉(zhuǎn)換為紅黑樹,而是先判斷table的長(zhǎng)度是否大于64,如果小于64,就通過擴(kuò)容的方式來解決,避免紅黑樹結(jié)構(gòu)化. 個(gè)人覺得鏈表長(zhǎng)度大于8有兩種情況:
- table長(zhǎng)度足夠,hash沖突過多
- table長(zhǎng)度太小,但是在計(jì)算table下標(biāo)的時(shí)候,導(dǎo)致很多hash不一致的key計(jì)算的下標(biāo)一致
所以擴(kuò)容后鏈表長(zhǎng)度變短,讀寫效率自然提高。另外,擴(kuò)容相對(duì)于轉(zhuǎn)換為紅黑樹的好處在于可以保證數(shù)據(jù)結(jié)構(gòu)更簡(jiǎn)單。并不是鏈表長(zhǎng)度超過8就一定會(huì)轉(zhuǎn)換成紅黑樹,而是先嘗試擴(kuò)容。
紅黑樹轉(zhuǎn)換為鏈表
基本思想是當(dāng)紅黑樹中的元素減少并小于一定數(shù)量時(shí),會(huì)切換回鏈表。
而元素減少有兩種情況:
- 調(diào)用map的remove方法刪除元素
- resize的時(shí)候,對(duì)紅黑樹進(jìn)行了拆分
1、hashMap的remove方法,會(huì)進(jìn)入到removeNode方法,找到要?jiǎng)h除的節(jié)點(diǎn),并判斷node類型是否為treeNode,然后進(jìn)入刪除紅黑樹節(jié)點(diǎn)邏輯的removeTreeNode方法中,該方法有關(guān)解除紅黑樹結(jié)構(gòu)的分支如下
//判斷是否要解除紅黑樹的條件 if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) { tab[index] = first.untreeify(map); // too small return; }
此時(shí)是通過紅黑樹根節(jié)點(diǎn)及其子節(jié)點(diǎn)是否為空來判斷,而滿足該條件的最大紅黑樹結(jié)構(gòu)如下:
節(jié)點(diǎn)數(shù)為10,大于 UNTREEIFY_THRESHOLD(6),但是根據(jù)該方法的邏輯判斷,是需要轉(zhuǎn)換為鏈表的
2、resize的時(shí)候,判斷節(jié)點(diǎn)類型,如果是鏈表,則將鏈表拆分,如果是TreeNode,則執(zhí)行TreeNode的split方法分割紅黑樹,而split方法中將紅黑樹轉(zhuǎn)換為鏈表的分支如下
//在這之前的邏輯是將紅黑樹每個(gè)節(jié)點(diǎn)的hash和一個(gè)bit進(jìn)行&運(yùn)算, //根據(jù)運(yùn)算結(jié)果將樹劃分為兩棵紅黑樹,lc表示其中一棵樹的節(jié)點(diǎn)數(shù) if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) // (else is already treeified) loHead.treeify(tab); }
這里才用到了 UNTREEIFY_THRESHOLD 的判斷,當(dāng)紅黑樹節(jié)點(diǎn)元素小于等于6時(shí),才調(diào)用untreeify方法轉(zhuǎn)換回鏈表
總結(jié)
1、hashMap并不是在鏈表元素個(gè)數(shù)大于8就一定會(huì)轉(zhuǎn)換為紅黑樹,而是先考慮擴(kuò)容,擴(kuò)容達(dá)到默認(rèn)限制后才轉(zhuǎn)換
2、hashMap的紅黑樹不一定小于6的時(shí)候才會(huì)轉(zhuǎn)換為鏈表,而是只有在resize的時(shí)候才會(huì)根據(jù) UNTREEIFY_THRESHOLD 進(jìn)行轉(zhuǎn)換。
到此這篇關(guān)于HashMap鏈表與紅黑樹轉(zhuǎn)換詳解的文章就介紹到這了,更多相關(guān)HashMap鏈表轉(zhuǎn)換內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java中timer的schedule和scheduleAtFixedRate方法區(qū)別詳解
這篇文章主要為大家詳細(xì)介紹了java中timer的schedule和scheduleAtFixedRate方法區(qū)別,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-12-12RestTemplate如何添加請(qǐng)求頭headers和請(qǐng)求體body
這篇文章主要介紹了RestTemplate如何添加請(qǐng)求頭headers和請(qǐng)求體body問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-07-07SpringCloud之LoadBalancer負(fù)載均衡服務(wù)調(diào)用過程
這篇文章主要介紹了SpringCloud之LoadBalancer負(fù)載均衡服務(wù)調(diào)用過程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2025-03-03Spring Cloud Gateway 獲取請(qǐng)求體(Request Body)的多種方法
這篇文章主要介紹了Spring Cloud Gateway 獲取請(qǐng)求體(Request Body)的多種方法,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-01-01java實(shí)現(xiàn)字符串四則運(yùn)算公式解析工具類的方法
今天小編就為大家分享一篇java實(shí)現(xiàn)字符串四則運(yùn)算公式解析工具類的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-07-07淺談SpringCloud feign的http請(qǐng)求組件優(yōu)化方案
這篇文章主要介紹了淺談SpringCloud feign的http請(qǐng)求組件優(yōu)化方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2021-02-02Java中快速排序優(yōu)化技巧之隨機(jī)取樣、三數(shù)取中和插入排序
快速排序是一種常用的基于比較的排序算法,下面這篇文章主要給大家介紹了關(guān)于Java中快速排序優(yōu)化技巧之隨機(jī)取樣、三數(shù)取中和插入排序的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-09-09