作者 | 波哥

作為一名程序員，你可能經(jīng)常使用 HashMap 這個(gè)重要的數(shù)據(jù)結(jié)構(gòu)，但你對(duì)它的底層實(shí)現(xiàn)原理可能不夠了解。本文將通過圖文結(jié)合的方式，為你詳細(xì)解析 HashMap 的底層實(shí)現(xiàn)原理，并回答一些常見問題，讓你能夠更好地理解和應(yīng)用 HashMap。

1. HashMap 概述

HashMap 是 Java 集合框架中最常用的映射表實(shí)現(xiàn)，它提供了鍵值對(duì)的存儲(chǔ)和檢索功能。底層基于數(shù)組和鏈表（或紅黑樹）實(shí)現(xiàn)，通過哈希算法將鍵映射到數(shù)組的索引位置，以實(shí)現(xiàn)快速的插入和查找操作。下面我們來看一下 HashMap 的底層代碼流程圖：

2. HashMap 的主要方法分析

2.1 put方法

put方法用于將鍵值對(duì)插入到 HashMap 中。讓我們看一下put方法的源代碼：

首先，通過has(key)方法計(jì)算鍵的哈希碼，并調(diào)用putVal()方法進(jìn)行插入操作。下面是putVal()方法的源代碼：

putVal()方法的核心是通過哈希碼定位桶，然后在桶中進(jìn)行插入操作。如果桶為空，則直接在桶中插入新節(jié)點(diǎn)。如果桶不為空，則遍歷鏈表或紅黑樹，查找鍵是否已存在。如果鍵已存在，則替換對(duì)應(yīng)的值；如果鍵不存在，則將新節(jié)點(diǎn)插入到鏈表的末尾，并根據(jù)鏈表長度是否達(dá)到閾值來決定是否將鏈表轉(zhuǎn)化為紅黑樹。最后，更新修改次數(shù)和元素?cái)?shù)量，并進(jìn)行必要的操作。

2.2 resize方法

resize方法用于動(dòng)態(tài)擴(kuò)容 HashMap。當(dāng)元素?cái)?shù)量超過閾值時(shí)，HashMap 會(huì)自動(dòng)觸發(fā)擴(kuò)容操作。下面是resize方法的源代碼：

resize方法的主要功能是創(chuàng)建一個(gè)新的數(shù)組，并將所有鍵值對(duì)重新計(jì)算哈希碼和索引位置，然后將它們分配到新的桶中。擴(kuò)容后的容量是原來的兩倍，并根據(jù)負(fù)載因子重新計(jì)算閾值。在轉(zhuǎn)移鍵值對(duì)時(shí)，會(huì)根據(jù)哈希碼的高位來確定是保留在原來的位置還是移動(dòng)到新的位置。如果鏈表長度超過閾值，則會(huì)將鏈表轉(zhuǎn)化為紅黑樹以提高查找效率。

2.3 get方法

當(dāng)我們需要根據(jù)鍵來獲取值時(shí)，可以使用 HashMap 的get(key)方法。下面講解下 HashMap 的get方法的原理。

首先，我們傳入要查找的鍵key，然后通過hash(key)方法計(jì)算鍵的哈希碼。哈希碼被用來確定鍵在 HashMap 中的桶（bucket）位置。根據(jù)哈希碼，我們可以確定鍵在數(shù)組中的索引位置。

接下來，我們?cè)诖_定的索引位置找到對(duì)應(yīng)的桶。如果桶為空，即沒有鍵值對(duì)存在，那么返回 null，表示沒有找到對(duì)應(yīng)的值。

如果桶不為空，那么可能存在多個(gè)鍵值對(duì)，這時(shí)我們需要遍歷鏈表或紅黑樹來找到具有相同鍵的節(jié)點(diǎn)。在遍歷過程中，我們會(huì)使用鍵的 equals() 方法來比較傳入的鍵和當(dāng)前節(jié)點(diǎn)的鍵是否相等。如果找到了相等的鍵，那么返回對(duì)應(yīng)節(jié)點(diǎn)的值。

如果遍歷完整個(gè)鏈表或紅黑樹仍然沒有找到相等的鍵，那么返回 null，表示沒有找到對(duì)應(yīng)的值。

整個(gè)get()方法的原理就是根據(jù)鍵的哈希碼確定索引位置，然后在對(duì)應(yīng)的桶中遍歷鏈表或紅黑樹，通過 equals() 方法比較鍵的相等性來找到對(duì)應(yīng)的值。

以下是get方法的偽代碼示例：

通過分析上述代碼，我們可以看到get方法的實(shí)現(xiàn)流程：首先計(jì)算鍵的哈希碼，然后根據(jù)哈希碼找到對(duì)應(yīng)的桶，最后在桶中遍歷鏈表或紅黑樹，查找具有相同鍵的節(jié)點(diǎn)，如果找到則返回對(duì)應(yīng)的值，否則返回 null。

3. 常見問題分析

3.1為什么哈希碼很重要?

哈希碼在 HashMap 中扮演著重要的角色。它通過哈希函數(shù)將鍵轉(zhuǎn)換為一個(gè)唯一的整數(shù)，決定了鍵值對(duì)在數(shù)組中的存儲(chǔ)位置。如果兩個(gè)鍵的哈希碼不同，它們會(huì)被分配到不同的桶中，提高了查找效率。如果哈希碼相同，就會(huì)發(fā)生哈希沖突，需要進(jìn)一步處理。

