HashMap 在不同的 JDK 版本下的實現(xiàn)是不同的，在 JDK 1.7 時，HashMap 底層是通過數(shù)組 + 鏈表實現(xiàn)的；而在 JDK 1.8 時，HashMap 底層是通過數(shù)組 + 鏈表或紅黑樹實現(xiàn)的。

具體來說，HashMap 內(nèi)部維護(hù)了一個數(shù)組，每個數(shù)組元素又是一個鏈表或者紅黑樹，每個鏈表或者紅黑樹節(jié)點存儲了一個鍵值對。當(dāng)需要存儲新的鍵值對時，HashMap 會根據(jù)鍵的哈希值確定其在數(shù)組中的位置，如果該位置已經(jīng)有了其他鍵值對，則通過鏈表或紅黑樹解決沖突，將新的鍵值對添加到鏈表或紅黑樹的末尾。當(dāng)鏈表或紅黑樹長度達(dá)到一定程度后，HashMap 會自動將鏈表轉(zhuǎn)換為紅黑樹，以提高查找效率。

如下圖所示，HashMap 在 JDK 1.7 中的實現(xiàn)如下圖所示：

在 JDK 1.8 時，HashMap 如下圖所示：

鏈表和紅黑樹互轉(zhuǎn)流程

鏈表升級為紅黑樹

在 JDK 1.8 之后，HashMap 默認(rèn)是先使用數(shù)組 + 鏈表存儲數(shù)據(jù)，但當(dāng)滿足以下兩個條件時：

• 鏈表的數(shù)量大于閾值（默認(rèn)是 8）
• 并且數(shù)組長度大于 64 時

為了（查詢）的性能考慮會將鏈表升級為紅黑樹進(jìn)行存儲，具體執(zhí)行流程如下：

• 創(chuàng)建新的紅黑樹對象，并將鏈表內(nèi)所有的鍵值對全部添加到紅黑樹中。

• 將原來的鏈表引用指向新創(chuàng)建的紅黑樹。

紅黑樹退化為鏈表

當(dāng)進(jìn)行了刪除操作，導(dǎo)致紅黑樹的節(jié)點小于等于 6 時，會發(fā)生退化，將紅黑樹轉(zhuǎn)換為鏈表。這是因為當(dāng)節(jié)點數(shù)量較少時，紅黑樹對性能的提升并不明顯，反而占用了更多的內(nèi)存空間。具體執(zhí)行流程如下：

• 從紅黑樹的根節(jié)點開始，按照中序遍歷的順序?qū)⑺泄?jié)點加入到一個新的鏈表中。

• 將原來的紅黑樹引用指向新創(chuàng)建的鏈表。

小結(jié)

HashMap 在 JDK 1.7 時，是通過數(shù)組 + 鏈表實現(xiàn)的，而在 JDK 1.8 時，HashMap 是通過數(shù)組 + 鏈表或紅黑樹實現(xiàn)的。在 JDK 1.8 之后，如果鏈表的數(shù)量大于閾值（默認(rèn)為 8），并且數(shù)組長度大于 64 時，為了查詢效率會將鏈表升級為紅黑樹，但當(dāng)紅黑樹的節(jié)點小于等于 6 時，為了節(jié)省內(nèi)存空間會將紅黑樹退化為鏈表。

到此這篇關(guān)于Java HashMap底層實現(xiàn)原理的文章就介紹到這了,更多相關(guān)HashMap 底層實現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論