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