【重難點】【Java集合 01】HashMap 和 ConcurrentHashMap

【重難點】【Java集合 01】HashMap

文章目錄

• 【重難點】【Java集合 01】HashMap
• 一、HashMap
• • 1.概述
  • 2.JDK 1.8 中的變化
  • 3.連結清單轉換為紅黑樹
  • 4.擴容問題
  • 5.加載因子
  • 6.添加新結點的完整流程
  • 7.擴容時的循環連結清單問題
  • 8.HashMap 和 TreeMap 的對比
  • 9.HashMap 和 LinkedHashMap 的對比
• 二、ConcurrentHashMap
• • 1.ConcurrentHashMap 和 HashMap 的對比
  • 2.JDK 1.7
  • 3.JDK 1.8

一、HashMap

1.概述

HashMap 是一個散清單，它存儲的内容是鍵值對（Key-Value）映射，JDK 1.2 時引入

從結構實作來講，HashMap 是數組 + 連結清單 + 紅黑樹（JDK 1.8 引入）實作的，如下圖所示

HashMap 實作了 Map 接口，根據鍵的 HashCode 值存儲資料，具有很快的通路速度，最多允許一條記錄的鍵為 null，不支援線程同步

其繼承關系如下圖所示：

2.JDK 1.8 中的變化

資料結構的變化：引入了紅黑樹

有關紅黑樹的内容請移步【Java 資料結構與算法】第十四章 紅黑樹，我進行了詳細地講解

JDK 1.8 之前，HashMap 由數組 + 連結清單組成，數組是 HashMap 的主體，連結清單主要是為了解決哈希沖突而存在的，我在【重難點】【Java基礎 02】Arrays.sort() 、建立對象的 5 種方式、hashCode() 的作用、解決哈希沖突的方法 中簡單介紹了解決哈希沖突的四種方法

JDK 1.8 以後，在解決哈希沖突時有了較大的變化，當連結清單長度大于門檻值（預設為 8），且目前數組的長度大于 64 時，此索引位置上的資料改為使用紅黑樹存儲

table 數組的類型由 Entry 改成了 Node

Entry 是 HashMap 中在 JDK 1.8 之前的一個靜态内部類，在 1.8 改成了 Node

并且在 JDK 1.8 以後就不是在構造時建立數組了，而是在第一次調用 put 方法時才建立

簡化了 hash() 函數算法

JDK 1.8 之前

final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
 
        h ^= k.hashCode();
 
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
           

JDK 1.8 以後

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

若 key 為 null，傳回 0；若 key 不為 null，則計算 key 的 hashCode 值，将結果右移 16 位之後，做異或運算

向連結清單中加入資料時采用尾插法

因為在多線程的場景下使用原來的頭插法會出現循環連結清單的情況

3.連結清單轉換為紅黑樹

上面提到，當連結清單長度超過門檻值時會将目前連結清單上的資料使用紅黑樹進行存儲。這裡的門檻值是可以自定義的，預設為 8。此外，還有一個很重要的條件，就是數組的長度也要大于等于 64，否則即使有連結清單長度超過門檻值，也不會轉換為紅黑樹，而是進行擴容，重新散列

樹結點的大小約是普通結點的兩倍，當數組較小時，我們要盡量避免使用紅黑樹，這種情況下将連結清單變為紅黑樹結構反而會降低效率。不僅僅是因為樹節點占更多空間，而且每次添加新結點時，紅黑樹可能需要進行一些較為複雜的操作來保持紅黑樹的結構穩定

JDK 1.8 引入紅黑樹的原因當然是為了提高查找效率，雖然紅黑樹使得 HashMap 底層資料結構變得複雜，但是當連結清單結點數超過 8，且數組長度大于 64 時，使用紅黑樹效率比連結清單更高

長度為 8 時，紅黑樹的平均查找時間為 log(8) = 3，連結清單的平均查找時間為 8 / 2 = 4，且長度越大，紅黑樹的優勢越明顯

