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

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

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

在 JDK 1.8 時(shí)，HashMap 如下圖所示：

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

鏈表升級(jí)為紅黑樹(shù)

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

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

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

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

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

紅黑樹(shù)退化為鏈表

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

• 從紅黑樹(shù)的根節(jié)點(diǎn)開(kāi)始，按照中序遍歷的順序?qū)⑺泄?jié)點(diǎn)加入到一個(gè)新的鏈表中。

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

小結(jié)

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

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

最新評(píng)論