一.HashMap

1.基本概念

HashMap是基于哈希表實現(xiàn)的Map接口，用于存儲鍵值對（K-V）格式，其核心作用就是通過哈希函數(shù)為了更快查詢到某個元素，時間復雜度O(1);

2.底層數(shù)據(jù)結構：

在java（1.7）之前 底層是采用“數(shù)組 + 鏈表” 的形式存儲

但在java（1.8） 之后，變成了“數(shù)組 + 鏈表 + 紅黑樹 ”形式存儲

我們主要了解java1.8之后的內(nèi)容；

從源碼上查看

數(shù)組的初始容量為16，負載因子為0.75，所以當超過這個閾值 16 * 0.75 = 12 
設計初始容量為16核心原因是2 的冪次方更適合哈希計算，能減少哈希沖突，但8又太頻繁擴容，新增性能開銷，而32空間又會太大，則浪費空間~
負載因子也是同理，太小，會頻繁擴容，雖然查詢快了，但是數(shù)組太稀疏，浪費空間，而太大，就會擴容少，空間利用率高，但查詢會變慢~

當插入第13個元素的時候，已經(jīng)超過閾值，為了避免哈希沖突，會進行擴容~

然后這邊當數(shù)組大小超過64時候，鏈表大小超過8的時候，會從鏈表進化成紅黑樹，但當元素個數(shù)少于6個時，會退回鏈表~

1. 鏈表長度≥8
   基于泊松分布，當負載因子為 0.75 時，鏈表長度自然增長到 8 的概率極低（約千萬分之一），此時說明哈希沖突異常頻繁，需要轉(zhuǎn)為紅黑樹優(yōu)化。

2. 數(shù)組容量≥64
   若數(shù)組容量小于 64（如 32），即使鏈表長度≥8，也會先觸發(fā)擴容（而非轉(zhuǎn)紅黑樹）。原因是：數(shù)組容量小時，擴容成本低，通過擴容可分散元素，減少沖突；而紅黑樹的維護成本（插入 / 刪除時的旋轉(zhuǎn)操作）高于擴容，此時擴容更高效。

3.HashCode和equals方法

HashMap中的鍵一定會實現(xiàn)這倆個方法，hashCode用于計算存儲的位置，而equals用于判斷來個鍵是否相同，在put方法的時候，如果倆個哈希值相同，會判斷是否是同一個值，如果不是就會放在同一個桶中的不同位置，如果相同就是一個東西~

為什么重寫HashCode方法？

如果不重寫，這個時候，就會導致倆個相同的key，會被計算出倆個不同的哈希值，導致他們存在在不同的桶中，到時候查詢的時候到底是查哪個？

為什么重新equals方法？

equals方法是為了當出現(xiàn)哈希沖突的時候，倆個key的哈希值相同，放在同一桶中，但沒有比較它們的對象，可能會誤判會導致倆個key存儲在不同位置，所以沒有覆蓋之前的值，就會錯誤~

class Person {
    String name;
    int age;
    @Override
    public 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判斷為不同key
    System.out.println(map.size()); // 仍輸出2，而非預期的1
}

hashCode()和equals()必須配套重寫，且滿足以下規(guī)則：

• 一致性：如果兩個對象通過equals()判斷為相等，則它們的hashCode()必須返回相同的值；
• 對稱性：如果a.equals(b)為true，則b.equals(a)也必須為true；
• 非空性：a.equals(null)必須返回false。

4.put操作

1.初始化和數(shù)組檢查

首先判斷 HashMap 是否未初始化（table 數(shù)組為 null 或長度為 0），若是則觸發(fā) 初始化（resize）：

2.計算索引并檢查桶是否為空

如果該位置為空，直接創(chuàng)建新節(jié)點插入

3.桶不為null，處理哈希沖突

1. 檢查首節(jié)點：若首節(jié)點的 key 與傳入 key equals 相等（且哈希值相同），則視為 “重復 key”，記錄該節(jié)點（后續(xù)替換其 value）。
2. 遍歷后續(xù)節(jié)點：
   • 若桶是單鏈表（Node）：遍歷鏈表，若找到 key 相等的節(jié)點，記錄該節(jié)點；若遍歷到鏈表尾部仍未找到，則在鏈尾插入新節(jié)點（Node）。
   • 若桶是紅黑樹（TreeNode）：調(diào)用紅黑樹的插入方法（putTreeVal），若找到重復 key 則記錄節(jié)點，否則插入新樹節(jié)點。
3. 處理重復 key：若步驟 1 或 2 中找到重復 key 的節(jié)點，用新 value 替換其舊 value，流程結束。

4.判斷鏈表是否轉(zhuǎn)化紅黑樹

5.以及數(shù)組大小是否超過閾值進行擴容

5.get操作

同理get 方法的核心邏輯是：

哈希計算→定位桶→根據(jù)桶結構（鏈表 / 紅黑樹）查找匹配節(jié)點

java1.7 -- java1.8 HashMap 做了哪些優(yōu)化：

哈希值計算：

1.7版本：對 key 的原始哈希值（hashCode() 結果）進行 4 次擾動（多次移位和異或運算）