當長度為 6 時，紅黑樹的平均查找時間為 log(6) = 2.6，連結清單的平均查找時間為 6 / 2 = 3，雖然紅黑樹還是比連結清單查找得要快，但是随着長度變小，紅黑樹的優勢就逐漸被連結清單追上，并且将連結清單轉換為樹結構也要花費不少的時間

是以在結點數減少為 6 時，紅黑樹又會轉化為連結清單了。那麼為什麼不是結點數為 7 的時候退化呢？這也很好了解，為 8 就轉化為紅黑樹，為 7 就轉化為連結清單，如果僅僅是變化了 1 個結點就要進行來回轉化，這也太耗費時間了，是以把 7 作為緩沖

4.擴容問題

在不斷地添加資料的過程中，會涉及到擴容問題。當數組長度即将超過門檻值時就會進行擴容，預設的擴容方式是将數組容量擴容到原來的 2 倍，并重新散列

HashMap 的容量總是 2 的 n 次方，這是什麼原因呢？

當向 HashMap 中添加一個元素的時候，需要根據 Key 的 hash 值确定其在數組中的具體位置，這就需要進行取模運算。而 CPU 是采用二進制進行運算的，是以取模運算的效率遠不如位運算，在一個公式下，是可以用位運算代替取模運算的，這個公式為：

hash % length = hash & (length - 1)

length 為 2 的 n 次方是這個公式成立的條件。并且，當 length 不為 2 的 n 次方時，計算出的索引就特别容易相同，導緻資料存儲集中在幾個索引中，連結清單和紅黑樹也會随之變長，查找效率大打折扣

并且這個規則是固定的，即使我們在建立 HashMap 時指定的數組長度不為 2 的 n 次方，底層也會自動将其變為大于我們指定長度且離其最近的 2 的 n 次方

數組的最大上限為 2 的 30 次方

5.加載因子

加載因子（loadFactor）也叫負載因子，是用來衡量 HashMap 是否需要擴容的重要條件，通過 length * loadFactory 可以算出需要擴容的門檻值，loadFactory 預設為 0.75，當 HashMap 裡面已用索引長度已經達到數組總長度的 75% 時說明 HashMap 太擠了，需要進行擴容

我們知道，如果進行擴容就需要重新散列，這是非常消耗性能的，是以開發中需要盡量減少擴容的次數，那是不是加載因子越大越好呢？

當然不是，JDK 開發人員一定是進行過嚴謹的計算才得出 0.75 這個數值的。加載因子越趨近于 1 ，數組中存放的資料也就越多，導緻查詢效率降低；加載因子越小，數組中存放的資料也就越少，導緻資料使用率過低

6.添加新結點的完整流程

7.擴容時的循環連結清單問題

這個問題隻會出現在 JDK 1.7 頭插法和多線程的場景下

有線程 α 和 線程 β，此時線程 α 正在擴容，在擴容時，原本的最後一個元素 A 會重新放入到數組中；同時，線程 β 添加結點 B 進來，如果是頭插法，理想的情況是這樣的：

而實際可能出現如下的問題：

在 HashMap 中，擴容的方法為 resize(int newCapacity)

resize() 中調用了一個方法 transfer(newTable, initHashSeedASNeeded(newCapacity))

transfer 裡會執行具體的擴容操作，newTable 是一個新的 Entry[] 數組

void transfer(Entry[] newTable, boolean rehash){
	int newCapacity = newTable.length;	//容量
	for(Entry<K,V> e : table){	//周遊 table[1,2,3,4,5]
		while(null != e){	//周遊 table 中的連結清單 table[i]
			
			Entry<K,V> next = e.next;	//α 線程在跑，而 β 線程沒在跑
			if(rehash){	//如果 rehash 需要重新計算 hash 值
				e.hash = null == e.key ? 0 : hash(e.key);
			}
	
			int i = indexFor(e.hash, newCapacity);	//定位索引
			//元素插入對應連結清單中，頭插法
			//newTable[i] 的值總是最新插入的值
			newTable[i] = e;
			//繼續下一個元素
			e = next;
		}
	}
}		
           

