引言

Hi，大家好，我是小米，一個喜歡分享技術的29歲程序員。今天和大家聊聊一個在Java面試中非常經典的問題：“說一下 HashMap 的實現原理？”。別著急，我會用講故事的方式，把它掰開了揉碎了講清楚，讓你聽完之后，再也不怕這個問題！

故事的開頭：一個簡單的需求

一天，產品經理找到你，說用戶需要存儲一組“鍵值對”，并且希望能通過“鍵”快速找到對應的“值”。作為一個有經驗的開發者，你第一時間就想到了Java里的HashMap，對吧？

HashMap 就像是一個超級高效的存儲工具，它的核心理念是：通過哈希算法定位存儲位置，快速存取數據。接下來，我們就一起探討它的實現原理。

HashMap 的基本構造

1. 底層數據結構

HashMap 的底層是由一個數組和多個鏈表/紅黑樹組成的。這種結構有個專業名詞，叫做“拉鏈法”。我們可以把它想象成一個巨大的倉庫，里面有許多貨架，每個貨架上又掛了很多小籃子：

• 數組：倉庫的貨架，負責存儲數據的入口；
• 鏈表/紅黑樹：每個籃子，存儲可能沖突的鍵值對。

2. 核心字段

HashMap 有幾個非常重要的字段，分別是：

• 容量（capacity）：數組的大小，默認是16；
• 負載因子（loadFactor）：控制數組什么時候擴容，默認是0.75；
• 閾值（threshold）：容量 × 負載因子，當元素個數超過這個值時，就需要擴容。

如何存儲數據？

當我們調用 put(K key, V value) 方法時，HashMap 會經歷以下幾個步驟：

1. 計算哈希值

通過 key 的 hashCode() 方法計算哈希值，并通過一個位運算 h & (n - 1) 確定該數據應該存儲到數組的哪個索引上。

為什么不用取模，而用位運算呢？

因為位運算比取?？旌芏?，尤其是在需要高性能的場景下。

2. 定位桶（Bucket）

找到數組的對應位置，查看這個位置上是否已經有數據：

• 如果沒有數據，直接存儲；
• 如果已經有數據，則發生了哈希沖突。

3. 解決哈希沖突

哈希沖突是不可避免的，HashMap 通過兩種方式來解決：

• 鏈表：在同一個索引處存儲多個鍵值對；
• 紅黑樹：當鏈表的長度超過8時，會轉化為紅黑樹，提升查找效率。

4. 插入數據

將新的鍵值對插入到對應的鏈表或紅黑樹中。如果 key 已經存在，會覆蓋舊的 value。

如何取出數據？

當我們調用 get(K key) 方法時，HashMap 會進行以下操作：

1. 再次計算哈希值

通過 key 的 hashCode() 方法計算哈希值，定位到數組的某個索引。

2. 查找桶內數據

• 進入桶中，依次遍歷鏈表或紅黑樹：
• 如果找到對應的 key，就返回 value；
• 如果遍歷完沒有找到，返回 null。

注意：這里的 key 比較是通過 equals() 方法完成的。

擴容機制

當 HashMap 的元素數量超過閾值（capacity × loadFactor）時，就會觸發擴容：

• 數組的大小變為原來的兩倍；
• 重新計算每個鍵值對的哈希值，并放入新的數組中。

擴容是個性能開銷較大的操作，所以在使用 HashMap 時，我們通常會預估大小，盡量減少擴容次數。

故事的高潮：面試官的深挖

當你講完上述內容，面試官可能會進一步問你一些細節問題：

1. 為什么數組大小是2的冪次？

因為 h & (n - 1) 的位運算只有在數組大小是2的冪次時，才能均勻分布哈希值，減少沖突。

2. 紅黑樹是如何提高效率的？

鏈表的時間復雜度是 O(n)，而紅黑樹的查找復雜度是 O(log n)。當鏈表太長時（超過8），會自動轉化為紅黑樹，顯著提高查找效率。

3. HashMap 是線程安全的嗎？

HashMap 不是線程安全的。如果在多線程環境下使用，可以考慮使用 ConcurrentHashMap。

故事的結尾：小技巧

最后，分享幾個關于 HashMap 的小技巧：

• 合理設置初始容量：避免頻繁擴容，提升性能；
• 重寫 hashCode() 和 equals() 方法：確保鍵的哈希值均勻分布，減少沖突；
• 多線程場景用 ConcurrentHashMap：避免線程安全問題。