ConcurrentHashMap高并發的原理

簡介

ConcurrentHashMap 是 util.concurrent 包的重要成員。本文将結合 Java 記憶體模型，分析 JDK 源代碼，探索 ConcurrentHashMap 高并發的具體實作機制。

由于 ConcurrentHashMap 的源代碼實作依賴于 Java 記憶體模型，是以閱讀本文需要讀者了解 Java 記憶體模型。同時，ConcurrentHashMap 的源代碼會涉及到雜湊演算法和連結清單資料結構，是以，讀者需要對雜湊演算法和基于連結清單的資料結構有所了解。

Java 記憶體模型

由于 ConcurrentHashMap 是建立在 Java 記憶體模型基礎上的，為了更好的了解 ConcurrentHashMap，讓我們首先來了解一下 Java 的記憶體模型。

Java 語言的記憶體模型由一些規則組成，這些規則确定線程對記憶體的通路如何排序以及何時可以確定它們對線程是可見的。下面我們将分别介紹 Java 記憶體模型的重排序，記憶體可見性和 happens-before 關系。

重排序

記憶體模型描述了程式的可能行為。具體的編譯器實作可以産生任意它喜歡的代碼 -- 隻要所有執行這些代碼産生的結果，能夠和記憶體模型預測的結果保持一緻。這為編譯器實作者提供了很大的自由，包括操作的重排序。

編譯器生成指令的次序，可以不同于源代碼所暗示的“顯然”版本。重排序後的指令，對于優化執行以及成熟的全局寄存器配置設定算法的使用，都是大有脾益的，它使得程式在計算性能上有了很大的提升。

重排序類型包括：

• 編譯器生成指令的次序，可以不同于源代碼所暗示的“顯然”版本。
• 處理器可以亂序或者并行的執行指令。
• 緩存會改變寫入送出到主記憶體的變量的次序。

記憶體可見性

由于現代可共享記憶體的多處理器架構可能導緻一個線程無法馬上（甚至永遠）看到另一個線程操作産生的結果。是以 Java 記憶體模型規定了 JVM 的一種最小保證：什麼時候寫入一個變量對其他線程可見。

在現代可共享記憶體的多處理器體系結構中每個處理器都有自己的緩存，并周期性的與主記憶體協調一緻。假設線程 A 寫入一個變量值 V，随後另一個線程 B 讀取變量 V 的值，在下列情況下，線程 B 讀取的值可能不是線程 A 寫入的最新值：

• 執行線程 A 的處理器把變量 V 緩存到寄存器中。
• 執行線程 A 的處理器把變量 V 緩存到自己的緩存中，但還沒有同步重新整理到主記憶體中去。
• 執行線程 B 的處理器的緩存中有變量 V 的舊值。

Happens-before 關系

happens-before 關系保證：如果線程 A 與線程 B 滿足 happens-before 關系，則線程 A 執行動作的結果對于線程 B 是可見的。如果兩個操作未按 happens-before 排序，JVM 将可以對他們任意重排序。

下面介紹幾個與了解 ConcurrentHashMap 有關的 happens-before 關系法則：

1. 程式次序法則：如果在程式中，所有動作 A 出現在動作 B 之前，則線程中的每動作 A 都 happens-before 于該線程中的每一個動作 B。
2. 螢幕鎖法則：對一個螢幕的解鎖 happens-before 于每個後續對同一螢幕的加鎖。
3. Volatile 變量法則：對 Volatile 域的寫入操作 happens-before 于每個後續對同一 Volatile 的讀操作。
4. 傳遞性：如果 A happens-before 于 B，且 B happens-before C，則 A happens-before C。

ConcurrentHashMap 的結構分析

為了更好的了解 ConcurrentHashMap 高并發的具體實作，讓我們先探索它的結構模型。

ConcurrentHashMap 類中包含兩個靜态内部類 HashEntry 和 Segment。HashEntry 用來封裝映射表的鍵 / 值對；Segment 用來充當鎖的角色，每個 Segment 對象守護整個散列映射表的若幹個桶。每個桶是由若幹個 HashEntry 對象連結起來的連結清單。一個 ConcurrentHashMap 執行個體中包含由若幹個 Segment 對象組成的數組。