我們舉一個例子，有兩個線程，線程 1 和線程 2。線程 1 和線程 2 都處于 if(rehash) 的位置，即将進行擴容，隻是線程 1 處于喚醒狀态即将進行擴容，線程 2 要等到線程 1 擴容完成後才能被喚醒再進行擴容操作

下圖是線程 1 還未進行擴容的情形，此時線程 1 和線程 2 的指針都指向 3 和 2 ：

線程1 擴容完成之後，線程 2 被喚醒，我們可以發現，e2 和 next 2 的位置已經颠倒了，已經開始出錯，但是線程 2 并不知道：

線程 2 從 if(rehash) 處一步一步将代碼全部執行完就會出現下面的情形：

綜上我們可以看出，導緻環形連結清單出現的根本原因就是頭插法，擴容時頭插法打亂了連結清單的順序，導緻兩個線程的資料結構不一緻

8.HashMap 和 TreeMap 的對比

相同點：

都繼承了 AbstractMap，都是非線程安全的

不同點：

• 實作方式
  • HashMap 基于哈希表實作，使用 HashMap 要求添加的鍵類明确定義了 hashCode() 和 equals()，可以通過調整初始容量和加載因子優化 HashMap 的空間使用
  • TreeMap 基于紅黑樹實作，該樹總是處于平衡狀态，是以沒有調優選項
• 存儲方式
  • HashMap：随機存儲
  • TreeMap：預設按鍵的升序排序
• 周遊方式
  • HashMap：Iterator 周遊是随機的
  • TreeMap：Iterator 周遊是有序的
• 性能損耗：
  • HashMap：基本沒有
  • TreeMap：插入和删除時有
• 是否允許為 NULL
  • HashMap：隻允許鍵、值均為 NULL
  • TreeMap：鍵、值均不能為 NULL
• 效率
  • HashMap：高
  • TreeMap：低

總結：

一般情況下我們選用 HashMap，因為 HashMap 的鍵值對再取出時是随機的，其依據鍵的 hashCode 和鍵的 equals 方法存取資料，具有很快的通路速度，是以在 Map 中插入、删除及索引元素時其是效率最高的實作

而 TreeMap 的鍵值對在取出時是排過序的，是以效率會低一些

9.HashMap 和 LinkedHashMap 的對比

LinkedHashMap 是 HashMap 的子類，隻是 LinkedHashMap 重寫了 newNode() 方法，在該方法中将每個新生成的節點與已經存在的節點用雙向連結清單連接配接起來，可以了解為 LinkedHashMap 及采用了哈希表（拉鍊法和紅黑樹）存儲，也采用了雙向連結清單存儲，更準确地說，它是一個将所有 Entry 節點鍊入一個雙向連結清單的 HashMap。值得一提的是，因為它額外維護了一個雙向連結清單用于保持疊代順序，是以 LinkedHashMap 可以很好地支援 LRU（Least Recently Used）算法

二、ConcurrentHashMap

1.ConcurrentHashMap 和 HashMap 的對比

ConcurrentHashMap 和 HashMap 之間的第一個重要的差別就是 ConcurrentHashMap 是線程安全的，且在并發環境下不需要加額外的同步

ConcurrentHashMap 具有很好的擴充性，在多線程環境下性能方面比做了同步的 HashMap 要好，但在單線程環境下，HashMap 會更好

ConcurrentHashMap 比 HashMap 更适合用于緩存

ConcurrentHashMap 更适合讀操作線程數多于寫操作線程數的情況

ConcurrentHashMap 既不允許 key 值為 NULL，也不允許 value 值為 NULL

2.JDK 1.7

基本介紹

