一.HashMap

1.基本概念

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

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

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

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

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

從源碼上查看

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

當(dāng)插入第13個(gè)元素的時(shí)候，已經(jīng)超過閾值，為了避免哈希沖突，會(huì)進(jìn)行擴(kuò)容~

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

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

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

3.HashCode和equals方法

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

為什么重寫HashCode方法？

如果不重寫，這個(gè)時(shí)候，就會(huì)導(dǎo)致倆個(gè)相同的key，會(huì)被計(jì)算出倆個(gè)不同的哈希值，導(dǎo)致他們存在在不同的桶中，到時(shí)候查詢的時(shí)候到底是查哪個(gè)？

為什么重新equals方法？

equals方法是為了當(dāng)出現(xiàn)哈希沖突的時(shí)候，倆個(gè)key的哈希值相同，放在同一桶中，但沒有比較它們的對(duì)象，可能會(huì)誤判會(huì)導(dǎo)致倆個(gè)key存儲(chǔ)在不同位置，所以沒有覆蓋之前的值，就會(huì)錯(cuò)誤~

class Person {
    String name;
    int age;
    @Override
    public int hashCode() { // 重寫hashCode，保證邏輯相等的對(duì)象哈希值相同
        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, "學(xué)生");
    map.put(p2, "工人"); // 哈希值相同，進(jìn)入同一個(gè)桶，但equals判斷為不同key
    System.out.println(map.size()); // 仍輸出2，而非預(yù)期的1
}

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

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

4.put操作

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

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

2.計(jì)算索引并檢查桶是否為空

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

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

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

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

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

5.get操作

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

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

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

哈希值計(jì)算：

1.7版本：對(duì) key 的原始哈希值（hashCode() 結(jié)果）進(jìn)行 4 次擾動(dòng)（多次移位和異或運(yùn)算）

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

減少計(jì)算開銷：一次異或運(yùn)算即可達(dá)到近似的混合效果，相比 1.7 的 4 次運(yùn)算，計(jì)算效率更高。

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

鏈表插入方式：

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

多線程擴(kuò)容時(shí)可能導(dǎo)致鏈表環(huán)化（死循環(huán)）。

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

二.ConcurrentHashMap

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

1.Java 1.7 ConcurrentHashMap架構(gòu)：

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

• 整體結(jié)構(gòu)：ConcurrentHashMap -> Segment[] -> HashEntry[] -> 鏈表。

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

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

2.Java 1.8 ConcurrentHashMap架構(gòu)：

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

鎖的粒度更小，鎖的是桶的頭節(jié)點(diǎn)，并且采取了CAS + synchronized 機(jī)制，僅當(dāng)多個(gè)線程操作同一鏈表 / 紅黑樹時(shí)才會(huì)競(jìng)爭鎖，鎖沖突概率遠(yuǎn)低于 1.7 的 Segment 級(jí)鎖。

CAS+synchronized的使用場(chǎng)景：

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

擴(kuò)容區(qū)別：

size()區(qū)別：

在JDK 1.7 中，ConcurrentHashMap 由多個(gè) Segment 組成，每個(gè) Segment 獨(dú)立維護(hù)自己的元素?cái)?shù)量（count），因此計(jì)算總 size 時(shí)需要累加所有 Segment 的 count。

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

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

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

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

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

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

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

總結(jié) 

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

最新評(píng)論