一、前提說(shuō)明本文討論的擴(kuò)容特指HashMap 完成初始化之后因新增元素導(dǎo)致 size 超過(guò)閾值而觸發(fā)的擴(kuò)容過(guò)程不包含第一次創(chuàng)建內(nèi)部數(shù)組的情況。JDK 7 與 JDK 8 在這一時(shí)機(jī)的處理邏輯存在根本性差異背后的設(shè)計(jì)思想也大不相同。二、JDK 7先擴(kuò)容再插入2.1 執(zhí)行流程JDK 7 在插入新節(jié)點(diǎn)前會(huì)進(jìn)行一個(gè)雙重判斷當(dāng)前元素?cái)?shù)量是否已達(dá)到擴(kuò)容閾值size threshold待插入的新節(jié)點(diǎn)所在的桶是否已有元素即是否發(fā)生哈希沖突。只有兩個(gè)條件同時(shí)滿足時(shí)才會(huì)先執(zhí)行擴(kuò)容再將新節(jié)點(diǎn)插入擴(kuò)容后的空數(shù)組。如果目標(biāo)桶為空即使 size 已經(jīng)達(dá)到閾值也不會(huì)立即擴(kuò)容而是直接把新節(jié)點(diǎn)放進(jìn)空桶。// JDK 7 插入邏輯簡(jiǎn)化示意if (size threshold table[bucketIndex] ! null) {resize(); // 擴(kuò)容bucketIndex indexFor(hash, table.length); // 重新計(jì)算下標(biāo)}addEntry(...); // 插入新節(jié)點(diǎn)2.2 優(yōu)點(diǎn)避免新節(jié)點(diǎn)重復(fù)遷移新節(jié)點(diǎn)不會(huì)先放入舊數(shù)組、再馬上參與數(shù)據(jù)遷移減少了不必要的搬運(yùn)開(kāi)銷(xiāo)?？胀皥?chǎng)景下的內(nèi)存節(jié)省當(dāng)新節(jié)點(diǎn)落入空桶時(shí)暫不擴(kuò)容可以在哈希沖突較少時(shí)延遲數(shù)組分配一定程度上節(jié)約內(nèi)存。2.3 缺點(diǎn)擴(kuò)容規(guī)則不夠統(tǒng)一是否觸發(fā)擴(kuò)容不僅取決于size和threshold還與目標(biāo)桶是否為空相關(guān)。兩個(gè)容量相同、元素?cái)?shù)量相同的 HashMap可能僅僅因?yàn)樾鹿?jié)點(diǎn)落入的桶不同一個(gè)觸發(fā)擴(kuò)容而另一個(gè)不擴(kuò)容。這導(dǎo)致擴(kuò)容行為不易預(yù)測(cè)負(fù)載因子的語(yǔ)義也被弱化。插入流程復(fù)雜化提前擴(kuò)容后由于數(shù)組長(zhǎng)度改變需要重新計(jì)算新節(jié)點(diǎn)的存儲(chǔ)位置增加了插入路徑的復(fù)雜度。三、JDK 8先插入確認(rèn)新增后再擴(kuò)容3.1 執(zhí)行流程JDK 8 將擴(kuò)容判斷后置先完成桶內(nèi)查找與插入可能是鏈表追加或紅黑樹(shù)插入若本次插入確實(shí)是一個(gè)新鍵非覆蓋舊值則size加 1若插入后的size threshold觸發(fā)擴(kuò)容。// JDK 8 插入邏輯簡(jiǎn)化示意NodeK,V e ...; // 在桶中完成查找/插入if (e null) { // 新增鍵size;if (size threshold)resize();}afterNodeInsertion(evict); // 回調(diào)3.2 優(yōu)點(diǎn)1. 擴(kuò)容條件更清晰、統(tǒng)一是否擴(kuò)容完全由size threshold決定不再依賴新節(jié)點(diǎn)是否落入空桶。負(fù)載因子成為真正意義上的“容量飽和度”指標(biāo)語(yǔ)義明確行為可預(yù)測(cè)。2. 僅新增鍵時(shí)觸發(fā)擴(kuò)容如果調(diào)用put的 key 已存在僅僅覆蓋舊值size保持不變自然也不會(huì)引發(fā)擴(kuò)容避免了無(wú)意義的數(shù)組重建。3. 與紅黑樹(shù)機(jī)制無(wú)縫配合JDK 8 引入了“鏈表轉(zhuǎn)紅黑樹(shù)”的優(yōu)化。采用“先完成桶內(nèi)部操作再統(tǒng)一處理樹(shù)化、size 更新和擴(kuò)容判斷”的流程代碼結(jié)構(gòu)更加一致邏輯內(nèi)聚便于維護(hù)。4. 擴(kuò)容遷移代價(jià)降低使后置擴(kuò)容可行JDK 8 的遷移算法做了關(guān)鍵優(yōu)化因?yàn)閿?shù)組容量按 2 倍擴(kuò)展節(jié)點(diǎn)在新數(shù)組中的下標(biāo)只有兩種可能——保持原下標(biāo)或原下標(biāo) 舊容量。只需判斷節(jié)點(diǎn)哈希值中與oldCap對(duì)應(yīng)的那一位即可將原鏈表拆分為“高位鏈”和“低位鏈”無(wú)需重新計(jì)算完整哈希下標(biāo)。因此即使新節(jié)點(diǎn)剛剛插入舊數(shù)組就立即參與一次遷移額外成本也遠(yuǎn)低于 JDK 7這使得“先插入后擴(kuò)容”的設(shè)計(jì)在性能上完全可接受。// JDK 8 擴(kuò)容拆分示意NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;for (NodeK,V e oldTab[j]; e ! null; e e.next) {if ((e.hash oldCap) 0) {// 保留在原下標(biāo)} else {// 移動(dòng)到 原下標(biāo) oldCap}}3.3 缺點(diǎn)臨界場(chǎng)景下的重復(fù)遷移新節(jié)點(diǎn)可能剛剛放入舊數(shù)組就因?yàn)閿U(kuò)容被再次遷移發(fā)生一次“無(wú)用搬運(yùn)”。不再因空桶而延遲擴(kuò)容JDK 8 丟棄了“目標(biāo)桶為空則不擴(kuò)容”的優(yōu)化只要 size 超過(guò)閾值就會(huì)立即擴(kuò)容可能比 JDK 7 更早分配更大的數(shù)組在內(nèi)存敏感的場(chǎng)景下略顯激進(jìn)。四、設(shè)計(jì)取舍總結(jié)JDK 7 與 JDK 8 在擴(kuò)容時(shí)機(jī)上的差異本質(zhì)上是一組設(shè)計(jì)取舍JDK 7 偏向局部?jī)?yōu)化盡量避免新節(jié)點(diǎn)的重復(fù)遷移同時(shí)在沖突較少時(shí)通過(guò)延遲擴(kuò)容來(lái)節(jié)省內(nèi)存。代價(jià)是擴(kuò)容條件復(fù)雜化、行為不一致代碼邏輯耦合度高。JDK 8 追求全局統(tǒng)一與可維護(hù)性用一次可能的額外遷移換取了擴(kuò)容規(guī)則的純粹與統(tǒng)一負(fù)載因子語(yǔ)義的嚴(yán)格保證與紅黑樹(shù)機(jī)制的和諧共生更清晰的代碼結(jié)構(gòu)與更可預(yù)測(cè)的性能表現(xiàn)因此不能簡(jiǎn)單地說(shuō) JDK 8 的“先插入再擴(kuò)容”就一定更快。更準(zhǔn)確的理解是正是因?yàn)?JDK 8 優(yōu)化了遷移算法2 倍擴(kuò)容下標(biāo)二選一并引入了紅黑樹(shù)等新結(jié)構(gòu)“先插入、確認(rèn) size 增加后再統(tǒng)一擴(kuò)容”才成為更合適的設(shè)計(jì)選擇。這也是 JDK 在不斷演進(jìn)中根據(jù)內(nèi)部機(jī)制的變化對(duì)同一問(wèn)題給出的不同最優(yōu)解。五、對(duì)比一覽維度JDK 7JDK 8擴(kuò)容時(shí)機(jī)插入前size≥閾值且桶非空插入后新增鍵且 size閾值擴(kuò)容規(guī)則依賴哈希沖突情況不夠統(tǒng)一純粹依賴 size 與閾值統(tǒng)一清晰新節(jié)點(diǎn)遷移避免重復(fù)遷移可能剛插入就遷移一次空桶行為可延遲擴(kuò)容節(jié)省內(nèi)存不再延遲size 超閾值必?cái)U(kuò)容遷移算法重新計(jì)算所有節(jié)點(diǎn)下標(biāo)只需拆分高位/低位鏈表代碼復(fù)雜度插入路徑分支多邏輯統(tǒng)一樹(shù)化與擴(kuò)容分離配合機(jī)制純鏈表鏈表 紅黑樹(shù)理解這些差異有助于我們?cè)诓煌膽?yīng)用場(chǎng)景中更合理地評(píng)估 HashMap 的性能表現(xiàn)同時(shí)也體現(xiàn)了 JDK 設(shè)計(jì)團(tuán)隊(duì)在性能、語(yǔ)義與可維護(hù)性之間的精妙平衡。