通過使用段 (Segment) 将 ConcurrentHashMap 劃分為不同的部分，ConcurrentHashMap 就可以使用不同的鎖來控制對哈希表的不同部分的修改，進而允許多個修改操作并發進行, 這是 ConcurrentHashMap 鎖分段技術的核心内涵

ConcurrentHashMap 類中包含兩個靜态内部類 HashEntry 和 Segment，其中 HashEntry 用來封裝具體的鍵值對，而 Segement 用來充當鎖的角色，每個 Segment 對象守護整個 ConcurrentHashMap 的若幹個桶（可以把 Segment 看作是一個小型的哈希表），其中每個桶是由若幹個 HashEntry 對象連結起來的連結清單。也就是說一個 ConcurrentHashMap 執行個體中包含若幹個 Segement 執行個體組成的數組，而一個 Segment 執行個體又包含若幹個桶，每個桶中都包含一條有若幹個 HashEntry 對象連結起來的連結清單。ConcurrentHashMap 在預設并發級别下會建立 16 個 Segment 對象的數組，如果鍵能均勻散列，每個 Segment 大約守護整個散清單中桶總數的 1 / 16

ConcurrentHashMap 繼承了 AbstractMap，并實作了 ConcurrentMap 接口

與 HashMap 相比，ConcurrentHashMap 增加了兩個屬性用于定位段，分别是 segmentMask 和 segmentShift。此外，ConcurrentHashMap 底層結構是一個 Segment 數組，而不是 Object 數組

Segment

Segment 類繼承自 ReentrantLock 類，進而使得 Segment 對象能充當鎖的角色。每個 Segment 對象用來守護它的成員對象 table 中包含的若幹個桶。table 是一個由 HashEntry 對象組成的連結清單數組，table 數組的每一個數組成員就是一個桶

在 Segment 類中，count 變量是一個計數器，它表示每個 Segment 對象管理的 table 數組包含的 HashEntry 對象的個數，也就是 Segment 中包含的 HashEntry 對象的總數。特别需要注意的是，之是以在每個 Segment 對象中包含一個計數器，而不是在 ConcurrentHashMap 中使用全局計數器，是對 ConcurrentHashMap 并發性的考慮，當需要更新計數器時，不用鎖定整個 ConcurrentHashMap。事實上，每次對段進行結構上的改變，如在段中進行增加 / 删除節點（修改節點的值不算結構上的改變），都要更新 count 的值。此外，在 JDK 的實作中，每次讀取操作開始時都要先讀取 count 的值。特别需要注意的是，count 被 volatile 修飾，這使得 count 的任何更新對其它線程都是立即可見的。modCount 用于統計段結構改變的次數，主要是為了檢測對多個段進行周遊過程中某個段是否發生改變，這一點具體在談到跨段操作時會詳述u。threashold 用來表示段需要進行擴容的門檻值。loadFactor 表示段的加載因子，其值等同于 ConcurrentHashMap 的加載因子。table 是一個典型的連結清單數組，而且也被 volatile 修飾，這使得 table 的任何更新對其它線程也是立即可見的

ConcurrentHashMap 允許多個修改（寫）操作并發進行，其關鍵在于使用了鎖分段技術，它使用了不同的鎖來控制對哈希表的不同部分進行修改（寫），而 ConcurrentHashMap 内部使用段（Segment）來表示這些不同的部分。實際上，每個段實質上時一個小的哈希表，每個段都有自己的鎖。這樣，隻要多個修改（寫）操作發生在不同的段上，它們就可以并發進行，下圖是依次插入 ABC 三個 HashEntry 結點後，Segment 的結構示意圖：

HashEntry

