圖片

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

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

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

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

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

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

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

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

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

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

• 使用位運算&替代取模操作，效率更高。

PART.03put方法的過程

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

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

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

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

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

PART.04哈希函數(shù)：擾動函數(shù)與hash計算

HashMap的哈希函數(shù)不僅僅是簡單地用key.hashCode()來決定索引位置，因為直接使用hashCode()的低效與不均勻會導致大量哈希碰撞。因此，HashMap采用了一種“擾動函數(shù)”來優(yōu)化哈希值的計算過程。

• HashMap在計算key的哈希值時，先對key的hashCode()進行一次擾動，將hashCode的高16位和低16位進行異或運算。
• 這個“擾動”能讓哈希結果更加均勻分布，盡可能地減少哈希碰撞。

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

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

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

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

END

好了，這就是HashMap的底層設計和實現(xiàn)原理，學會這些知識之后，再遇到關于HashMap的面試題，你一定可以輕松應對！

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