作者 | 波哥

作為一名程序員，你可能經常使用 HashMap 這個重要的數據結構，但你對它的底層實現原理可能不夠了解。本文將通過圖文結合的方式，為你詳細解析 HashMap 的底層實現原理，并回答一些常見問題，讓你能夠更好地理解和應用 HashMap。

1. HashMap 概述

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

2. HashMap 的主要方法分析

2.1 put方法

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

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

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

2.2 resize方法

resize方法用于動態擴容 HashMap。當元素數量超過閾值時，HashMap 會自動觸發擴容操作。下面是resize方法的源代碼：

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

2.3 get方法

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

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

接下來，我們在確定的索引位置找到對應的桶。如果桶為空，即沒有鍵值對存在，那么返回 null，表示沒有找到對應的值。

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

如果遍歷完整個鏈表或紅黑樹仍然沒有找到相等的鍵，那么返回 null，表示沒有找到對應的值。

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

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

通過分析上述代碼，我們可以看到get方法的實現流程：首先計算鍵的哈希碼，然后根據哈希碼找到對應的桶，最后在桶中遍歷鏈表或紅黑樹，查找具有相同鍵的節點，如果找到則返回對應的值，否則返回 null。

3. 常見問題分析

3.1為什么哈希碼很重要?

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

3.2如何處理哈希沖突？

當兩個不同的鍵具有相同的哈希碼時，HashMap 會使用鏈表或紅黑樹來解決哈希沖突。鏈表是 JDK 8 之前的解決方案，而紅黑樹是 JDK 8 之后的優化。HashMap 在桶中通過鏈表或紅黑樹結構存儲沖突的鍵值對，以便在查找時能快速定位到正確的鍵值對。

3.3為什么需要動態擴容？

動態擴容是為了避免哈希沖突過多，提高 HashMap 的性能。當鍵值對的數量接近數組容量的閾值時，HashMap 會自動觸發擴容操作。它創建一個更大的數組，并重新計算每個鍵的哈希碼和索引位置，然后將鍵值對重新插入到新數組中。這樣可以減少桶的數量，降低哈希沖突的概率，提高存儲和檢索的效率。

3.4如何保證鍵的唯一性？

HashMap 通過哈希碼和鏈表/紅黑樹結構來保證鍵的唯一性。當存儲鍵值對時，如果發現相同的鍵已經存在于桶中，HashMap 會檢查鍵的 equals() 方法來確定是否是同一個鍵。如果 equals() 方法返回 true，新的鍵值對會替換舊的鍵值對；如果 equals() 方法返回 false，新的鍵值對會被添加到桶中。這樣就確保了 HashMap 中的鍵是唯一的。

3.5HashMap 和線程安全有關嗎？

HashMap 在默認情況下是非線程安全的。多個線程同時對 HashMap 進行插入、刪除或查找操作可能會導致不一致的結果。如果在并發環境下使用 HashMap，應考慮使用線程安全的 ConcurrentHashMap 或使用適當的同步機制來保護 HashMap 的訪問。

3.6如何選擇適當的初始容量和負載因子？

HashMap 的初始容量和負載因子會影響其性能和空間利用率。初始容量是指 HashMap 初始化時的桶數量，默認為 16。負載因子是指 HashMap 在擴容之前允許的平均桶占用比例，默認為 0.75。

選擇適當的初始容量和負載因子取決于你的應用需求。如果預計存儲的鍵值對數量較多，可以選擇一個較大的初始容量，以減少動態擴容的頻率。負載因子較小可以減少哈希沖突的概率，但會增加空間占用。綜合考慮，通常可以使用 HashMap 的默認值，并根據實際情況進行調整。

HashMap 是一個強大而靈活的數據結構，合理使用它可以提高程序的性能和效率。通過深入了解 HashMap 的底層實現原理，你可以更好地理解其工作方式，并在實際開發中做出更明智的設計和優化決策。

結論

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

作者介紹

波哥，在互聯網行業從業10余年，先后擔任項目總監及架構師。目前專攻技術，喜歡研究技術原理。技術全面，主攻Java，精通JVM底層機制及Spring全家桶底層框架原理，熟練掌握當前主流的中間件、服務網格等技術原理。