引言

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

故事的開(kāi)頭：一個(gè)簡(jiǎn)單的需求

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

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

HashMap 的基本構(gòu)造

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

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

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

2. 核心字段

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

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

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

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

1. 計(jì)算哈希值

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

為什么不用取模，而用位運(yùn)算呢？

因?yàn)槲贿\(yùn)算比取模快很多，尤其是在需要高性能的場(chǎng)景下。

2. 定位桶（Bucket）

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

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

3. 解決哈希沖突

哈希沖突是不可避免的，HashMap 通過(guò)兩種方式來(lái)解決：

• 鏈表：在同一個(gè)索引處存儲(chǔ)多個(gè)鍵值對(duì)；
• 紅黑樹(shù)：當(dāng)鏈表的長(zhǎng)度超過(guò)8時(shí)，會(huì)轉(zhuǎn)化為紅黑樹(shù)，提升查找效率。

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

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

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

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

1. 再次計(jì)算哈希值

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

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

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

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

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

當(dāng) HashMap 的元素?cái)?shù)量超過(guò)閾值（capacity × loadFactor）時(shí)，就會(huì)觸發(fā)擴(kuò)容：

• 數(shù)組的大小變?yōu)樵瓉?lái)的兩倍；
• 重新計(jì)算每個(gè)鍵值對(duì)的哈希值，并放入新的數(shù)組中。

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

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

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

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

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

2. 紅黑樹(shù)是如何提高效率的？

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

3. HashMap 是線程安全的嗎？

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

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

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

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