圖片

哈嘍大家好！今天咱們來聊聊Java中最經(jīng)典的數(shù)據(jù)結(jié)構(gòu)之一——HashMap！如果你是Java開發(fā)者，那你一定對(duì)它不陌生。HashMap 是我們進(jìn)行鍵值對(duì)存儲(chǔ)的好幫手，幾乎是我們?cè)谌粘ｉ_發(fā)中離不開的工具。本文會(huì)從數(shù)據(jù)結(jié)構(gòu)、擴(kuò)容機(jī)制、put和查找過程、哈希函數(shù)以及JDK 1.7與1.8的差異等多方面，來詳細(xì)拆解一下HashMap的底層原理！Let's go～

PART.01數(shù)據(jù)結(jié)構(gòu)：數(shù)組 + 鏈表 + 紅黑樹

在Java的HashMap中，底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組、鏈表、紅黑樹三者的組合。通過鍵值對(duì)的哈希映射，HashMap可以實(shí)現(xiàn)快速的數(shù)據(jù)存取。那么，HashMap是如何把這三種數(shù)據(jù)結(jié)構(gòu)組合起來的呢？

數(shù)組：這是HashMap的核心存儲(chǔ)空間，稱為table。當(dāng)我們通過key來存取數(shù)據(jù)時(shí)，實(shí)際是把key通過哈希函數(shù)映射到table中的某個(gè)索引位置。

鏈表：在HashMap中，鏈表主要是用來處理哈希沖突的。如果多個(gè)key被映射到了同一個(gè)數(shù)組索引，那么這些沖突的元素會(huì)被放在一個(gè)鏈表中，以鏈表形式存儲(chǔ)。

紅黑樹：在JDK1.8引入了紅黑樹，以優(yōu)化鏈表的查找效率。若一個(gè)索引下的鏈表長(zhǎng)度超過8，并且數(shù)組長(zhǎng)度大于64，HashMap會(huì)將鏈表轉(zhuǎn)換成紅黑樹。這樣可以將查找的時(shí)間復(fù)雜度從O(n)降到O(log n)，大幅度提升性能。

PART.02擴(kuò)容情況：為什么是2的冪次方？

HashMap在擴(kuò)容機(jī)制上也是獨(dú)具匠心。擴(kuò)容不僅影響性能，還會(huì)影響數(shù)據(jù)的分布和哈希碰撞，所以在容量和擴(kuò)容機(jī)制設(shè)計(jì)上，HashMap非常講究。

• 默認(rèn)大小和負(fù)載因子：HashMap的默認(rèn)容量是16，負(fù)載因子是0.75。也就是說，當(dāng)HashMap的填充度超過75%時(shí)，就會(huì)觸發(fā)擴(kuò)容操作，避免因?yàn)檫^多的哈希沖突而降低性能。
• 擴(kuò)容機(jī)制：擴(kuò)容發(fā)生時(shí)，HashMap會(huì)將當(dāng)前容量翻倍，并重新將所有元素重新哈希到新的數(shù)組中。
• 容量始終是2的冪次方：HashMap的容量總是保持2的冪次方。這樣設(shè)計(jì)的原因主要有以下幾點(diǎn)：

2的冪次方可以使(n-1) & hash的運(yùn)算分布更均勻，減少哈希碰撞。

• 使用位運(yùn)算&替代取模操作，效率更高。

PART.03put方法的過程

HashMap的put方法可以說是HashMap的精髓之一，理解它的執(zhí)行過程，有助于我們掌握HashMap的存儲(chǔ)機(jī)制。put方法主要分以下幾個(gè)步驟：

• 判斷table是否為空：如果table為空，HashMap會(huì)進(jìn)行初始化操作，將容量擴(kuò)充為默認(rèn)大小16。
• 計(jì)算hash值和索引位置：通過key的hashCode值經(jīng)過擾動(dòng)函數(shù)處理后，再通過(n - 1) & hash計(jì)算出該元素存放的數(shù)組下標(biāo)index。
• 檢查是否有哈希沖突：檢查table[index]處是否已經(jīng)有節(jié)點(diǎn)。

如果沒有節(jié)點(diǎn)，直接構(gòu)造一個(gè)新的Node節(jié)點(diǎn)放入table[index]處；

如果已經(jīng)有節(jié)點(diǎn)，說明發(fā)生了哈希沖突，進(jìn)入下一步判斷。

