引言

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

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

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

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

HashMap 的基本構(gòu)造

1. 底層數(shù)據(jù)結(jié)構(gòu)

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

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

2. 核心字段

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

• 容量（capacity）：數(shù)組的大小，默認(rèn)是16；
• 負(fù)載因子（loadFactor）：控制數(shù)組什么時候擴(kuò)容，默認(rèn)是0.75；
• 閾值（threshold）：容量 × 負(fù)載因子，當(dāng)元素個數(shù)超過這個值時，就需要擴(kuò)容。

如何存儲數(shù)據(jù)？

當(dāng)我們調(diào)用 put(K key, V value) 方法時，HashMap 會經(jīng)歷以下幾個步驟：

1. 計算哈希值

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

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

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

2. 定位桶（Bucket）

找到數(shù)組的對應(yīng)位置，查看這個位置上是否已經(jīng)有數(shù)據(jù)：

• 如果沒有數(shù)據(jù)，直接存儲；
• 如果已經(jīng)有數(shù)據(jù)，則發(fā)生了哈希沖突。

3. 解決哈希沖突

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

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

4. 插入數(shù)據(jù)

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

如何取出數(shù)據(jù)？

當(dāng)我們調(diào)用 get(K key) 方法時，HashMap 會進(jìn)行以下操作：

1. 再次計算哈希值

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

2. 查找桶內(nèi)數(shù)據(jù)

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

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

擴(kuò)容機(jī)制

當(dāng) HashMap 的元素數(shù)量超過閾值（capacity × loadFactor）時，就會觸發(fā)擴(kuò)容：

• 數(shù)組的大小變?yōu)樵瓉淼膬杀叮?/li>
• 重新計算每個鍵值對的哈希值，并放入新的數(shù)組中。

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

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

當(dāng)你講完上述內(nèi)容，面試官可能會進(jìn)一步問你一些細(xì)節(jié)問題：

1. 為什么數(shù)組大小是2的冪次？

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

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

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

3. HashMap 是線程安全的嗎？

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

故事的結(jié)尾：小技巧

最后，分享幾個關(guān)于 HashMap 的小技巧：

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