前言

HashMap 是 Java 中最常用、面試中最常被問到的集合類之一。它基于哈希表實現(xiàn)，提供了存儲鍵值對的功能，具有高效的存取速度。以下是對 HashMap 的全方位深度解析，包括底層結(jié)構(gòu)、核心原理、擴容機制、版本差異以及常見面試題。

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

HashMap 的底層數(shù)據(jù)結(jié)構(gòu)是 數(shù)組 + 鏈表 + 紅黑樹（JDK 1.8 及以后）。

• 哈希桶數(shù)組（table）: 這是HashMap的骨干，即 Node<K,V>[] table(JDK 1.8 中 Node 是 HashMap 的內(nèi)部類，實現(xiàn)了 Map.Entry 接口）。數(shù)組的每個位置稱為一個“桶”（bucket），桶中存放的是鏈表或紅黑樹的頭節(jié)點，用于快速定位元素。數(shù)組的默認(rèn)初始容量為16，且長度始終保持為2的冪次方;
• 鏈表: 當(dāng)不同的鍵通過哈希函數(shù)計算出相同的數(shù)組下標(biāo)（即發(fā)生哈希沖突）時，HashMap采用鏈地址法來解決沖突。沖突的鍵值對會以鏈表形式存儲在同一個桶中。鏈表節(jié)點是一個靜態(tài)內(nèi)部類 Node，它包含了鍵的哈希值（final int hash）、鍵（final K key）、值（V value）以及指向下一個節(jié)點的指針（Node<K,V> next）;
• 紅黑樹: 這是JDK 1.8引入的關(guān)鍵優(yōu)化。當(dāng)某個桶中的鏈表長度過長（默認(rèn)達(dá)到8），且當(dāng)前哈希桶數(shù)組的總長度大于等于64時，該鏈表會被轉(zhuǎn)換為紅黑樹。紅黑樹是一種自平衡的二叉查找樹，能將最壞情況下的查找時間復(fù)雜度從鏈表的O(n)優(yōu)化至O(log n)。當(dāng)紅黑樹節(jié)點數(shù)少于 6 時，又會轉(zhuǎn)回鏈表（平衡查詢和插入性能）;

2. 核心成員變量與參數(shù)

理解 HashMap 必須知道以下幾個關(guān)鍵參數(shù)：

1. initialCapacity（初始容量）: 默認(rèn)是 16。必須是 2 的 n 次冪。
2. loadFactor（負(fù)載因子）: 默認(rèn)是 0.75。
3. threshold（擴容閾值） = capacity * loadFactor。當(dāng) size（元素個數(shù)）大于這個值時，觸發(fā)擴容。
4. size: 當(dāng)前 Map 中實際存儲的鍵值對數(shù)量。

3. 核心方法原理

3.1 確定 Hash 索引（如何把 Key 放進(jìn)數(shù)組？）

當(dāng)調(diào)用 put(key, value) 時，HashMap 需要計算這個 key 應(yīng)該放在數(shù)組的哪個下標(biāo)。計算步驟如下：

1. 擾動函數(shù): hash = (h = key.hashCode()) ^ (h >>> 16)
   • 首先調(diào)用key.hashCode() 獲得原始哈希值;
   • 將 hashCode 的高16位與低16位進(jìn)行異或運算。這樣做的目的是讓高位特征也參與后續(xù)的尋址運算，從而降低哈希沖突的概率;
2. 取模運算: index = hash & (n - 1)
   • 注意：這里沒有用 % 運算，而是用了 & 位運算。前提是數(shù)組長度 n 必須是 2 的冪次方(n=2x2^x2x)。
   • (n - 1) 的二進(jìn)制形式全為 1（例如 15 是 1111），這個位運算(n-1) & hash 的效果等價于 hash % n（取模），但位運算的效率遠(yuǎn)高于取模運算。

3.2 put() 流程詳解（JDK 1.8）

put(key, value) 方法是HashMap的核心，其流程高度復(fù)雜且優(yōu)化充分：

1. 初始化/擴容判斷：如果哈希桶數(shù)組 table 為空或長度為0，則首先調(diào)用 resize() 方法進(jìn)行初始化。

2. 計算索引并檢查桶：根據(jù)key計算哈希和索引 i。如果 table[i] 為空，直接在此處創(chuàng)建一個新Node。

3. 處理哈希沖突：如果table[i]不為空（發(fā)生沖突），則需進(jìn)一步處理：

   • 覆蓋：檢查頭節(jié)點的key是否與待插入key相同（先比較hash，再用equals()比較），相同則覆蓋舊值。
   • 紅黑樹插入：如果頭節(jié)點是 TreeNode 類型，則調(diào)用紅黑樹的插入方法 putTreeVal。
   • 鏈表遍歷與插入：如果是普通鏈表，則遍歷鏈表。遍歷過程中若找到相同key則覆蓋；若未找到，則采用尾插法將新節(jié)點插入鏈表末尾（JDK 1.8改為尾插法，解決了JDK 1.7頭插法在并發(fā)擴容時可能導(dǎo)致的死循環(huán)問題）。插入后，如果鏈表長度達(dá)到樹化閾值（TREEIFY_THRESHOLD=8），則調(diào)用 treeifyBin 方法。

4. 樹化判斷：在 treeifyBin 中，會先判斷數(shù)組長度是否達(dá)到最小樹化容量（MIN_TREEIFY_CAPACITY=64）。如果未達(dá)到，則優(yōu)先進(jìn)行擴容；如果已達(dá)到，才將鏈表轉(zhuǎn)換為紅黑樹。

5. 擴容檢查：插入完成后，元素總數(shù) size 加1。如果 size 超過了擴容閾值（threshold = 容量 * 負(fù)載因子），則觸發(fā) resize() 擴容。

3.3 get() 流程詳解

1. 計算 key 的 hash。
2. 定位桶位置。
3. 在該桶中遍歷：
   • 若是鏈表，逐個比較 key.equals()；
   • 若是紅黑樹，按樹結(jié)構(gòu)查找。
4. 找到則返回 value，否則返回 null。

時間復(fù)雜度：

• 理想情況：O(1)
• 最壞情況（大量沖突）：O(log n)（紅黑樹）或 O(n)（長鏈表）

3.4. 擴容機制

HashMap 默認(rèn)初始容量為 16，負(fù)載因子為 0.75。

• 擴容條件：當(dāng)你調(diào)用 put 方法插入數(shù)據(jù)，且滿足 size > threshold 時，HashMap 會調(diào)用resize()方法；

• 擴容大小:

  • 容量翻倍：新數(shù)組的容量 = 舊數(shù)組容量 << 1（乘以 2）;
  • 閾值翻倍：新的閾值 = 新容量 * 負(fù)載因子；

• 擴容過程:

  • 創(chuàng)建一個新的大數(shù)組。
  • 遍歷舊數(shù)組，將每個元素重新計算 hash 值，放入新數(shù)組。
  • JDK 1.8 的優(yōu)化：
    • 由于擴容是 2 倍，在計算新索引時：index = hash & (newCap - 1)。
    • 觀察發(fā)現(xiàn)，元素的位置要么在原索引，要么在原索引 + 原容量的位置。
    • 因此，不需要重新計算 hash，只需要判斷 (hash & oldCap) == 0 即可決定去哪。這大大提高了擴容效率。

?? 舉例說明（JDK 8）：
原容量=16（二進(jìn)制 10000），元素 hash=20（二進(jìn)制 10100）
20 & 16 = 16 ≠ 0 → 新位置 = 原索引(4) + 16 = 20
原在索引4的元素，擴容后可能分散到索引4或20

4. JDK 1.7 與 JDK 1.8 的主要區(qū)別

這是一個高頻面試考點。

?為什么要改為尾插法？
在 JDK 1.7 中，擴容時 transfer 數(shù)據(jù)使用頭插法，會導(dǎo)致鏈表逆序。在多線程并發(fā)擴容環(huán)境下，可能會造成鏈表成環(huán)（死循環(huán)），導(dǎo)致 CPU 100%。JDK 1.8 改用尾插法，保持了元素順序，避免了這個問題。

5. 線程安全問題

HashMap 是非線程安全的。

如果在多線程環(huán)境下使用 HashMap，可能會導(dǎo)致：

1. 數(shù)據(jù)丟失：多線程 put 競爭導(dǎo)致覆蓋。
2. 死循環(huán)（僅限 JDK 1.7）：擴容導(dǎo)致的環(huán)形鏈表。
3. 數(shù)據(jù)不一致：size 計數(shù)不準(zhǔn)等。

解決方案：

1. ConcurrentHashMap: 推薦使用。JDK 1.7 使用分段鎖，JDK 1.8 使用 CAS + synchronized，效率極高。
2. Collections.synchronizedMap(new HashMap<>()): 給所有方法加鎖，性能較差。
3. Hashtable: 古老類，所有方法加 synchronized，全表鎖，性能極差，基本不使用。

6. 常見面試題總結(jié)

1. HashMap 的底層數(shù)據(jù)結(jié)構(gòu)？
   • 數(shù)組+鏈表+紅黑樹（JDK 8）。
   • 鏈表->紅黑樹閾值是 8，紅黑樹->鏈表閾值是 6。
2. 為什么 HashMap 容量建議是 2 的冪次方？
   • 為了讓元素分布均勻。
   • 為了使用 (n - 1) & hash 這種高效的位運算代替取模運算。
3. HashMap 的擴容機制是怎樣的？
   • 達(dá)到閾值（容量 * 負(fù)載因子）時擴容為 2 倍。JDK 8 通過位運算判斷元素位置是原索引還是 原索引+舊容量。
4. HashMap 在 JDK 1.7 和 1.8 的區(qū)別？
   • 1.7 頭插法，1.8 尾插法（防止死循環(huán)）。
   • 1.8 引入紅黑樹（優(yōu)化查詢性能）。
5. HashMap 為什么不直接使用 hashCode()？
   • 因為 hashCode() 返回的是 int，范圍太大，且分布可能不均。
   • HashMap 使用擾動函數(shù)（高位異或低位）來打散低位特征，減少沖突。
6. 為什么轉(zhuǎn)紅黑樹的閾值是 8？
   • 根據(jù)泊松分布計算，在負(fù)載因子 0.75 的情況下，鏈表長度達(dá)到 8 的概率極低（千萬分之一）。如果到了 8，說明 Hash 沖突非常嚴(yán)重，需要由 O(n) 轉(zhuǎn)為O(log n)的樹結(jié)構(gòu)來提升性能。
7. 為什么要擾動？
   • hashCode() 返回的是 int 類型（32 位），數(shù)組長度通常較?。ㄈ?16），直接取模會導(dǎo)致高 16 位的特征丟失。通過異或高 16 位，能讓高 16 位參與后續(xù)的索引計算，減少哈希沖突。
8. 為什么負(fù)載因子是 0.75？
   這是一個時間和空間的權(quán)衡。
   • 太大（如 1.0）：空間利用率高，但哈希沖突概率增加，導(dǎo)致鏈表/紅黑樹過長，查詢效率下降。
   • 太小（如 0.5）：哈希沖突少，查詢快，但空間浪費嚴(yán)重，頻繁擴容。
   • 0.75 是根據(jù)泊松分布統(tǒng)計得出的經(jīng)驗值，能夠較好地平衡空間和時間開銷。
9. 擾動函數(shù)解釋

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

1. h = key.hashCode() → 獲取原始哈希值（32 位整數(shù)）
2. h >>> 16 → 無符號右移 16 位，把高 16 位移到低 16 位，高 16 位補 0
3. h ^ (h >>> 16) → 將原哈希值的 高 16 位 與 低 16 位 異或

? 這就是所謂的 “高位異或低位” —— 更準(zhǔn)確說是 高16位與低16位異或，生成新的低16位，讓高位信息也能影響最終的索引計算。

總結(jié)

HashMap 是一個設(shè)計精妙的類，它通過哈希算法快速定位，通過鏈表解決沖突，通過紅黑樹優(yōu)化極端情況，通過位運算提升效率。理解它對于理解 Java 集合框架和哈希表原理至關(guān)重要。

到此這篇關(guān)于Java HashMap底層原理的文章就介紹到這了,更多相關(guān)Java HashMap底層原理內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論