HashEntry 用來封裝具體的鍵值對，與 HashMap 中的 Entry 類似，HashEntry 也包括同樣的四個域，分别是 Key、hash、value 和 next。不同的是，在 HashEntry 類中，key、hash 和 next 域都被聲明為 final，而 value 域被 volatile 修飾，是以 HashEntry 對象幾乎是不可變的，這是 ConcurrentHashMap 讀操作并不需要加鎖的一個重要原因。next 域被聲明為 fianl 本身就意味着我們不能從 hash 鍊的中間或尾部添加或删除節點，因為這需要修改 next 引用值，是以所有節點的修改隻能從頭部開始。對于 put 操作，可以一律添加到 Hash 鍊的頭部。但是對于 remove 操作，可能需要從中間删除一個節點，這就需要将要删除節點的前面所有的節點複制一份，讓最後一個節點指向要删除節點的下一個節點。特别地，由于 value 域被 volatile 修飾，是以其可以確定被讀線程讀到最新的值，這是 ConcurrentHashMap 讀操作并不需要加鎖的另一個重要原因。實際上，ConcurrentHashMap 完全允許多個讀操作并發進行，讀操作并不需要加鎖

put 操作

Sement 繼承了 ReentrantLock，也就帶有鎖的功能，當執行 put 操作時。首先會對 key 進行第一次 hash 計算，來定位 Segment 的位置，，然後進行第二次 hash 計算，找到對應的 HashEntry 的位置，這裡會利用繼承過來的鎖的特性，在将資料插入指定的 HashEntry 位置時（連結清單的尾端），會通過繼承 ReentrantLock 的 tryLock() 方法嘗試去擷取鎖，如果擷取成功就直接插入相應的位置，如果已經有線程擷取該 Segment 的鎖，那目前線程會以自旋的方式繼續調用 tryLock() 方法去擷取鎖，超過指定次數就挂起，等待喚醒

get 操作

ConcurrentHashMap 的 get 操作跟 HashMap 類似，隻是 ConcurrentHashMap 需要先進行一次 hash 計算定位到 Segment 的位置，然後進行一次 hash 計算，定位到指定的 HashEntry

擷取 size

計算 ConcurrentHashMap 的 size是一個有趣的問題，因為它是并發操作的。當你計算 size 的時候，它還在并發地插入資料，可能會導緻結果偏差，要解決這個問題，JDK 1.7 采用兩種方案：

1. 使用不加鎖的模式去嘗試多此計算 size，對多三次，比較計算結果，結果一緻就認為目前沒有元素加入
2. 如果第一種方案結果不一緻，就會給每個 Sement 加鎖，然後再計算 ConcurrentHashMap 的 size

3.JDK 1.8

改進一：摒棄了 Segment 的概念，直接采用 transient volatile HashEntry<K，V>[ ] table 儲存資料，使用 table 數組元素作為鎖，進而實作了對每一行資料進行加鎖，進一步減少并發沖突的機率。雖然在 JDK 1.8 中還能看到 Segment 的資料結構，但是已經簡化了屬性，隻是為了相容舊版本

改進二：将原先 table 數組 + 單向連結清單的資料結構，變更為 table 數組 + 單向連結清單 + 紅黑樹的結構

put 操作

1. 如果沒有初始化就先調用 initTable() 初始化
2. 如果沒有哈希沖突就直接 CAS 插入
3. 如果還在進行擴容操作就先進行擴容
4. 如果存在哈希沖突就加鎖來保證線程安全，這裡有兩種情況：一種是連結清單形式尾插法；另一種是紅黑樹
5. 如果該連結清單的節點數大于門檻值，就要先轉換成紅黑樹
6. 如果添加成功就調用 addCount() 統計 size，并檢查是否需要擴容

put 操作在并發進行中使用的是樂觀鎖，當有沖突的時候才進行并發處理

get 操作

1. 計算 hash 值，定位到 table 索引位置，如果首節點符合就傳回
2. 如果遇到擴容的時候，會調用标志正在擴容節點 ForwardingNode 的 find 方法，查找該節點，比對到就傳回
3. 以上都不符合的化就向下周遊節點，比對到就傳回，否則傳回 NUL

擷取 size

對于 size 的計算，在擴容和 addCount() 就已經計算好了，你需要擷取 size 的時候直接給你