圖片

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

PART.01數據結構：數組 + 鏈表 + 紅黑樹

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

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

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

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

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

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

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

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

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

PART.03put方法的過程

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

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

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

如果已經有節點，說明發生了哈希沖突，進入下一步判斷。

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

PART.04哈希函數：擾動函數與hash計算

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

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

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

PART.05JDK1.7與JDK1.8的區別

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

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

END

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

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