淺顯易懂HashMap的數據結構

HashMap 就像一個大倉庫，里面有很多小柜子（數組），每個小柜子可以掛一串鏈條（鏈表），鏈條太長的時候會變成更高級的架子（紅黑樹）。下面用超簡單的例子解釋：

?壹. 排列方式

?數組：一排固定的小柜子（比如柜子0、柜子1、柜子2...）。
?鏈表：如果多個東西要放在同一個柜子里，它們會串成一條鏈子。
?紅黑樹：當某個柜子的鏈子太長（比如超過8個），鏈子會變成一個小架子（樹結構），找東西更快。

?貳. 存數據的過程

假設我們要存一個鍵值對?("name", "小明")：

?找柜子：先算?"name"?的哈希值（類似身份證號），比如得到柜子3。
?放數據：
- 如果柜子3是空的，直接放進去。
- 如果柜子3已經有東西，檢查鏈條上的每個元素：
  - 如果有相同的鍵（比如已經有?"name"），替換它的值。
  - 如果沒有，把新鍵值對掛到鏈子末尾。
?鏈條轉架子：如果鏈子長度超過8，就把鏈子變成紅黑樹架子。

?叁. 取數據的過程

假設要取?"name"?對應的值：

?找柜子：算?"name"?的哈希值，確定是柜子3。
?找數據：
- 如果柜子3是鏈子，遍歷鏈子找?"name"。
- 如果柜子3是架子（紅黑樹），用樹的快速查找方法。

?肆. 代碼簡化版（Java）?

// 小柜子（數組）
Node[] table = new Node[16];// 鏈表節點（如果鏈子太長，會變成 TreeNode）
class Node {String key;String value;Node next; // 下一個節點
}// 紅黑樹節點（架子結構）
class TreeNode extends Node {TreeNode parent;TreeNode left;TreeNode right;
}// 存數據示例
void put(String key, String value) {int hash = key.hashCode();int index = hash % table.length; // 計算柜子位置if (table[index] == null) {// 柜子是空的，直接放進去table[index] = new Node(key, value);} else {// 柜子非空，掛到鏈子末尾或更新值// 如果鏈子太長，轉成紅黑樹}
}

?伍. 一句話總結

HashMap? 的數組是主干，鏈表解決哈希沖突，紅黑樹解決鏈表過長時的性能問題！

陸. 源碼：HashMap的putVal()方法

