簡(jiǎn)介
ConcurrentHashMap 是 Java concurrent 包的重要成員留瞳。本文將結(jié)合 Java 內(nèi)存模型绰更，來(lái)分析 ConcurrentHashMap 的 JDK 源代碼茅特，探索 ConcurrentHashMap 高并發(fā)的具體實(shí)現(xiàn)機(jī)制。通過(guò)本文，讀者將了解到 ConcurrentHashMap 高并發(fā)性的具體實(shí)現(xiàn)機(jī)制燎猛。這對(duì)于我們?cè)趯?shí)際應(yīng)用中更加高效的使用它是很有幫助的。
由于 ConcurrentHashMap 的源代碼實(shí)現(xiàn)依賴于 Java 內(nèi)存模型照皆，所以閱讀本文需要讀者了解 Java 內(nèi)存模型重绷。同時(shí)，ConcurrentHashMap 的源代碼會(huì)涉及到散列算法和鏈表數(shù)據(jù)結(jié)構(gòu)膜毁，所以昭卓，讀者需要對(duì)散列算法和基于鏈表的數(shù)據(jù)結(jié)構(gòu)有所了解。
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ì)算性能上有了很大的提升峰伙。
重排序類(lèi)型包括：
- 編譯器生成指令的次序，可以不同于源代碼所暗示的“顯然”版本该默。
- 處理器可以亂序或者并行的執(zhí)行指令瞳氓。
- 緩存會(huì)改變寫(xiě)入提交到主內(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 寫(xiě)入一個(gè)變量值 V蔚鸥，隨后另一個(gè)線程 B 讀取變量 V 的值，在下列情況下捧弃，線程 B 讀取的值可能不是線程 A 寫(xiě)入的最新值：
- 執(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 域的寫(xiě)入操作 happens-before 于每個(gè)后續(xù)對(duì)同一 Volatile 的讀操作弹砚。
- 傳遞性：如果 A happens-before 于 B双仍，且 B happens-before C，則 A happens-before C桌吃。
ConcurrentHashMap 的結(jié)構(gòu)分析
為了更好的理解 ConcurrentHashMap 高并發(fā)的具體實(shí)現(xiàn)朱沃，讓我們先探索它的結(jié)構(gòu)模型。
ConcurrentHashMap 類(lèi)中包含兩個(gè)靜態(tài)內(nèi)部類(lè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 類(lèi)
HashEntry 用來(lái)封裝散列映射表中的鍵值對(duì)摆寄。在 HashEntry 類(lèi)中失暴，key坯门，hash 和 next 域都被聲明為 final 型，value 域被聲明為 volatile 型逗扒。
清單 1.HashEntry 類(lèi)的定義
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)圖：
注意：由于只能在表頭插入，所以鏈表中節(jié)點(diǎn)的順序和插入的順序相反刽酱。
Segment 類(lèi)
Segment 類(lèi)繼承于 ReentrantLock 類(lèi)喳逛，從而使得 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ā)性乔夯。
避免熱點(diǎn)域：
在 ConcurrentHashMap 中， 每一個(gè) Segment 對(duì)象都有一個(gè) count 對(duì)象來(lái)表示本 Segment 中包含的 HashEntry 對(duì)象的個(gè)數(shù)款侵。這樣當(dāng)需要更新計(jì)數(shù)器時(shí)末荐，不用鎖定整個(gè)ConcurrentHashMap。
清單 2.Segment 類(lèi)的定義
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)示意圖墩新。
ConcurrentHashMap 類(lèi)
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 類(lèi)的定義
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)示意圖驮樊。
用分離鎖實(shí)現(xiàn)多個(gè)線程間的并發(fā)寫(xiě)操作
在 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
V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 加鎖，這里是鎖定某個(gè) Segment 對(duì)象而非整個(gè) ConcurrentHashMap
lock();
try {
int c = count;
// 如果超過(guò)再散列的閾值
if (c++ > threshold)
// 執(zhí)行再散列崖飘，table 數(shù)組的長(zhǎng)度將擴(kuò)充一倍
rehash();
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;
// 如果鍵 / 值對(duì)以經(jīng)存在
if (e != null) {
oldValue = e.value;
if (!onlyIfAbsent)
// 設(shè)置 value 值
e.value = value;
} else {
// 鍵 / 值對(duì)不存在
oldValue = null;
// 要添加新節(jié)點(diǎn)到鏈表中朱浴，所以 modCont 要加 1
++modCount;
// 創(chuàng)建新節(jié)點(diǎn)，并添加到鏈表的頭部
tab[index] = new HashEntry<K, V>(key, hash, first, value);
// 寫(xiě) count 變量
count = c;
}
return oldValue;
} finally {
// 解鎖
unlock();
}
}
注意：這里的加鎖操作是針對(duì)（鍵的 hash 值對(duì)應(yīng)的）某個(gè)具體的 Segment赊琳，鎖定的是該 Segment 而不是整個(gè) ConcurrentHashMap。因?yàn)椴迦腈I / 值對(duì)操作只是在這個(gè) Segment 包含的某個(gè)桶中完成躏筏，不需要鎖定整個(gè)ConcurrentHashMap呈枉。此時(shí)埃碱，其他寫(xiě)線程對(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ū)懖僮髦ザ冢珻oncurrentHashMap 在并發(fā)訪問(wèn)性能上有了質(zhì)的提高似炎。在理想狀態(tài)下，ConcurrentHashMap 可以支持 16 個(gè)線程執(zhí)行并發(fā)寫(xiě)操作（如果并發(fā)級(jí)別設(shè)置為 16）悯姊，及任意數(shù)量線程的讀操作羡藐。
用 HashEntery 對(duì)象的不變性來(lái)降低讀操作對(duì)加鎖的需求
在代碼清單“HashEntry 類(lèi)的定義”中我們可以看到，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 類(lèi)的 value 域被聲明為 Volatile 型倒慧，Java 的內(nèi)存模型可以保證：某個(gè)寫(xiě)線程對(duì) value 域的寫(xiě)入馬上可以被后續(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)分析線程寫(xiě)入的兩種情形：對(duì)散列表做非結(jié)構(gòu)性修改的操作和對(duì)散列表做結(jié)構(gòu)性修改的操作爆捞。
非結(jié)構(gòu)性修改操作只是更改某個(gè) HashEntry 的 value 域的值煮甥。由于對(duì) Volatile 變量的寫(xiě)入操作將與隨后對(duì)這個(gè)變量的讀操作進(jìn)行同步成肘。當(dāng)一個(gè)寫(xiě)線程修改了某個(gè) HashEntry 的 value 域后砚偶，另一個(gè)讀線程讀這個(gè)值域蟹演，Java 內(nèi)存模型能夠保證讀線程讀取的一定是更新后的值酒请。所以羞反，寫(xiě)線程對(duì)鏈表的非結(jié)構(gòu)性修改能夠被后續(xù)不加鎖的讀線程“看到”昼窗。
對(duì) ConcurrentHashMap 做結(jié)構(gòu)性修改澄惊，實(shí)質(zhì)上是對(duì)某個(gè)桶指向的鏈表做結(jié)構(gòu)性修改掸驱。如果能夠確保：在讀線程遍歷一個(gè)鏈表期間，寫(xiě)線程對(duì)這個(gè)鏈表所做的結(jié)構(gòu)性修改不影響讀線程繼續(xù)正常遍歷這個(gè)鏈表鬼癣。那么讀 / 寫(xiě)線程之間就可以安全并發(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; // 寫(xiě) 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è)寫(xiě)線程執(zhí)行 remove 操作，要?jiǎng)h除鏈表的 C 節(jié)點(diǎn)芹橡，另一個(gè)讀線程同時(shí)正在遍歷這個(gè)鏈表林说。
從上圖可以看出，刪除節(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ā)寫(xiě)線程的干擾历涝。
綜合上面的分析我們可以看出荧库，寫(xiě)線程對(duì)某個(gè)鏈表的結(jié)構(gòu)性修改不會(huì)影響其他的并發(fā)讀線程對(duì)這個(gè)鏈表的遍歷訪問(wèn)。
用 Volatile 變量協(xié)調(diào)讀寫(xiě)線程間的內(nèi)存可見(jiàn)性
由于內(nèi)存可見(jiàn)性問(wèn)題般此，未正確同步的情況下，寫(xiě)線程寫(xiě)入的值可能并不為后續(xù)的讀線程可見(jiàn)邀桑。
下面以寫(xiě)線程 M 和讀線程 N 來(lái)說(shuō)明 ConcurrentHashMap 如何協(xié)調(diào)讀 / 寫(xiě)線程間的內(nèi)存可見(jiàn)性問(wèn)題。
假設(shè)線程 M 在寫(xiě)入了 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ō)：寫(xiě)線程 M 對(duì)鏈表做的結(jié)構(gòu)性修改柑蛇，在讀線程 N 讀取了同一個(gè) volatile 變量后，對(duì)線程 N 也是可見(jiàn)的了驱闷。
雖然線程 N 是在未加鎖的情況下訪問(wèn)鏈表扼菠。Java 的內(nèi)存模型可以保證：只要之前對(duì)鏈表做結(jié)構(gòu)性修改操作的寫(xiě)線程 M 在退出寫(xiě)方法前寫(xiě) 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í)行寫(xiě)操作的方法（put, remove, clear）翼闹，在對(duì)鏈表做結(jié)構(gòu)性修改之后荒叶，在退出寫(xiě)方法前都會(huì)去寫(xiě)這個(gè) count 變量戈毒。所有未加鎖的讀操作（get, contains, containsKey）在讀方法中，都會(huì)首先去讀取這個(gè) count 變量迹蛤。
根據(jù) Java 內(nèi)存模型痕囱，對(duì) 同一個(gè) volatile 變量的寫(xiě) / 讀操作可以確保：寫(xiě)線程寫(xiě)入的值巷查，能夠被之后未加鎖的讀線程“看到”。
這個(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(newHashMap()))阀蒂，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 變量的寫(xiě) / 讀訪問(wèn)，協(xié)調(diào)不同線程間讀 / 寫(xiě)操作的內(nèi)存可見(jiàn)性亿虽。
使用分離鎖菱涤，減小了請(qǐng)求 同一個(gè)鎖的頻率。
通過(guò) HashEntery 對(duì)象的不變性及對(duì)同一個(gè) Volatile 變量的讀 / 寫(xiě)來(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ì)的提高牛哺。
原文鏈接：
http://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/index.html
