目錄
一.HashMap
1.基本概念
2.底層數據結構：
3.HashCode和equals方法
為什么重寫HashCode方法？
為什么重新equals方法？
4.put操作
1.初始化和數組檢查
2.計算索引并檢查桶是否為空
3.桶不為null，處理哈希沖突
4.判斷鏈表是否轉化紅黑樹
5.以及數組大小是否超過閾值進行擴容
5.get操作
java1.7 -- java1.8 HashMap 做了哪些優化：
哈希值計算：
鏈表插入方式：
二.ConcurrentHashMap
1.Java 1.7?ConcurrentHashMap架構：
2.Java 1.8?ConcurrentHashMap架構：
CAS+synchronized的使用場景：
擴容區別：
size()區別：
一.HashMap
1.基本概念
HashMap是基于哈希表實現的Map接口，用于存儲鍵值對（K-V）格式，其核心作用就是通過哈希函數為了更快查詢到某個元素，時間復雜度O(1);
2.底層數據結構：
在java（1.7）之前 底層是采用“數組 + 鏈表” 的形式存儲
但在java（1.8） 之后，變成了“數組 + 鏈表 + 紅黑樹?”形式存儲
我們主要了解java1.8之后的內容；
從源碼上查看
數組的初始容量為16，負載因子為0.75，所以當超過這個閾值 16 * 0.75 = 12?
設計初始容量為16核心原因是2 的冪次方更適合哈希計算，能減少哈希沖突，但8又太頻繁擴容，新增性能開銷，而32空間又會太大，則浪費空間~
負載因子也是同理，太小，會頻繁擴容，雖然查詢快了，但是數組太稀疏，浪費空間，而太大，就會擴容少，空間利用率高，但查詢會變慢~
當插入第13個元素的時候，已經超過閾值，為了避免哈希沖突，會進行擴容~
然后這邊當數組大小超過64時候，鏈表大小超過8的時候，會從鏈表進化成紅黑樹，但當元素個數少于6個時，會退回鏈表~
-
鏈表長度≥8
基于泊松分布，當負載因子為 0.75 時，鏈表長度自然增長到 8 的概率極低（約千萬分之一），此時說明哈希沖突異常頻繁，需要轉為紅黑樹優化。 -
數組容量≥64
若數組容量小于 64（如 32），即使鏈表長度≥8，也會先觸發擴容（而非轉紅黑樹）。原因是：數組容量小時，擴容成本低，通過擴容可分散元素，減少沖突；而紅黑樹的維護成本（插入 / 刪除時的旋轉操作）高于擴容，此時擴容更高效。
3.HashCode和equals方法
HashMap中的鍵一定會實現這倆個方法，hashCode用于計算存儲的位置，而equals用于判斷來個鍵是否相同，在put方法的時候，如果倆個哈希值相同，會判斷是否是同一個值，如果不是就會放在同一個桶中的不同位置，如果相同就是一個東西~
為什么重寫HashCode方法？
如果不重寫，這個時候，就會導致倆個相同的key，會被計算出倆個不同的哈希值，導致他們存在在不同的桶中，到時候查詢的時候到底是查哪個？
為什么重新equals方法？
equals方法是為了當出現哈希沖突的時候，倆個key的哈希值相同，放在同一桶中，但沒有比較它們的對象，可能會誤判會導致倆個key存儲在不同位置，所以沒有覆蓋之前的值，就會錯誤~
class Person {String name;int age;@Overridepublic int hashCode() { // 重寫hashCode，保證邏輯相等的對象哈希值相同return Objects.hash(name, age);}// 未重寫equals()
}public static void main(String[] args) {HashMap<Person, String> map = new HashMap<>();Person p1 = new Person("張三", 20);Person p2 = new Person("張三", 20);map.put(p1, "學生");map.put(p2, "工人"); // 哈希值相同，進入同一個桶，但equals判斷為不同keySystem.out.println(map.size()); // 仍輸出2，而非預期的1
}hashCode()和equals()必須配套重寫，且滿足以下規則：
- 一致性：如果兩個對象通過
equals()判斷為相等，則它們的hashCode()必須返回相同的值； - 對稱性：如果
a.equals(b)為true，則b.equals(a)也必須為true； - 非空性：
a.equals(null)必須返回false。
4.put操作
1.初始化和數組檢查
首先判斷 HashMap 是否未初始化（table?數組為?null?或長度為 0），若是則觸發?初始化（resize）：
2.計算索引并檢查桶是否為空
如果該位置為空，直接創建新節點插入
3.桶不為null，處理哈希沖突
- 檢查首節點：若首節點的 key 與傳入 key?equals 相等（且哈希值相同），則視為 “重復 key”，記錄該節點（后續替換其 value）。
- 遍歷后續節點：
- 若桶是單鏈表（
Node）：遍歷鏈表，若找到 key 相等的節點，記錄該節點；若遍歷到鏈表尾部仍未找到，則在鏈尾插入新節點（Node）。 - 若桶是紅黑樹（
TreeNode）：調用紅黑樹的插入方法（putTreeVal），若找到重復 key 則記錄節點，否則插入新樹節點。
- 若桶是單鏈表（
- 處理重復 key：若步驟 1 或 2 中找到重復 key 的節點，用新 value 替換其舊 value，流程結束。
4.判斷鏈表是否轉化紅黑樹
5.以及數組大小是否超過閾值進行擴容
5.get操作
同理get?方法的核心邏輯是：
哈希計算→定位桶→根據桶結構（鏈表 / 紅黑樹）查找匹配節點
java1.7 -- java1.8 HashMap 做了哪些優化：
哈希值計算：
1.7版本：對 key 的原始哈希值（hashCode()?結果）進行?4 次擾動（多次移位和異或運算）
1.8版本：簡化為?1 次擾動，僅通過一次 “高 16 位與低 16 位異或” 實現混合
減少計算開銷：一次異或運算即可達到近似的混合效果，相比 1.7 的 4 次運算，計算效率更高。
實際效果：在大多數場景下，1 次擾動已能保證哈希值的均勻分布，同時降低了 CPU 運算成本。
鏈表插入方式：
由頭插變成尾插，核心是為了解決多線程擴容時的鏈表環化問題，同時讓鏈表操作邏輯更合理。
多線程擴容時可能導致鏈表環化（死循環）。
擴容過程中，節點會從舊數組遷移到新數組，頭插法在遷移時會反轉鏈表順序（例如舊鏈表 A→B，遷移后新鏈表變為 B→A）。若此時有多個線程同時操作，可能出現節點引用相互指向的情況（如 A.next = B 且 B.next = A），形成環形鏈表。后續查詢時，線程會陷入無限循環，導致 CPU 占用飆升。
二.ConcurrentHashMap
ConcurrentHashMap 是 Java 中用于并發場景的哈希表實現，專為高并發環境設計；
1.Java 1.7?ConcurrentHashMap架構：
在java1.8之前?ConcurrentHashMap?采用的是?分段數組（Segment）+ 哈希表 ， 默認為16個segment，同時支持16個并發~
- 整體結構：
ConcurrentHashMap -> Segment[] -> HashEntry[] -> 鏈表。
- 寫操作（put/remove 等）：
- 計算 key 的哈希值，定位到對應的?
Segment； - 獲取該?
Segment?的鎖（若被占用則阻塞）； - 在?
Segment?內部的哈希表中執行插入 / 刪除（類似 HashMap 的邏輯，鏈表頭插法）； - 釋放鎖。
- 計算 key 的哈希值，定位到對應的?
- 優點：通過分段鎖實現了多線程并發寫，效率比全表鎖（如 Hashtable）高得多。
- 缺點：
- 鎖粒度仍較大（以?
Segment?為單位），若多個線程操作同一?Segment，仍會阻塞； - 結構復雜，維護成本高；
- 擴容僅針對單個?
Segment，但整體性能受限于?Segment?數量。
- 鎖粒度仍較大（以?
2.Java 1.8?ConcurrentHashMap架構：
摒棄了?Segment?分段結構，底層直接使用?數組 + 鏈表 + 紅黑樹（與 JDK 1.8 HashMap 結構類似）
鎖的粒度更小，鎖的是桶的頭節點，并且采取了CAS + synchronized 機制，僅當多個線程操作同一鏈表 / 紅黑樹時才會競爭鎖，鎖沖突概率遠低于 1.7 的 Segment 級鎖。
CAS+synchronized的使用場景：
- 無沖突場景（空桶插入、初始化、低并發計數）：用 CAS 實現高效無鎖操作。
- 有沖突場景（非空桶操作、復雜結構修改）：用 synchronized 加鎖保證原子性。
| 版本 | 底層架構 | 哈希表數量 | 鎖粒度 |
|---|---|---|---|
| JDK 1.7 及之前 | 兩層結構：Segment [] 數組 + 每個 Segment 包含一個 HashEntry [] 數組 | 多個（默認 16 個，與 Segment 數量一致） | Segment 級（鎖整個子哈希表） |
| JDK 1.8 及之后 | 單層結構：Node [] 數組（鏈表 / 紅黑樹解決沖突） | 1 個（整個 ConcurrentHashMap 共用一個底層數組） | 節點級（鎖鏈表頭節點或紅黑樹根節點） |
擴容區別：
| 特性 | JDK 1.7 擴容 | JDK 1.8 擴容 |
|---|---|---|
| 擴容范圍 | 單個 Segment 獨立擴容 | 整個數組全表擴容 |
| 并發能力 | 單線程擴容（當前操作 Segment 的線程） | 多線程協同擴容（所有線程可協助遷移） |
| 鎖影響范圍 | 僅鎖定當前 Segment，其他 Segment 可用 | 無全局鎖，僅鎖定遷移中的桶節點 |
| 遷移效率 | 單個 Segment 遷移，效率較低 | 多線程分片遷移，效率更高 |
| 節點遷移方式 | 頭插法（可能反轉鏈表） | 尾插法（保持鏈表順序，無環化風險） |
| 與讀寫的兼容性 | 擴容時該 Segment 讀寫阻塞 | 擴容與讀寫可并行（讀無鎖，寫鎖單個桶） |
size()區別：
在JDK 1.7 中，ConcurrentHashMap 由多個?Segment?組成，每個?Segment?獨立維護自己的元素數量（count），因此計算總?size?時需要累加所有 Segment 的 count。
- 為減少誤差，JDK 1.7 采用 “重試機制”：如果兩次連續累加的結果一致，則認為是準確值；若不一致（說明期間有并發修改），最多重試 3 次，若仍不一致則直接返回當前累加值（接受一定誤差）。
而在JDK 1.8中，計算?size?依賴于?baseCount?原子變量和?counterCells?輔助數組，通過無鎖累加實現，返回兩者的總和作為最終的?size。
當插入元素成功后，需要將總數?+1，流程如下：
-
優先嘗試更新?
baseCount：
線程通過 CAS 操作直接更新?baseCount（baseCount + 1）。- 若 CAS 成功：計數完成，無需其他操作。
- 若 CAS 失敗：說明存在并發競爭（多個線程同時更新?
baseCount），進入下一步。
-
競爭激烈時，使用?
counterCells?分散計數：- 若?
counterCells?未初始化，先通過 CAS 初始化（創建一個?CounterCell?數組）。 - 線程通過哈希算法（基于線程 ID 或隨機數）隨機選擇?
counterCells?中的一個?CounterCell。 - 嘗試用 CAS 更新該?
CounterCell?的?value（value + 1）：- 若成功：計數完成。
- 若失敗：重試或選擇其他?
CounterCell（避免死鎖）。
- 若?
| 特性 | JDK 1.7 計數方式 | JDK 1.8 計數方式 |
|---|---|---|
| 底層依賴 | 各 Segment 的?count?累加 | baseCount?+?counterCells?累加 |
| 并發處理 | 重試機制減少誤差，返回近似值 | CAS 原子操作，返回接近精確值 |
| 性能 | 低并發時高效，依賴 Segment 數量 | 高低并發均高效，通過分散競爭優化 |
| 實現復雜度 | 簡單（遍歷 + 重試） | 復雜（原子變量 + 輔助數組 + 競爭分散） |
| 適用場景 | 分段鎖架構下的近似計數 | 全局數組架構下的高效精確計數 |