3.2如何處理哈希沖突？

當(dāng)兩個(gè)不同的鍵具有相同的哈希碼時(shí)，HashMap 會(huì)使用鏈表或紅黑樹來解決哈希沖突。鏈表是 JDK 8 之前的解決方案，而紅黑樹是 JDK 8 之后的優(yōu)化。HashMap 在桶中通過鏈表或紅黑樹結(jié)構(gòu)存儲(chǔ)沖突的鍵值對(duì)，以便在查找時(shí)能快速定位到正確的鍵值對(duì)。

3.3為什么需要?jiǎng)討B(tài)擴(kuò)容？

動(dòng)態(tài)擴(kuò)容是為了避免哈希沖突過多，提高 HashMap 的性能。當(dāng)鍵值對(duì)的數(shù)量接近數(shù)組容量的閾值時(shí)，HashMap 會(huì)自動(dòng)觸發(fā)擴(kuò)容操作。它創(chuàng)建一個(gè)更大的數(shù)組，并重新計(jì)算每個(gè)鍵的哈希碼和索引位置，然后將鍵值對(duì)重新插入到新數(shù)組中。這樣可以減少桶的數(shù)量，降低哈希沖突的概率，提高存儲(chǔ)和檢索的效率。

3.4如何保證鍵的唯一性？

HashMap 通過哈希碼和鏈表/紅黑樹結(jié)構(gòu)來保證鍵的唯一性。當(dāng)存儲(chǔ)鍵值對(duì)時(shí)，如果發(fā)現(xiàn)相同的鍵已經(jīng)存在于桶中，HashMap 會(huì)檢查鍵的 equals() 方法來確定是否是同一個(gè)鍵。如果 equals() 方法返回 true，新的鍵值對(duì)會(huì)替換舊的鍵值對(duì)；如果 equals() 方法返回 false，新的鍵值對(duì)會(huì)被添加到桶中。這樣就確保了 HashMap 中的鍵是唯一的。

3.5HashMap 和線程安全有關(guān)嗎？

HashMap 在默認(rèn)情況下是非線程安全的。多個(gè)線程同時(shí)對(duì) HashMap 進(jìn)行插入、刪除或查找操作可能會(huì)導(dǎo)致不一致的結(jié)果。如果在并發(fā)環(huán)境下使用 HashMap，應(yīng)考慮使用線程安全的 ConcurrentHashMap 或使用適當(dāng)?shù)耐綑C(jī)制來保護(hù) HashMap 的訪問。

3.6如何選擇適當(dāng)?shù)某跏既萘亢拓?fù)載因子？

HashMap 的初始容量和負(fù)載因子會(huì)影響其性能和空間利用率。初始容量是指 HashMap 初始化時(shí)的桶數(shù)量，默認(rèn)為 16。負(fù)載因子是指 HashMap 在擴(kuò)容之前允許的平均桶占用比例，默認(rèn)為 0.75。

選擇適當(dāng)?shù)某跏既萘亢拓?fù)載因子取決于你的應(yīng)用需求。如果預(yù)計(jì)存儲(chǔ)的鍵值對(duì)數(shù)量較多，可以選擇一個(gè)較大的初始容量，以減少動(dòng)態(tài)擴(kuò)容的頻率。負(fù)載因子較小可以減少哈希沖突的概率，但會(huì)增加空間占用。綜合考慮，通常可以使用 HashMap 的默認(rèn)值，并根據(jù)實(shí)際情況進(jìn)行調(diào)整。

HashMap 是一個(gè)強(qiáng)大而靈活的數(shù)據(jù)結(jié)構(gòu)，合理使用它可以提高程序的性能和效率。通過深入了解 HashMap 的底層實(shí)現(xiàn)原理，你可以更好地理解其工作方式，并在實(shí)際開發(fā)中做出更明智的設(shè)計(jì)和優(yōu)化決策。

結(jié)論

通過以上的源代碼分析和常見問題的解答，相信你已經(jīng)對(duì) HashMap 的底層實(shí)現(xiàn)原理有了更深入的理解。HashMap 的底層使用數(shù)組和鏈表（或紅黑樹）實(shí)現(xiàn)，通過哈希算法將鍵映射到數(shù)組的索引位置，以實(shí)現(xiàn)快速的插入和查找操作。動(dòng)態(tài)擴(kuò)容過程會(huì)創(chuàng)建一個(gè)更大的數(shù)組，并重新分配鍵值對(duì)到新的桶中，以提高性能。同時(shí)，我們還回答了一些常見問題，希望能幫助你更好地理解和應(yīng)用 HashMap。

作者介紹

波哥，在互聯(lián)網(wǎng)行業(yè)從業(yè)10余年，先后擔(dān)任項(xiàng)目總監(jiān)及架構(gòu)師。目前專攻技術(shù)，喜歡研究技術(shù)原理。技術(shù)全面，主攻Java，精通JVM底層機(jī)制及Spring全家桶底層框架原理，熟練掌握當(dāng)前主流的中間件、服務(wù)網(wǎng)格等技術(shù)原理。