/*** Implements Map.put and related methods** @param hash hash for key* @param key the key* @param value the value to put* @param onlyIfAbsent if true, don't change existing value* @param evict if false, the table is in creation mode.* @return previous value, or null if none*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

柒、我們來拆解 ??“哈希沖突時，鏈表如何掛到數組上”?? 的詳細過程，用大白話 + 例子解釋：

?1. 核心原理：用鏈表串聯沖突的鍵值對

當兩個不同的鍵（比如?"name"?和?"age"）通過哈希計算后，分配到 ?同一個數組位置（同一個柜子）?? 時，就會發生 ?哈希沖突。
此時，HashMap 會用 ?鏈表? 把這些沖突的鍵值對串起來，掛在數組的這個位置上（類似掛一串鑰匙）。

?2. 具體掛鏈表的步驟（逐行分析）?

假設數組的某個位置?index?已經有數據，現在要存入新的鍵值對?(key2, value2)：

?檢查是否重復：遍歷鏈表，對比每個節點的?key：
- 如果發現某個節點的?key?和?key2??相同?（用?equals()?判斷），直接覆蓋它的值。
- 如果鏈表中沒有相同的?key，則把新節點 ?掛到鏈表末尾?（Java 8 之后是尾插法）。

?鏈表掛載示意圖：

// 數組的某個位置 index 已經有一個節點 Node1
table[index] = Node1(key1, value1) -> null;// 存入新節點 Node2（沖突）
Node1.next = Node2(key2, value2); // 掛到鏈表尾部
table[index] = Node1 -> Node2 -> null;

?代碼邏輯簡化版：

Node existingNode = table[index]; // 獲取數組當前位置的鏈表頭// 遍歷鏈表，檢查是否已有相同的 key
while (existingNode != null) {if (existingNode.key.equals(newKey)) {existingNode.value = newValue; // 覆蓋舊值return;}existingNode = existingNode.next;
}// 如果沒有重復 key，把新節點掛到鏈表末尾
Node newNode = new Node(newKey, newValue);
newNode.next = table[index]; // Java 8 之前是頭插法（新節點變成鏈表頭）
table[index] = newNode;      // Java 8 之后是尾插法（直接掛在鏈表尾部）

?3. 關鍵細節：頭插法 vs 尾插法

?Java 8 之前：新節點插入鏈表頭部（頭插法）。
- 問題：多線程下可能導致鏈表成環（死循環）。
- 示例：table[index] = 新節點 -> 舊節點 -> null。
?Java 8 之后：新節點插入鏈表尾部（尾插法）。
- 改進：避免多線程下的鏈表成環問題。
- 示例：舊節點 -> 新節點 -> null。

?4. 鏈表轉紅黑樹的條件

當鏈表長度 ?超過 8，且 ?數組總長度 ≥ 64? 時，鏈表會轉換成紅黑樹。
?如果數組長度 < 64，即使鏈表長度 > 8，HashMap 也會優先選擇 ?擴容數組?（而不是轉樹），因為擴容能直接減少哈希沖突的概率，成本更低。
這正說明 HashMap 的設計是 ?先嘗試擴容解決沖突，實在不行再轉樹。😄
- 為什么這樣設計？
  - ?小數組時擴容更高效：
    - 數組較小時，哈希沖突可能只是因為數組容量不足，直接擴容能快速緩解問題。
    - 紅黑樹結構復雜，維護成本高，小規模數據下不如擴容劃算。
  - ?大數組時優化查詢：
    - 數組足夠大（≥64）后，如果仍有長鏈表，說明哈希沖突難以通過擴容解決（如多個 key 哈希值相同）。
    - 此時轉為紅黑樹，將查詢復雜度從?O(n)?降為?O(logn)。

?5. 完整流程示例

假設存入?("name", "小明")?和?("age", 18)，它們的哈希值沖突（都映射到數組位置 3）：

?存入第一個節點：

table[3] = Node("name", "小明") -> null;

?存入第二個節點（沖突）?：

// 檢查鏈表，發現沒有重復 key，掛到鏈表末尾
table[3] = Node("name", "小明") -> Node("age", 18) -> null;

?查找時：遍歷鏈表，逐個對比?key，找到對應值。

?6.總結

?鏈表掛在數組上：通過節點的?next?指針串聯沖突的鍵值對。
?插入位置：Java 8 之后用尾插法，避免多線程問題。
?轉紅黑樹：鏈表過長時優化查找速度（從 O(n) 優化到 O(log n)）。

捌、再幫你用 ??“倉庫管理員” 的比喻? 總結一下，確保徹底理解：

?終極傻瓜版總結

?倉庫（數組）?：管理員有一排柜子（比如16個），每個柜子有編號（0到15）。
?存東西（鍵值對）?：
- 管理員用 ?哈希函數?（比如?key.hashCode() % 16）算出東西應該放哪個柜子。
- 如果柜子空，直接放進去。
?柜子沖突（哈希沖突）?：
- 如果柜子已經有東西，管理員會拿一根 ?鏈條（鏈表）?? 把新東西和舊東西綁在一起，掛在柜子里。
- ?鏈條的掛法：新東西掛在鏈條的尾部（Java 8之后）。
?鏈條太長怎么辦：
- 如果鏈條長度超過8，管理員會把鏈條換成 ?高級貨架（紅黑樹）?，這樣找東西更快。
- 但如果倉庫的柜子總數太少（比如小于64個），管理員會直接 ?擴建倉庫（擴容數組）?，而不是換貨架。

?關鍵邏輯圖示

// 數組（柜子列表）
Node[] table = [柜子0, 柜子1, ..., 柜子15];// 柜子里的內容（鏈表或樹）
柜子3 -> Node1("name", "小明") -> Node2("age", 18) -> null  // 鏈表形式
柜子5 -> TreeNode("id", 1001)  // 樹形式（如果鏈表轉成了紅黑樹）

?容易混淆的點

?覆蓋值：如果兩次存同一個?key（比如兩次存?"name"），會直接覆蓋舊值。
?哈希函數：hashCode()?決定柜子位置，但不同對象可能算出相同的哈希值（沖突）。
?擴容：當倉庫的柜子被填滿超過一定比例（默認75%），管理員會擴建倉庫（數組長度翻倍），重新分配所有東西的位置。

玖、結合：面試被問 Java中hashmap數據結構?

? ? ? ? URL：?地基：Java中hashmap數據結構（面試被問）-CSDN博客

兄弟們，理解好了。rt.jar包里的hashmap源碼的putval方法的方式，有厲害的同學可以學以致用哈！向大家致敬！

（望各位潘安、各位子健/各位彥祖、于晏不吝賜教！多多指正！🙏）

-----分界線----------------------------------------------------------------------------------------------------

兄弟們，上面的足以應付面試了，如何還想更深入，可以看下面的。

拾. 為什么數組長度 ≥64 時不擴容，而是轉樹？

?1?擴容的局限性**

?擴容的本質：通過擴大數組長度，將節點分散到新數組中，減少哈希沖突。

?局限性：如果多個鍵的哈希值本身就沖突（例如哈希算法導致碰撞），即使擴容也無法分散它們。

// 例如：鍵A和鍵B的哈希值不同，但取模后仍落在同一個桶
hash(A) % 64 = 5;
hash(B) % 64 = 5;  // 即使數組擴容到128，依然可能 hash(A) % 128 = 5，hash(B) % 128 = 5

?2) 轉樹的優勢**

?解決哈希碰撞：當哈希沖突無法通過擴容避免時（如多個鍵哈希值相同），紅黑樹將查詢復雜度從鏈表O(n)降到O(logn)。
?成本權衡：
- ?擴容成本高：需新建數組、重新哈希所有節點（時間復雜度O(n)）。
- ?轉樹成本低：只處理單個沖突嚴重的桶，其他桶不受影響。

?3) 閾值為什么是64？**

?經驗值：基于測試和性能權衡：
- 數組長度較小時（<64），哈希沖突可能因數組容量不足，優先擴容更高效。
- 數組長度≥64時，認為哈希沖突更可能是哈希算法導致（而非數組容量問題），轉樹更合理。

4. 源碼邏輯驗證

HashMap的treeifyBin()方法中會先檢查數組長度是否≥64，再決定轉樹或擴容：

// HashMap 源碼片段
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) { // MIN_TREEIFY_CAPACITY=64resize(); // 數組長度<64時，選擇擴容} else {// 數組長度≥64時，將鏈表轉為紅黑樹TreeNode<K,V> hd = null, tl = null;// ...（具體轉樹邏輯）}
}

5. 舉例說明

?場景1：數組長度=16，鏈表長度=9

數組長度16 < 64 → ?觸發擴容?（數組擴大到32），而不是轉樹。

?場景2：數組長度=64，鏈表長度=9

數組長度≥64 → ?鏈表轉為紅黑樹，不再擴容。

6、?總結

?轉樹的條件：鏈表長度>8 ?且? 數組長度≥64。
?轉樹的目的：針對哈希算法導致的不可分散沖突，用空間換時間（紅黑樹優化查詢）。
?擴容的優先級：數組較小時，擴容是更經濟的解決方案。

拾壹、數組擴容是否重新計算哈希值？

在 HashMap 中，當數組長度小于 64 時觸發擴容，哈希值本身不會重新計算，但元素在數組中的位置（索引）會根據新的數組長度重新確定。以下是具體機制：

?1. 哈希值如何生成？

?哈希值來源：
HashMap 中每個鍵（Key）的哈希值由以下兩步生成：
1. 調用鍵對象的?hashCode()?方法，得到原始哈希值。
2. 通過 ?擾動函數?（位運算）對原始哈希值進行二次處理，增加隨機性，減少哈希沖突。
```
// HashMap 的擾動函數實現
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
?哈希值的存儲：
這個最終哈希值會在鍵值對被插入 HashMap 時計算一次，并存儲在?Node?或?TreeNode?對象中，后續不再重新計算。

?2. 擴容時如何確定新位置？

當數組長度從?oldCap（例如 16）擴容到?newCap（例如 32）時，元素的索引位置會按以下規則重新分配：

?索引計算公式：
新索引 =?hash & (newCap - 1)
（newCap - 1?是新的掩碼，例如 32 →?0b11111）。
?優化計算技巧：
由于擴容是翻倍（newCap = oldCap << 1），新掩碼比舊掩碼多出一個高位?1（例如 16 →?0b1111，32 →?0b11111）。
因此，新索引只需判斷哈希值中新增的高位是?0?還是?1：
- 如果高位是?0：新索引 = ?原位置。
- 如果高位是?1：新索引 = ?原位置 + oldCap。
?源碼邏輯：
```
// 遍歷舊數組中的每個桶
for (int j = 0; j < oldCap; j++) {Node<K,V> e;if ((e = oldTab[j]) != null) {// 檢查哈希值高位是 0 還是 1if ((e.hash & oldCap) == 0) {// 高位為 0 → 留在原位置（j）} else {// 高位為 1 → 移動到新位置（j + oldCap）}}
}
```

?3. 示例說明

假設原數組長度?oldCap = 16（二進制?0b10000），擴容后?newCap = 32（二進制?0b100000）。

?鍵的哈希值：假設為?0b10101。
?舊索引計算：
hash & (oldCap - 1) = 0b10101 & 0b1111 = 0b00101?→ 索引 5。
?新索引計算：
hash & (newCap - 1) = 0b10101 & 0b11111 = 0b10101?→ 索引 21。
或者直接通過高位判斷：
hash & oldCap = 0b10101 & 0b10000 = 0b10000 ≠ 0?→ 高位為 1，新索引 = 5 + 16 = 21。