• 哈希沖突處理：在處理哈希沖突時(shí)，HashMap通過鏈表和紅黑樹來解決沖突。
• 若現(xiàn)有節(jié)點(diǎn)的key與新節(jié)點(diǎn)的key相同，就會(huì)用新的value覆蓋原有值。
• 如果不相同，檢查現(xiàn)有節(jié)點(diǎn)類型，如果是鏈表節(jié)點(diǎn)，則將新節(jié)點(diǎn)添加到鏈表中；如果鏈表長(zhǎng)度超過閾值8且數(shù)組長(zhǎng)度大于64，會(huì)將鏈表轉(zhuǎn)換為紅黑樹。
• 判斷是否需要擴(kuò)容：當(dāng)插入完成后，HashMap會(huì)檢查當(dāng)前容量是否超過負(fù)載因子0.75的閾值，如果超過則觸發(fā)擴(kuò)容。

PART.04哈希函數(shù)：擾動(dòng)函數(shù)與hash計(jì)算

HashMap的哈希函數(shù)不僅僅是簡(jiǎn)單地用key.hashCode()來決定索引位置，因?yàn)橹苯邮褂胔ashCode()的低效與不均勻會(huì)導(dǎo)致大量哈希碰撞。因此，HashMap采用了一種“擾動(dòng)函數(shù)”來優(yōu)化哈希值的計(jì)算過程。

• HashMap在計(jì)算key的哈希值時(shí)，先對(duì)key的hashCode()進(jìn)行一次擾動(dòng)，將hashCode的高16位和低16位進(jìn)行異或運(yùn)算。
• 這個(gè)“擾動(dòng)”能讓哈希結(jié)果更加均勻分布，盡可能地減少哈希碰撞。

經(jīng)過擾動(dòng)處理后的哈希值，最終會(huì)通過(n - 1) & hash來計(jì)算索引位置，這樣可以確保得到的索引位置始終位于數(shù)組范圍內(nèi)。

PART.05JDK1.7與JDK1.8的區(qū)別

在JDK1.7與JDK1.8之間，HashMap的實(shí)現(xiàn)有一些關(guān)鍵性變化：

• 數(shù)據(jù)結(jié)構(gòu)：JDK1.7中，HashMap采用了“數(shù)組+鏈表”的組合，而JDK1.8中則采用“數(shù)組+鏈表+紅黑樹”三者結(jié)合的結(jié)構(gòu)。在JDK1.8中，當(dāng)鏈表長(zhǎng)度超過8且數(shù)組長(zhǎng)度大于64時(shí)，鏈表會(huì)轉(zhuǎn)化為紅黑樹以優(yōu)化查找性能，避免長(zhǎng)鏈表造成的性能瓶頸。
• hash沖突處理方式：在JDK1.7中，鏈表插入新節(jié)點(diǎn)時(shí)采用的是頭插法，這樣做的好處是插入速度較快，但在并發(fā)情況下可能會(huì)產(chǎn)生死循環(huán)（例如在rehash期間）。而在JDK1.8中，鏈表插入時(shí)采用了尾插法，避免了并發(fā)擴(kuò)容時(shí)死循環(huán)的問題。
• 擴(kuò)容過程：JDK1.8中，HashMap的擴(kuò)容更為智能高效，通過高位運(yùn)算決定節(jié)點(diǎn)位置是否發(fā)生變化。擴(kuò)容時(shí)不再重新計(jì)算所有節(jié)點(diǎn)的哈希值，只需檢查每個(gè)節(jié)點(diǎn)的高位，決定是否需要搬移至新數(shù)組。
• 性能優(yōu)化：JDK1.8的HashMap在多線程環(huán)境下性能優(yōu)化明顯，解決了JDK1.7在并發(fā)條件下擴(kuò)容時(shí)可能導(dǎo)致的死循環(huán)問題?？傮w來看，JDK1.8的HashMap在結(jié)構(gòu)上更為合理，更適用于高并發(fā)場(chǎng)景。

END

好了，這就是HashMap的底層設(shè)計(jì)和實(shí)現(xiàn)原理，學(xué)會(huì)這些知識(shí)之后，再遇到關(guān)于HashMap的面試題，你一定可以輕松應(yīng)對(duì)！

• 底層結(jié)構(gòu)：HashMap采用數(shù)組、鏈表、紅黑樹組合的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)鍵值對(duì)。
• 擴(kuò)容機(jī)制：HashMap默認(rèn)負(fù)載因子為0.75，擴(kuò)容時(shí)容量翻倍，始終保持2的冪次方以提高存儲(chǔ)效率。
• put過程：put方法主要包括判斷初始化、計(jì)算hash值、解決哈希沖突、擴(kuò)容等幾個(gè)步驟。
• 哈希函數(shù)：采用擾動(dòng)函數(shù)，降低哈希碰撞，確保元素均勻分布。
• JDK1.7 vs JDK1.8：1.8引入紅黑樹和尾插法處理沖突，避免了死循環(huán)，提高了多線程環(huán)境的安全性。