|
原文地址：http://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/index.html 簡介 ConcurrentHashMap 是 util.concurrent 包的重要成員。本文將結(jié)合 Java 內(nèi)存模型，分析 JDK 源代碼，探索 ConcurrentHashMap 高并發(fā)的具體實現(xiàn)機制。 由于 ConcurrentHashMap 的源代碼實現(xiàn)依賴于 Java 內(nèi)存模型，所以閱讀本文需要讀者了解 Java 內(nèi)存模型。同時，ConcurrentHashMap 的源代碼會涉及到散列算法和鏈表數(shù)據(jù)結(jié)構(gòu)，所以，讀者需要對散列算法和基于鏈表的數(shù)據(jù)結(jié)構(gòu)有所了解。
回頁首 Java 內(nèi)存模型 由于 ConcurrentHashMap 是建立在 Java 內(nèi)存模型基礎(chǔ)上的，為了更好的理解 ConcurrentHashMap，讓我們首先來了解一下 Java 的內(nèi)存模型。 Java 語言的內(nèi)存模型由一些規(guī)則組成，這些規(guī)則確定線程對內(nèi)存的訪問如何排序以及何時可以確保它們對線程是可見的。下面我們將分別介紹 Java 內(nèi)存模型的重排序，內(nèi)存可見性和 happens-before 關(guān)系。 重排序 內(nèi)存模型描述了程序的可能行為。具體的編譯器實現(xiàn)可以產(chǎn)生任意它喜歡的代碼 -- 只要所有執(zhí)行這些代碼產(chǎn)生的結(jié)果，能夠和內(nèi)存模型預(yù)測的結(jié)果保持一致。這為編譯器實現(xiàn)者提供了很大的自由，包括操作的重排序。 編譯器生成指令的次序，可以不同于源代碼所暗示的“顯然”版本。重排序后的指令，對于優(yōu)化執(zhí)行以及成熟的全局寄存器分配算法的使用，都是大有脾益的，它使得程序在計算性能上有了很大的提升。 重排序類型包括：
編譯器生成指令的次序，可以不同于源代碼所暗示的“顯然”版本。
處理器可以亂序或者并行的執(zhí)行指令。
緩存會改變寫入提交到主內(nèi)存的變量的次序。
內(nèi)存可見性 由于現(xiàn)代可共享內(nèi)存的多處理器架構(gòu)可能導(dǎo)致一個線程無法馬上（甚至永遠）看到另一個線程操作產(chǎn)生的結(jié)果。所以 Java 內(nèi)存模型規(guī)定了 JVM 的一種最小保證：什么時候?qū)懭胍粋€變量對其他線程可見。 在現(xiàn)代可共享內(nèi)存的多處理器體系結(jié)構(gòu)中每個處理器都有自己的緩存，并周期性的與主內(nèi)存協(xié)調(diào)一致。假設(shè)線程 A 寫入一個變量值 V，隨后另一個線程 B 讀取變量 V 的值，在下列情況下，線程 B 讀取的值可能不是線程 A 寫入的最新值：
執(zhí)行線程 A 的處理器把變量 V 緩存到寄存器中。
執(zhí)行線程 A 的處理器把變量 V 緩存到自己的緩存中，但還沒有同步刷新到主內(nèi)存中去。
執(zhí)行線程 B 的處理器的緩存中有變量 V 的舊值。
Happens-before 關(guān)系 happens-before 關(guān)系保證：如果線程 A 與線程 B 滿足 happens-before 關(guān)系，則線程 A 執(zhí)行動作的結(jié)果對于線程 B 是可見的。如果兩個操作未按 happens-before 排序，JVM 將可以對他們?nèi)我庵嘏判颉?/p> 下面介紹幾個與理解 ConcurrentHashMap 有關(guān)的 happens-before 關(guān)系法則：
程序次序法則：如果在程序中，所有動作 A 出現(xiàn)在動作 B 之前，則線程中的每動作 A 都 happens-before 于該線程中的每一個動作 B。
監(jiān)視器鎖法則：對一個監(jiān)視器的解鎖 happens-before 于每個后續(xù)對同一監(jiān)視器的加鎖。
Volatile 變量法則：對 Volatile 域的寫入操作 happens-before 于每個后續(xù)對同一 Volatile 的讀操作。
傳遞性：如果 A happens-before 于 B，且 B happens-before C，則 A happens-before C。
回頁首 ConcurrentHashMap 的結(jié)構(gòu)分析 為了更好的理解 ConcurrentHashMap 高并發(fā)的具體實現(xiàn)，讓我們先探索它的結(jié)構(gòu)模型。 ConcurrentHashMap 類中包含兩個靜態(tài)內(nèi)部類 HashEntry 和 Segment。HashEntry 用來封裝映射表的鍵 / 值對；Segment 用來充當(dāng)鎖的角色，每個 Segment 對象守護整個散列映射表的若干個桶。每個桶是由若干個 HashEntry 對象鏈接起來的鏈表。一個 ConcurrentHashMap 實例中包含由若干個 Segment 對象組成的數(shù)組。 HashEntry 類 HashEntry 用來封裝散列映射表中的鍵值對。在 HashEntry 類中，key，hash 和 next 域都被聲明為 final 型，value 域被聲明為 volatile 型。
清單 1.HashEntry 類的定義
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 中，在散列時如果產(chǎn)生“碰撞”，將采用“分離鏈接法”來處理“碰撞”：把“碰撞”的 HashEntry 對象鏈接成一個鏈表。由于 HashEntry 的 next 域為 final 型，所以新節(jié)點只能在鏈表的表頭處插入。 下圖是在一個空桶中依次插入 A，B，C 三個 HashEntry 對象后的結(jié)構(gòu)圖：
圖 1. 插入三個節(jié)點后桶的結(jié)構(gòu)示意圖：
注意：由于只能在表頭插入，所以鏈表中節(jié)點的順序和插入的順序相反。
避免熱點域 在
ConcurrentHashMap
中，
每一個 Segment 對象都有一個 count 對象來表示本 Segment 中包含的 HashEntry 對象的個數(shù)。這樣當(dāng)需要更新計數(shù)器時，不用鎖定整個
ConcurrentHashMap
。
Segment 類 Segment 類繼承于 ReentrantLock 類，從而使得 Segment 對象能充當(dāng)鎖的角色。每個 Segment 對象用來守護其（成員對象 table 中）包含的若干個桶。 table 是一個由 HashEntry 對象組成的數(shù)組。table 數(shù)組的每一個數(shù)組成員就是散列映射表的一個桶。 count 變量是一個計數(shù)器，它表示每個 Segment 對象管理的 table 數(shù)組（若干個 HashEntry 組成的鏈表）包含的 HashEntry 對象的個數(shù)。每一個 Segment 對象都有一個 count 對象來表示本 Segment 中包含的 HashEntry 對象的總數(shù)。注意，之所以在每個 Segment 對象中包含一個計數(shù)器，而不是在
ConcurrentHashMap 中使用全局的計數(shù)器，是為了避免出現(xiàn)“熱點域”而影響 ConcurrentHashMap 的并發(fā)性。
清單 2.Segment 類的定義
static final class Segment<K,V> extends ReentrantLock implements Serializable { /** * 在本 segment 范圍內(nèi)，包含的 HashEntry 元素的個數(shù) * 該變量被聲明為 volatile 型 */ transient volatile int count; /** * table 被更新的次數(shù) */ transient int modCount; /** * 當(dāng) table 中包含的 HashEntry 元素的個數(shù)超過本變量值時，觸發(fā) table 的再散列 */ transient int threshold; /** * table 是由 HashEntry 對象組成的數(shù)組 * 如果散列時發(fā)生碰撞，碰撞的 HashEntry 對象就以鏈表的形式鏈接成一個鏈表 * table 數(shù)組的數(shù)組成員代表散列映射表的一個桶 * 每個 table 守護整個 ConcurrentHashMap 包含桶總數(shù)的一部分 * 如果并發(fā)級別為 16，table 則守護 ConcurrentHashMap 包含的桶總數(shù)的 1/16 */ transient volatile HashEntry<K,V>[] table; /** * 裝載因子 */ final float loadFactor; Segment(int initialCapacity, float lf) { loadFactor = lf; setTable(HashEntry.<K,V>newArray(initialCapacity)); } /** * 設(shè)置 table 引用到這個新生成的 HashEntry 數(shù)組 * 只能在持有鎖或構(gòu)造函數(shù)中調(diào)用本方法 */ void setTable(HashEntry<K,V>[] newTable) { // 計算臨界閥值為新數(shù)組的長度與裝載因子的乘積 threshold = (int)(newTable.length * loadFactor); table = newTable; } /** * 根據(jù) key 的散列值，找到 table 中對應(yīng)的那個桶（table 數(shù)組的某個數(shù)組成員） */ HashEntry<K,V> getFirst(int hash) { HashEntry<K,V>[] tab = table; // 把散列值與 table 數(shù)組長度減 1 的值相“與”， // 得到散列值對應(yīng)的 table 數(shù)組的下標(biāo) // 然后返回 table 數(shù)組中此下標(biāo)對應(yīng)的 HashEntry 元素 return tab[hash & (tab.length - 1)]; } } |
下圖是依次插入 ABC 三個 HashEntry 節(jié)點后，Segment 的結(jié)構(gòu)示意圖。
圖 2. 插入三個節(jié)點后 Segment 的結(jié)構(gòu)示意圖：
ConcurrentHashMap 類 ConcurrentHashMap 在默認并發(fā)級別會創(chuàng)建包含 16 個 Segment 對象的數(shù)組。每個 Segment 的成員對象 table 包含若干個散列表的桶。每個桶是由 HashEntry 鏈接起來的一個鏈表。如果鍵能均勻散列，每個 Segment 大約守護整個散列表中桶總數(shù)的 1/16。
清單 3.ConcurrentHashMap 類的定義
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable { /** * 散列映射表的默認初始容量為 16，即初始默認為 16 個桶 * 在構(gòu)造函數(shù)中沒有指定這個參數(shù)時，使用本參數(shù) */ static final int DEFAULT_INITIAL_CAPACITY= 16; /** * 散列映射表的默認裝載因子為 0.75，該值是 table 中包含的 HashEntry 元素的個數(shù)與 * table 數(shù)組長度的比值 * 當(dāng) table 中包含的 HashEntry 元素的個數(shù)超過了 table 數(shù)組的長度與裝載因子的乘積時， * 將觸發(fā) 再散列 * 在構(gòu)造函數(shù)中沒有指定這個參數(shù)時，使用本參數(shù) */ static final float DEFAULT_LOAD_FACTOR= 0.75f; /** * 散列表的默認并發(fā)級別為 16。該值表示當(dāng)前更新線程的估計數(shù) * 在構(gòu)造函數(shù)中沒有指定這個參數(shù)時，使用本參數(shù) */ static final int DEFAULT_CONCURRENCY_LEVEL= 16; /** * segments 的掩碼值 * key 的散列碼的高位用來選擇具體的 segment */ final int segmentMask; /** * 偏移量 */ final int segmentShift; /** * 由 Segment 對象組成的數(shù)組 */ final Segment<K,V>[] segments; /** * 創(chuàng)建一個帶有指定初始容量、加載因子和并發(fā)級別的新的空映射。 */ public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if(!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); if(concurrencyLevel > MAX_SEGMENTS) concurrencyLevel = MAX_SEGMENTS; // 尋找最佳匹配參數(shù)（不小于給定參數(shù)的最接近的 2 次冪） int sshift = 0; int ssize = 1; while(ssize < concurrencyLevel) { ++sshift; ssize <<= 1; } segmentShift = 32 - sshift; // 偏移量值 segmentMask = ssize - 1; // 掩碼值 this.segments = Segment.newArray(ssize); // 創(chuàng)建數(shù)組 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; int c = initialCapacity / ssize; if(c * ssize < initialCapacity) ++c; int cap = 1; while(cap < c) cap <<= 1; // 依次遍歷每個數(shù)組元素 for(int i = 0; i < this.segments.length; ++i) // 初始化每個數(shù)組元素引用的 Segment 對象 this.segments[i] = new Segment<K,V>(cap, loadFactor); } /** * 創(chuàng)建一個帶有默認初始容量 (16)、默認加載因子 (0.75) 和 默認并發(fā)級別 (16) * 的空散列映射表。 */ public ConcurrentHashMap() { // 使用三個默認參數(shù)，調(diào)用上面重載的構(gòu)造函數(shù)來創(chuàng)建空散列映射表 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL); } |
} 下面是 ConcurrentHashMap 的結(jié)構(gòu)示意圖。
圖 3.ConcurrentHashMap 的結(jié)構(gòu)示意圖：
用分離鎖實現(xiàn)多個線程間的并發(fā)寫操作 在 ConcurrentHashMap 中，線程對映射表做讀操作時，一般情況下不需要加鎖就可以完成，對容器做結(jié)構(gòu)性修改的操作才需要加鎖。下面以 put 操作為例說明對 ConcurrentHashMap 做結(jié)構(gòu)性修改的過程。 首先，根據(jù) key 計算出對應(yīng)的 hash 值：
清單 4.Put 方法的實現(xiàn)
public V put(K key, V value) { if (value == null) //ConcurrentHashMap 中不允許用 null 作為映射值 throw new NullPointerException(); int hash = hash(key.hashCode()); // 計算鍵對應(yīng)的散列碼 // 根據(jù)散列碼找到對應(yīng)的 Segment return segmentFor(hash).put(key, hash, value, false); } |
然后，根據(jù) hash 值找到對應(yīng)的
Segment 對象：
清單 5.根據(jù) hash 值找到對應(yīng)的 Segment
/** * 使用 key 的散列碼來得到 segments 數(shù)組中對應(yīng)的 Segment */ final Segment<K,V> segmentFor(int hash) { // 將散列值右移 segmentShift 個位，并在高位填充 0 // 然后把得到的值與 segmentMask 相“與” // 從而得到 hash 值對應(yīng)的 segments 數(shù)組的下標(biāo)值 // 最后根據(jù)下標(biāo)值返回散列碼對應(yīng)的 Segment 對象 return segments[(hash >>> segmentShift) & segmentMask]; } |
最后，在這個 Segment 中執(zhí)行具體的 put 操作：
清單 6.在 Segment 中執(zhí)行具體的 put 操作
V put(K key, int hash, V value, boolean onlyIfAbsent) { lock(); // 加鎖，這里是鎖定某個 Segment 對象而非整個 ConcurrentHashMap try { int c = count; if (c++ > threshold) // 如果超過再散列的閾值 rehash(); // 執(zhí)行再散列，table 數(shù)組的長度將擴充一倍 HashEntry<K,V>[] tab = table; // 把散列碼值與 table 數(shù)組的長度減 1 的值相“與” // 得到該散列碼對應(yīng)的 table 數(shù)組的下標(biāo)值 int index = hash & (tab.length - 1); // 找到散列碼對應(yīng)的具體的那個桶 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) { // 如果鍵 / 值對以經(jīng)存在 oldValue = e.value; if (!onlyIfAbsent) e.value = value; // 設(shè)置 value 值 } else { // 鍵 / 值對不存在 oldValue = null; ++modCount; // 要添加新節(jié)點到鏈表中，所以 modCont 要加 1 // 創(chuàng)建新節(jié)點，并添加到鏈表的頭部 tab[index] = new HashEntry<K,V>(key, hash, first, value); count = c; // 寫 count 變量 } return oldValue; } finally { unlock(); // 解鎖 } } |
注意：這里的加鎖操作是針對（鍵的 hash 值對應(yīng)的）某個具體的 Segment，鎖定的是該 Segment 而不是整個 ConcurrentHashMap
。因為插入鍵 / 值對操作只是在這個 Segment 包含的某個桶中完成，不需要鎖定整個
ConcurrentHashMap。
此時，其他寫線程對另外 15 個
Segment 的加鎖并不會因為當(dāng)前線程對這個 Segment 的加鎖而阻塞。同時，所有讀線程幾乎不會因本線程的加鎖而阻塞（除非讀線程剛好讀到這個 Segment 中某個
HashEntry 的 value 域的值為 null，此時需要加鎖后重新讀取該值
）。 相比較于
HashTable 和由同步包裝器包裝的 HashMap
每次只能有一個線程執(zhí)行讀或?qū)懖僮鳎?br>ConcurrentHashMap 在并發(fā)訪問性能上有了質(zhì)的提高。在理想狀態(tài)下，ConcurrentHashMap 可以支持 16 個線程執(zhí)行并發(fā)寫操作（如果并發(fā)級別設(shè)置為 16），及任意數(shù)量線程的讀操作。
用 HashEntery 對象的不變性來降低讀操作對加鎖的需求 在代碼清單“HashEntry 類的定義”中我們可以看到，HashEntry 中的 key，hash，next 都聲明為 final 型。這意味著，不能把節(jié)點添加到鏈接的中間和尾部，也不能在鏈接的中間和尾部刪除節(jié)點。這個特性可以保證：在訪問某個節(jié)點時，這個節(jié)點之后的鏈接不會被改變。這個特性可以大大降低處理鏈表時的復(fù)雜性。 同時，HashEntry 類的 value 域被聲明為 Volatile 型，Java 的內(nèi)存模型可以保證：某個寫線程對 value 域的寫入馬上可以被后續(xù)的某個讀線程“看”到。在 ConcurrentHashMap 中，不允許用 unll 作為鍵和值，當(dāng)讀線程讀到某個 HashEntry 的 value 域的值為 null 時，便知道產(chǎn)生了沖突——發(fā)生了重排序現(xiàn)象，需要加鎖后重新讀入這個 value 值。這些特性互相配合，使得讀線程即使在不加鎖狀態(tài)下，也能正確訪問 ConcurrentHashMap。 下面我們分別來分析線程寫入的兩種情形：對散列表做非結(jié)構(gòu)性修改的操作和對散列表做結(jié)構(gòu)性修改的操作。 非結(jié)構(gòu)性修改操作只是更改某個 HashEntry 的 value 域的值。由于對 Volatile 變量的寫入操作將與隨后對這個變量的讀操作進行同步。當(dāng)一個寫線程修改了某個 HashEntry 的 value 域后，另一個讀線程讀這個值域，Java 內(nèi)存模型能夠保證讀線程讀取的一定是更新后的值。所以，寫線程對鏈表的非結(jié)構(gòu)性修改能夠被后續(xù)不加鎖的讀線程“看到”。 對 ConcurrentHashMap 做結(jié)構(gòu)性修改，實質(zhì)上是對某個桶指向的鏈表做結(jié)構(gòu)性修改。如果能夠確保：在讀線程遍歷一個鏈表期間，寫線程對這個鏈表所做的結(jié)構(gòu)性修改不影響讀線程繼續(xù)正常遍歷這個鏈表。那么讀 / 寫線程之間就可以安全并發(fā)訪問這個 ConcurrentHashMap。 結(jié)構(gòu)性修改操作包括 put，remove，clear。下面我們分別分析這三個操作。 clear 操作只是把 ConcurrentHashMap 中所有的桶“置空”，每個桶之前引用的鏈表依然存在，只是桶不再引用到這些鏈表（所有鏈表的結(jié)構(gòu)并沒有被修改）。正在遍歷某個鏈表的讀線程依然可以正常執(zhí)行對該鏈表的遍歷。 從上面的代碼清單“在 Segment 中執(zhí)行具體的 put 操作”中，我們可以看出：put 操作如果需要插入一個新節(jié)點到鏈表中時 , 會在鏈表頭部插入這個新節(jié)點。此時，鏈表中的原有節(jié)點的鏈接并沒有被修改。也就是說：插入新健 / 值對到鏈表中的操作不會影響讀線程正常遍歷這個鏈表。 下面來分析 remove 操作，先讓我們來看看 remove 操作的源代碼實現(xiàn)。
清單 7.remove 操作
V remove(Object key, int hash, Object value) { lock(); // 加鎖 try{ int c = count - 1; HashEntry<K,V>[] tab = table; // 根據(jù)散列碼找到 table 的下標(biāo)值 int index = hash & (tab.length - 1); // 找到散列碼對應(yīng)的那個桶 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)) { // 找到要刪除的節(jié)點 oldValue = v; ++modCount; // 所有處于待刪除節(jié)點之后的節(jié)點原樣保留在鏈表中 // 所有處于待刪除節(jié)點之前的節(jié)點被克隆到新鏈表中 HashEntry<K,V> newFirst = e.next;// 待刪節(jié)點的后繼結(jié)點 for(HashEntry<K,V> p = first; p != e; p = p.next) newFirst = new HashEntry<K,V>(p.key, p.hash, newFirst, p.value); // 把桶鏈接到新的頭結(jié)點 // 新的頭結(jié)點是原鏈表中，刪除節(jié)點之前的那個節(jié)點 tab[index] = newFirst; count = c; // 寫 count 變量 } } return oldValue; } finally{ unlock(); // 解鎖 } } |
和 get 操作一樣，首先根據(jù)散列碼找到具體的鏈表；然后遍歷這個鏈表找到要刪除的節(jié)點；最后把待刪除節(jié)點之后的所有節(jié)點原樣保留在新鏈表中，把待刪除節(jié)點之前的每個節(jié)點克隆到新鏈表中。下面通過圖例來說明 remove 操作。
假設(shè)寫線程執(zhí)行 remove 操作，要刪除鏈表的 C 節(jié)點，另一個讀線程同時正在遍歷這個鏈表。
圖 4. 執(zhí)行刪除之前的原鏈表：
圖 5. 執(zhí)行刪除之后的新鏈表
從上圖可以看出，刪除節(jié)點 C 之后的所有節(jié)點原樣保留到新鏈表中；刪除節(jié)點 C 之前的每個節(jié)點被克隆到新鏈表中，注意：它們在新鏈表中的鏈接順序被反轉(zhuǎn)了。 在執(zhí)行 remove 操作時，原始鏈表并沒有被修改，也就是說：讀線程不會受同時執(zhí)行 remove 操作的并發(fā)寫線程的干擾。 綜合上面的分析我們可以看出，寫線程對某個鏈表的結(jié)構(gòu)性修改不會影響其他的并發(fā)讀線程對這個鏈表的遍歷訪問。
用 Volatile 變量協(xié)調(diào)讀寫線程間的內(nèi)存可見性 由于內(nèi)存可見性問題，未正確同步的情況下，寫線程寫入的值可能并不為后續(xù)的讀線程可見。 下面以寫線程 M 和讀線程 N 來說明 ConcurrentHashMap 如何協(xié)調(diào)讀 / 寫線程間的內(nèi)存可見性問題。
圖 6. 協(xié)調(diào)讀 - 寫線程間的內(nèi)存可見性的示意圖：
假設(shè)線程 M 在寫入了 volatile 型變量 count 后，線程 N 讀取了這個 volatile 型變量 count。 根據(jù) happens-before 關(guān)系法則中的程序次序法則，A appens-before 于 B，C happens-before D。 根據(jù) Volatile 變量法則，B happens-before C。 根據(jù)傳遞性，連接上面三個 happens-before 關(guān)系得到：A appens-before 于 B； B appens-before C；C happens-before D。也就是說：寫線程 M 對鏈表做的結(jié)構(gòu)性修改，在讀線程 N 讀取了同一個 volatile 變量后，對線程 N 也是可見的了。 雖然線程 N 是在未加鎖的情況下訪問鏈表。Java 的內(nèi)存模型可以保證：只要之前對鏈表做結(jié)構(gòu)性修改操作的寫線程 M 在退出寫方法前寫 volatile 型變量 count，讀線程 N 在讀取這個 volatile 型變量 count 后，就一定能“看到”這些修改。 ConcurrentHashMap 中，每個 Segment 都有一個變量 count。它用來統(tǒng)計 Segment 中的 HashEntry 的個數(shù)。這個變量被聲明為 volatile。
清單 8.Count 變量的聲明
transient volatile int count; |
所有不加鎖讀方法，在進入讀方法時，首先都會去讀這個 count 變量。比如下面的 get 方法：
清單 9.get 操作
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，說明發(fā)生了重排序，加鎖后重新讀取 return readValueUnderLock(e); } e = e.next; } } return null; } |
在 ConcurrentHashMap 中，所有執(zhí)行寫操作的方法（put, remove, clear），在對鏈表做結(jié)構(gòu)性修改之后，在退出寫方法前都會去寫這個 count 變量。所有未加鎖的讀操作（get, contains, containsKey）在讀方法中，都會首先去讀取這個 count 變量。 根據(jù) Java 內(nèi)存模型，對 同一個 volatile 變量的寫 / 讀操作可以確保：寫線程寫入的值，能夠被之后未加鎖的讀線程“看到”。 這個特性和前面介紹的 HashEntry 對象的不變性相結(jié)合，使得在 ConcurrentHashMap 中，讀線程在讀取散列表時，基本不需要加鎖就能成功獲得需要的值。這兩個特性相配合，不僅減少了請求同一個鎖的頻率（讀操作一般不需要加鎖就能夠成功獲得值），也減少了持有同一個鎖的時間（只有讀到 value 域的值為 null 時 , 讀線程才需要加鎖后重讀）。
ConcurrentHashMap 實現(xiàn)高并發(fā)的總結(jié) 基于通常情形而優(yōu)化 在實際的應(yīng)用中，散列表一般的應(yīng)用場景是：除了少數(shù)插入操作和刪除操作外，絕大多數(shù)都是讀取操作，而且讀操作在大多數(shù)時候都是成功的。正是基于這個前提，ConcurrentHashMap 針對讀操作做了大量的優(yōu)化。通過 HashEntry 對象的不變性和用 volatile 型變量協(xié)調(diào)線程間的內(nèi)存可見性，使得 大多數(shù)時候，讀操作不需要加鎖就可以正確獲得值。這個特性使得 ConcurrentHashMap 的并發(fā)性能在分離鎖的基礎(chǔ)上又有了近一步的提高。 總結(jié) ConcurrentHashMap 是一個并發(fā)散列映射表的實現(xiàn)，它允許完全并發(fā)的讀取，并且支持給定數(shù)量的并發(fā)更新。相比于
HashTable 和
用同步包裝器包裝的 HashMap（Collections.synchronizedMap(new HashMap())），ConcurrentHashMap 擁有更高的并發(fā)性。在
HashTable 和由同步包裝器包裝的 HashMap 中，使用一個全局的鎖來同步不同線程間的并發(fā)訪問。同一時間點，只能有一個線程持有鎖，也就是說在同一時間點，只能有一個線程能訪問容器。這雖然保證多線程間的安全并發(fā)訪問，但同時也導(dǎo)致對容器的訪問變成
串行化
的了。
在使用鎖來協(xié)調(diào)多線程間并發(fā)訪問的模式下，減小對鎖的競爭可以有效提高并發(fā)性。有兩種方式可以減小對鎖的競爭：
減小請求 同一個鎖的 頻率。
減少持有鎖的 時間。
ConcurrentHashMap 的高并發(fā)性主要來自于三個方面：
用分離鎖實現(xiàn)多個線程間的更深層次的共享訪問。
用 HashEntery 對象的不變性來降低執(zhí)行讀操作的線程在遍歷鏈表期間對加鎖的需求。
通過對同一個 Volatile 變量的寫 / 讀訪問，協(xié)調(diào)不同線程間讀 / 寫操作的內(nèi)存可見性。
使用分離鎖，減小了請求 同一個鎖的頻率。 通過 HashEntery 對象的不變性及對同一個 Volatile 變量的讀 / 寫來協(xié)調(diào)內(nèi)存可見性，使得 讀操作大多數(shù)時候不需要加鎖就能成功獲取到需要的值。由于散列映射表在實際應(yīng)用中大多數(shù)操作都是成功的 讀操作，所以 2 和 3 既可以減少請求同一個鎖的頻率，也可以有效減少持有鎖的時間。 通過減小請求同一個鎖的頻率和盡量減少持有鎖的時間
，使得 ConcurrentHashMap 的并發(fā)性相對于 HashTable 和
用同步包裝器包裝的 HashMap
有了質(zhì)的提高。
|