1.8版本：簡化為 1 次擾動，僅通過一次 “高 16 位與低 16 位異或” 實現(xiàn)混合

減少計算開銷：一次異或運算即可達到近似的混合效果，相比 1.7 的 4 次運算，計算效率更高。

實際效果：在大多數(shù)場景下，1 次擾動已能保證哈希值的均勻分布，同時降低了 CPU 運算成本。

鏈表插入方式：

由頭插變成尾插，核心是為了解決多線程擴容時的鏈表環(huán)化問題，同時讓鏈表操作邏輯更合理。

多線程擴容時可能導致鏈表環(huán)化（死循環(huán)）。

擴容過程中，節(jié)點會從舊數(shù)組遷移到新數(shù)組，頭插法在遷移時會反轉(zhuǎn)鏈表順序（例如舊鏈表 A→B，遷移后新鏈表變?yōu)?B→A）。若此時有多個線程同時操作，可能出現(xiàn)節(jié)點引用相互指向的情況（如 A.next = B 且 B.next = A），形成環(huán)形鏈表。后續(xù)查詢時，線程會陷入無限循環(huán)，導致 CPU 占用飆升。

二.ConcurrentHashMap

ConcurrentHashMap 是 Java 中用于并發(fā)場景的哈希表實現(xiàn)，專為高并發(fā)環(huán)境設計；

1.Java 1.7 ConcurrentHashMap架構：

在java1.8之前 ConcurrentHashMap 采用的是 分段數(shù)組（Segment）+ 哈希表 ， 默認為16個segment，同時支持16個并發(fā)~

• 整體結構：ConcurrentHashMap -> Segment[] -> HashEntry[] -> 鏈表。

• 寫操作（put/remove 等）：
  1. 計算 key 的哈希值，定位到對應的 Segment；
  2. 獲取該 Segment 的鎖（若被占用則阻塞）；
  3. 在 Segment 內(nèi)部的哈希表中執(zhí)行插入 / 刪除（類似 HashMap 的邏輯，鏈表頭插法）；
  4. 釋放鎖。

• 優(yōu)點：通過分段鎖實現(xiàn)了多線程并發(fā)寫，效率比全表鎖（如 Hashtable）高得多。
• 缺點：
  • 鎖粒度仍較大（以 Segment 為單位），若多個線程操作同一 Segment，仍會阻塞；
  • 結構復雜，維護成本高；
  • 擴容僅針對單個 Segment，但整體性能受限于 Segment 數(shù)量。

2.Java 1.8 ConcurrentHashMap架構：

摒棄了 Segment 分段結構，底層直接使用 數(shù)組 + 鏈表 + 紅黑樹（與 JDK 1.8 HashMap 結構類似）

鎖的粒度更小，鎖的是桶的頭節(jié)點，并且采取了CAS + synchronized 機制，僅當多個線程操作同一鏈表 / 紅黑樹時才會競爭鎖，鎖沖突概率遠低于 1.7 的 Segment 級鎖。

CAS+synchronized的使用場景：

1. 無沖突場景（空桶插入、初始化、低并發(fā)計數(shù)）：用 CAS 實現(xiàn)高效無鎖操作。
2. 有沖突場景（非空桶操作、復雜結構修改）：用 synchronized 加鎖保證原子性。

擴容區(qū)別：

size()區(qū)別：

在JDK 1.7 中，ConcurrentHashMap 由多個 Segment 組成，每個 Segment 獨立維護自己的元素數(shù)量（count），因此計算總 size 時需要累加所有 Segment 的 count。

• 為減少誤差，JDK 1.7 采用 “重試機制”：如果兩次連續(xù)累加的結果一致，則認為是準確值；若不一致（說明期間有并發(fā)修改），最多重試 3 次，若仍不一致則直接返回當前累加值（接受一定誤差）。

而在JDK 1.8中，計算 size 依賴于 baseCount 原子變量和 counterCells 輔助數(shù)組，通過無鎖累加實現(xiàn)，返回兩者的總和作為最終的 size。

當插入元素成功后，需要將總數(shù) +1，流程如下：

1. 優(yōu)先嘗試更新 baseCount：
   線程通過 CAS 操作直接更新 baseCount（baseCount + 1）。

   • 若 CAS 成功：計數(shù)完成，無需其他操作。
   • 若 CAS 失?。赫f明存在并發(fā)競爭（多個線程同時更新 baseCount），進入下一步。

2. 競爭激烈時，使用 counterCells 分散計數(shù)：

   • 若 counterCells 未初始化，先通過 CAS 初始化（創(chuàng)建一個 CounterCell 數(shù)組）。
   • 線程通過哈希算法（基于線程 ID 或隨機數(shù)）隨機選擇 counterCells 中的一個 CounterCell。
   • 嘗試用 CAS 更新該 CounterCell 的 value（value + 1）：
     • 若成功：計數(shù)完成。
     • 若失?。褐卦嚮蜻x擇其他 CounterCell（避免死鎖）。

總結 

到此這篇關于Java中HashMap用法詳細介紹的文章就介紹到這了,更多相關java hashmap詳解內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論