HashEntry 類

HashEntry 用來封裝散列映射表中的鍵值對。在 HashEntry 類中，key，hash 和 next 域都被聲明為 final 型，value 域被聲明為 volatile 型。

清單 1.HashEntry 類的定義

1 2 3 4 5 6 7 8 9 10 11 12 13

static final class HashEntry< K ,V> { final K key;                       // 聲明 key 為 final 型 final int hash;                   // 聲明 hash 值為 final 型 volatile V value;                 // 聲明 value 為 volatile 型 final HashEntry< K ,V> next;      // 聲明 next 為 final 型 HashEntry(K key, int hash, HashEntry< K ,V> next, V value) { this.key = key; this.hash = hash; this.next = next; this.value = value; } }

在 ConcurrentHashMap 中，在散列時如果産生“碰撞”，将采用“分離連結法”來處理“碰撞”：把“碰撞”的 HashEntry 對象連結成一個連結清單。由于 HashEntry 的 next 域為 final 型，是以新節點隻能在連結清單的表頭處插入。 下圖是在一個空桶中依次插入 A，B，C 三個 HashEntry 對象後的結構圖：

圖 1. 插入三個節點後桶的結構示意圖：

注意：由于隻能在表頭插入，是以連結清單中節點的順序和插入的順序相反。

避免熱點域

在 

ConcurrentHashMap

中，

每一個 Segment 對象都有一個 count 對象來表示本 Segment 中包含的 HashEntry 對象的個數。這樣當需要更新計數器時，不用鎖定整個 

ConcurrentHashMap

。

Segment 類

Segment 類繼承于 ReentrantLock 類，進而使得 Segment 對象能充當鎖的角色。每個 Segment 對象用來守護其（成員對象 table 中）包含的若幹個桶。

table 是一個由 HashEntry 對象組成的數組。table 數組的每一個數組成員就是散列映射表的一個桶。

count 變量是一個計數器，它表示每個 Segment 對象管理的 table 數組（若幹個 HashEntry 組成的連結清單）包含的 HashEntry 對象的個數。每一個 Segment 對象都有一個 count 對象來表示本 Segment 中包含的 HashEntry 對象的總數。注意，之是以在每個 Segment 對象中包含一個計數器，而不是在 

ConcurrentHashMap 中使用全局的計數器，是為了避免出現“熱點域”而影響 ConcurrentHashMap 的并發性。

清單 2.Segment 類的定義

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

static final class Segment< K ,V> extends ReentrantLock implements Serializable { transient volatile int count; transient int modCount; transient int threshold; transient volatile HashEntry< K ,V>[] table; final float loadFactor; Segment(int initialCapacity, float lf) { loadFactor = lf; setTable(HashEntry.< K ,V>newArray(initialCapacity)); } void setTable(HashEntry< K ,V>[] newTable) { // 計算臨界閥值為新數組的長度與裝載因子的乘積 threshold = (int)(newTable.length * loadFactor); table = newTable; } HashEntry< K ,V> getFirst(int hash) { HashEntry< K ,V>[] tab = table; // 把散列值與 table 數組長度減 1 的值相“與”， // 得到散列值對應的 table 數組的下标 // 然後傳回 table 數組中此下标對應的 HashEntry 元素 return tab[hash & (tab.length - 1)]; } }

下圖是依次插入 ABC 三個 HashEntry 節點後，Segment 的結構示意圖。

圖 2. 插入三個節點後 Segment 的結構示意圖：

ConcurrentHashMap 類

ConcurrentHashMap 在預設并發級别會建立包含 16 個 Segment 對象的數組。每個 Segment 的成員對象 table 包含若幹個散清單的桶。每個桶是由 HashEntry 連結起來的一個連結清單。如果鍵能均勻散列，每個 Segment 大約守護整個散清單中桶總數的 1/16。

清單 3.ConcurrentHashMap 類的定義

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

public class ConcurrentHashMap< K , V> extends AbstractMap< K , V> implements ConcurrentMap< K , V>, Serializable { static final     int DEFAULT_INITIAL_CAPACITY= 16; static final float DEFAULT_LOAD_FACTOR= 0.75f; static final int DEFAULT_CONCURRENCY_LEVEL= 16; final int segmentMask; final int segmentShift; final Segment< K ,V>[] segments; public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if(!(loadFactor > 0) || initialCapacity < || concurrencyLevel <= 0) throw new IllegalArgumentException(); if(concurrencyLevel > MAX_SEGMENTS) concurrencyLevel = MAX_SEGMENTS; // 尋找最佳比對參數（不小于給定參數的最接近的 2 次幂） int sshift = 0; int ssize = 1; while(ssize < concurrencyLevel ) { ++sshift; ssize <<= 1; } segmentShift = 32 - sshift;       // 偏移量值 segmentMask = ssize - 1;           // 掩碼值 this.segments = Segment .newArray(ssize);   // 建立數組 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; int c = initialCapacity / ssize; if(c * ssize < initialCapacity ) ++c; int cap = 1 ; while(cap < c) cap <<= 1; // 依次周遊每個數組元素 for(int i = ; i < this.segments.length; ++i) // 初始化每個數組元素引用的 Segment 對象 this.segments[i] = new Segment<K,V>(cap, loadFactor); } public ConcurrentHashMap() { // 使用三個預設參數，調用上面重載的構造函數來建立空散列映射表 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); }

}

下面是 ConcurrentHashMap 的結構示意圖。

圖 3.ConcurrentHashMap 的結構示意圖：

用分離鎖實作多個線程間的并發寫操作

在 ConcurrentHashMap 中，線程對映射表做讀操作時，一般情況下不需要加鎖就可以完成，對容器做結構性修改的操作才需要加鎖。下面以 put 操作為例說明對 ConcurrentHashMap 做結構性修改的過程。

首先，根據 key 計算出對應的 hash 值：

清單 4.Put 方法的實作

1 2 3 4 5 6 7

public V put(K key, V value) { if (value == null)          //ConcurrentHashMap 中不允許用 null 作為映射值 throw new NullPointerException(); int hash = hash(key.hashCode());        // 計算鍵對應的散列碼 // 根據散列碼找到對應的 Segment return segmentFor(hash).put(key, hash, value, false); }

然後，根據 hash 值找到對應的

Segment 對象：

清單 5.根據 hash 值找到對應的 Segment

1 2 3 4 5 6 7 8 9 10

final Segment< K ,V> segmentFor(int hash) { // 将散列值右移 segmentShift 個位，并在高位填充 0 // 然後把得到的值與 segmentMask 相“與” // 進而得到 hash 值對應的 segments 數組的下标值 // 最後根據下标值傳回散列碼對應的 Segment 對象 return segments[(hash >>> segmentShift) & segmentMask]; }

最後，在這個 Segment 中執行具體的 put 操作：

清單 6.在 Segment 中執行具體的 put 操作

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

V put(K key, int hash, V value, boolean onlyIfAbsent) { lock();  // 加鎖，這裡是鎖定某個 Segment 對象而非整個 ConcurrentHashMap try { int c = count; if (c++ > threshold)     // 如果超過再散列的門檻值 rehash();              // 執行再散列，table 數組的長度将擴充一倍 HashEntry< K ,V>[] tab = table; // 把散列碼值與 table 數組的長度減 1 的值相“與” // 得到該散列碼對應的 table 數組的下标值 int index = hash & (tab.length - 1); // 找到散列碼對應的具體的那個桶 HashEntry< K ,V> first = tab[index]; HashEntry< K ,V> e = first; while (e != null && (e.hash != hash || !key.equals(e.key))) e = e.next; V oldValue; if (e != null) {            // 如果鍵 / 值對以經存在 oldValue = e.value; if (!onlyIfAbsent) e.value = value;    // 設定 value 值 } else {                        // 鍵 / 值對不存在 oldValue = null; ++modCount;         // 要添加新節點到連結清單中，是以 modCont 要加 1  // 建立新節點，并添加到連結清單的頭部 tab[index] = new HashEntry< K ,V>(key, hash, first, value); count = c;               // 寫 count 變量 } return oldValue; } finally { unlock();                     // 解鎖 } }

注意：這裡的加鎖操作是針對（鍵的 hash 值對應的）某個具體的 Segment，鎖定的是該 Segment 而不是整個 ConcurrentHashMap

。因為插入鍵 / 值對操作隻是在這個 Segment 包含的某個桶中完成，不需要鎖定整個

ConcurrentHashMap。

此時，其他寫線程對另外 15 個

Segment 的加鎖并不會因為目前線程對這個 Segment 的加鎖而阻塞。同時，所有讀線程幾乎不會因本線程的加鎖而阻塞（除非讀線程剛好讀到這個 Segment 中某個 

HashEntry 的 value 域的值為 null，此時需要加鎖後重新讀取該值

）。

相比較于 

HashTable 和由同步包裝器包裝的 HashMap

每次隻能有一個線程執行讀或寫操作，

ConcurrentHashMap 在并發通路性能上有了質的提高。在理想狀态下，ConcurrentHashMap 可以支援 16 個線程執行并發寫操作（如果并發級别設定為 16），及任意數量線程的讀操作。

用 HashEntery 對象的不變性來降低讀操作對加鎖的需求

在代碼清單“HashEntry 類的定義”中我們可以看到，HashEntry 中的 key，hash，next 都聲明為 final 型。這意味着，不能把節點添加到連結的中間和尾部，也不能在連結的中間和尾部删除節點。這個特性可以保證：在通路某個節點時，這個節點之後的連結不會被改變。這個特性可以大大降低處理連結清單時的複雜性。

同時，HashEntry 類的 value 域被聲明為 Volatile 型，Java 的記憶體模型可以保證：某個寫線程對 value 域的寫入馬上可以被後續的某個讀線程“看”到。在 ConcurrentHashMap 中，不允許用 unll 作為鍵和值，當讀線程讀到某個 HashEntry 的 value 域的值為 null 時，便知道産生了沖突——發生了重排序現象，需要加鎖後重新讀入這個 value 值。這些特性互相配合，使得讀線程即使在不加鎖狀态下，也能正确通路 ConcurrentHashMap。

下面我們分别來分析線程寫入的兩種情形：對散清單做非結構性修改的操作和對散清單做結構性修改的操作。

非結構性修改操作隻是更改某個 HashEntry 的 value 域的值。由于對 Volatile 變量的寫入操作将與随後對這個變量的讀操作進行同步。當一個寫線程修改了某個 HashEntry 的 value 域後，另一個讀線程讀這個值域，Java 記憶體模型能夠保證讀線程讀取的一定是更新後的值。是以，寫線程對連結清單的非結構性修改能夠被後續不加鎖的讀線程“看到”。

對 ConcurrentHashMap 做結構性修改，實質上是對某個桶指向的連結清單做結構性修改。如果能夠確定：在讀線程周遊一個連結清單期間，寫線程對這個連結清單所做的結構性修改不影響讀線程繼續正常周遊這個連結清單。那麼讀 / 寫線程之間就可以安全并發通路這個 ConcurrentHashMap。

結構性修改操作包括 put，remove，clear。下面我們分别分析這三個操作。

clear 操作隻是把 ConcurrentHashMap 中所有的桶“置空”，每個桶之前引用的連結清單依然存在，隻是桶不再引用到這些連結清單（所有連結清單的結構并沒有被修改）。正在周遊某個連結清單的讀線程依然可以正常執行對該連結清單的周遊。

從上面的代碼清單“在 Segment 中執行具體的 put 操作”中，我們可以看出：put 操作如果需要插入一個新節點到連結清單中時 , 會在連結清單頭部插入這個新節點。此時，連結清單中的原有節點的連結并沒有被修改。也就是說：插入新健 / 值對到連結清單中的操作不會影響讀線程正常周遊這個連結清單。

下面來分析 remove 操作，先讓我們來看看 remove 操作的源代碼實作。

清單 7.remove 操作

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

V remove(Object key, int hash, Object value) { lock();         // 加鎖 try{ int c = count - 1; HashEntry< K ,V>[] tab = table; // 根據散列碼找到 table 的下标值 int index = hash & (tab.length - 1); // 找到散列碼對應的那個桶 HashEntry< K ,V> first = tab[index]; HashEntry< K ,V> e = first; while(e != null&& (e.hash != hash || !key.equals(e.key))) e = e.next; V oldValue = null; if(e != null) { V v = e.value; if(value == null|| value.equals(v)) { // 找到要删除的節點 oldValue = v; ++modCount; // 所有處于待删除節點之後的節點原樣保留在連結清單中 // 所有處于待删除節點之前的節點被克隆到新連結清單中 HashEntry< K ,V> newFirst = e.next;// 待删節點的後繼結點 for(HashEntry< K ,V> p = first; p != e; p = p.next) newFirst = new HashEntry< K ,V>(p.key, p.hash, newFirst, p.value); // 把桶連結到新的頭結點 // 新的頭結點是原連結清單中，删除節點之前的那個節點 tab[index] = newFirst; count = c;      // 寫 count 變量 } } return oldValue; } finally{ unlock();               // 解鎖 } }

和 get 操作一樣，首先根據散列碼找到具體的連結清單；然後周遊這個連結清單找到要删除的節點；最後把待删除節點之後的所有節點原樣保留在新連結清單中，把待删除節點之前的每個節點克隆到新連結清單中。下面通過圖例來說明 remove 操作。

假設寫線程執行 remove 操作，要删除連結清單的 C 節點，另一個讀線程同時正在周遊這個連結清單。

圖 4. 執行删除之前的原連結清單：

圖 5. 執行删除之後的新連結清單

從上圖可以看出，删除節點 C 之後的所有節點原樣保留到新連結清單中；删除節點 C 之前的每個節點被克隆到新連結清單中，注意：它們在新連結清單中的連結順序被反轉了。

在執行 remove 操作時，原始連結清單并沒有被修改，也就是說：讀線程不會受同時執行 remove 操作的并發寫線程的幹擾。

綜合上面的分析我們可以看出，寫線程對某個連結清單的結構性修改不會影響其他的并發讀線程對這個連結清單的周遊通路。

用 Volatile 變量協調讀寫線程間的記憶體可見性

由于記憶體可見性問題，未正确同步的情況下，寫線程寫入的值可能并不為後續的讀線程可見。

下面以寫線程 M 和讀線程 N 來說明 ConcurrentHashMap 如何協調讀 / 寫線程間的記憶體可見性問題。

圖 6. 協調讀 - 寫線程間的記憶體可見性的示意圖：

假設線程 M 在寫入了 volatile 型變量 count 後，線程 N 讀取了這個 volatile 型變量 count。

根據 happens-before 關系法則中的程式次序法則，A appens-before 于 B，C happens-before D。

根據 Volatile 變量法則，B happens-before C。

根據傳遞性，連接配接上面三個 happens-before 關系得到：A appens-before 于 B； B appens-before C；C happens-before D。也就是說：寫線程 M 對連結清單做的結構性修改，在讀線程 N 讀取了同一個 volatile 變量後，對線程 N 也是可見的了。

雖然線程 N 是在未加鎖的情況下通路連結清單。Java 的記憶體模型可以保證：隻要之前對連結清單做結構性修改操作的寫線程 M 在退出寫方法前寫 volatile 型變量 count，讀線程 N 在讀取這個 volatile 型變量 count 後，就一定能“看到”這些修改。

ConcurrentHashMap 中，每個 Segment 都有一個變量 count。它用來統計 Segment 中的 HashEntry 的個數。這個變量被聲明為 volatile。

清單 8.Count 變量的聲明

1	transient volatile int count;

所有不加鎖讀方法，在進入讀方法時，首先都會去讀這個 count 變量。比如下面的 get 方法：

清單 9.get 操作

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

V get(Object key, int hash) { if(count != 0) {       // 首先讀 count 變量 HashEntry< K ,V> e = getFirst(hash); while(e != null) { if(e.hash == hash && key.equals(e.key)) { V v = e.value; if(v != null)            return v; // 如果讀到 value 域為 null，說明發生了重排序，加鎖後重新讀取 return readValueUnderLock(e); } e = e.next; } } return null; }

在 ConcurrentHashMap 中，所有執行寫操作的方法（put, remove, clear），在對連結清單做結構性修改之後，在退出寫方法前都會去寫這個 count 變量。所有未加鎖的讀操作（get, contains, containsKey）在讀方法中，都會首先去讀取這個 count 變量。

根據 Java 記憶體模型，對 同一個 volatile 變量的寫 / 讀操作可以確定：寫線程寫入的值，能夠被之後未加鎖的讀線程“看到”。

這個特性和前面介紹的 HashEntry 對象的不變性相結合，使得在 ConcurrentHashMap 中，讀線程在讀取散清單時，基本不需要加鎖就能成功獲得需要的值。這兩個特性相配合，不僅減少了請求同一個鎖的頻率（讀操作一般不需要加鎖就能夠成功獲得值），也減少了持有同一個鎖的時間（隻有讀到 value 域的值為 null 時 , 讀線程才需要加鎖後重讀）。

ConcurrentHashMap 實作高并發的總結

基于通常情形而優化

在實際的應用中，散清單一般的應用場景是：除了少數插入操作和删除操作外，絕大多數都是讀取操作，而且讀操作在大多數時候都是成功的。正是基于這個前提，ConcurrentHashMap 針對讀操作做了大量的優化。通過 HashEntry 對象的不變性和用 volatile 型變量協調線程間的記憶體可見性，使得 大多數時候，讀操作不需要加鎖就可以正确獲得值。這個特性使得 ConcurrentHashMap 的并發性能在分離鎖的基礎上又有了近一步的提高。

總結

ConcurrentHashMap 是一個并發散列映射表的實作，它允許完全并發的讀取，并且支援給定數量的并發更新。相比于 

HashTable 和

用同步包裝器包裝的 HashMap（Collections.synchronizedMap(new HashMap())），ConcurrentHashMap 擁有更高的并發性。在 

HashTable 和由同步包裝器包裝的 HashMap 中，使用一個全局的鎖來同步不同線程間的并發通路。同一時間點，隻能有一個線程持有鎖，也就是說在同一時間點，隻能有一個線程能通路容器。這雖然保證多線程間的安全并發通路，但同時也導緻對容器的通路變成

串行化

的了。

在使用鎖來協調多線程間并發通路的模式下，減小對鎖的競争可以有效提高并發性。有兩種方式可以減小對鎖的競争：

1. 減小請求 同一個鎖的 頻率。
2. 減少持有鎖的 時間。

ConcurrentHashMap 的高并發性主要來自于三個方面：

1. 用分離鎖實作多個線程間的更深層次的共享通路。
2. 用 HashEntery 對象的不變性來降低執行讀操作的線程在周遊連結清單期間對加鎖的需求。
3. 通過對同一個 Volatile 變量的寫 / 讀通路，協調不同線程間讀 / 寫操作的記憶體可見性。

使用分離鎖，減小了請求 同一個鎖的頻率。

通過 HashEntery 對象的不變性及對同一個 Volatile 變量的讀 / 寫來協調記憶體可見性，使得 讀操作大多數時候不需要加鎖就能成功擷取到需要的值。由于散列映射表在實際應用中大多數操作都是成功的 讀操作，是以 2 和 3 既可以減少請求同一個鎖的頻率，也可以有效減少持有鎖的時間。

通過減小請求同一個鎖的頻率和盡量減少持有鎖的時間 

，使得 ConcurrentHashMap 的并發性相對于 HashTable 和

用同步包裝器包裝的 HashMap

有了質的提高。