我們在之前的博文中了解到關(guān)于 HashMap 和 Hashtable 這兩種集合。其中 HashMap 是非線程安全的，當我們只有一個線程在使用 HashMap 的時候，自然不會有問題，但如果涉及到多個線程，并且有讀有寫的過程中，HashMap 就不能滿足我們的需要了(fail-fast)。在不考慮性能問題的時候，我們的解決方案有 Hashtable 或者Collections.synchronizedMap(hashMap)，這兩種方式基本都是對整個 hash 表結(jié)構(gòu)做鎖定操作的，這樣在鎖表的期間，別的線程就需要等待了，無疑性能不高。
所以我們在本文中學(xué)習(xí)一個 util.concurrent 包的重要成員，ConcurrentHashMap。
ConcurrentHashMap 的實現(xiàn)是依賴于 Java 內(nèi)存模型，所以我們在了解 ConcurrentHashMap 的前提是必須了解Java 內(nèi)存模型。但 Java 內(nèi)存模型并不是本文的重點，所以我假設(shè)讀者已經(jīng)對 Java 內(nèi)存模型有所了解。
ConcurrentHashMap 的結(jié)構(gòu)是比較復(fù)雜的，都深究去本質(zhì)，其實也就是數(shù)組和鏈表而已。我們由淺入深慢慢的分析其結(jié)構(gòu)。
先簡單分析一下，ConcurrentHashMap 的成員變量中，包含了一個 Segment 的數(shù)組（final Segment<K,V>[] segments;），而 Segment 是 ConcurrentHashMap 的內(nèi)部類，然后在 Segment 這個類中，包含了一個 HashEntry 的數(shù)組（transient volatile HashEntry<K,V>[] table;）。而 HashEntry 也是 ConcurrentHashMap 的內(nèi)部類。HashEntry 中，包含了 key 和 value 以及 next 指針（類似于 HashMap 中 Entry），所以 HashEntry 可以構(gòu)成一個鏈表。
所以通俗的講，ConcurrentHashMap 數(shù)據(jù)結(jié)構(gòu)為一個 Segment 數(shù)組，Segment 的數(shù)據(jù)結(jié)構(gòu)為 HashEntry 的數(shù)組，而 HashEntry 存的是我們的鍵值對，可以構(gòu)成鏈表。
首先，我們看一下 HashEntry 類。
HashEntry 用來封裝散列映射表中的鍵值對。在 HashEntry 類中，key，hash 和 next 域都被聲明為 final 型，value 域被聲明為 volatile 型。其類的定義為：
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
...
}HashEntry 的學(xué)習(xí)可以類比著 HashMap 中的 Entry。我們的存儲鍵值對的過程中，散列的時候如果發(fā)生“碰撞”，將采用“分離鏈表法”來處理碰撞：把碰撞的 HashEntry 對象鏈接成一個鏈表。
如下圖，我們在一個空桶中插入 A、B、C 兩個 HashEntry 對象后的結(jié)構(gòu)圖（其實應(yīng)該為鍵值對，在這進行了簡化以方便更容易理解）：
http://wiki.jikexueyuan.com/project/java-collection/images/concurrenthashmap1.jpg" alt="圖1" />
Segment 的類定義為static final class Segment<K,V> extends ReentrantLock implements Serializable。其繼承于 ReentrantLock 類，從而使得 Segment 對象可以充當鎖的角色。Segment 中包含HashEntry 的數(shù)組，其可以守護其包含的若干個桶（HashEntry的數(shù)組）。Segment 在某些意義上有點類似于 HashMap了，都是包含了一個數(shù)組，而數(shù)組中的元素可以是一個鏈表。
table:table 是由 HashEntry 對象組成的數(shù)組如果散列時發(fā)生碰撞，碰撞的 HashEntry 對象就以鏈表的形式鏈接成一個鏈表table數(shù)組的數(shù)組成員代表散列映射表的一個桶每個 table 守護整個 ConcurrentHashMap 包含桶總數(shù)的一部分如果并發(fā)級別為 16，table 則守護 ConcurrentHashMap 包含的桶總數(shù)的 1/16。
count 變量是計算器，表示每個 Segment 對象管理的 table 數(shù)組（若干個 HashEntry 的鏈表）包含的HashEntry 對象的個數(shù)。之所以在每個Segment對象中包含一個 count 計數(shù)器，而不在 ConcurrentHashMap 中使用全局的計數(shù)器，是為了避免出現(xiàn)“熱點域”而影響并發(fā)性。
/**
* Segments are specialized versions of hash tables. This
* subclasses from ReentrantLock opportunistically, just to
* simplify some locking and avoid separate construction.
*/
static final class Segment<K,V> extends ReentrantLock implements Serializable {
/**
* The per-segment table. Elements are accessed via
* entryAt/setEntryAt providing volatile semantics.
*/
transient volatile HashEntry<K,V>[] table;
/**
* The number of elements. Accessed only either within locks
* or among other volatile reads that maintain visibility.
*/
transient int count;
transient int modCount;
/**
* 裝載因子
*/
final float loadFactor;
}我們通過下圖來展示一下插入 ABC 三個節(jié)點后，Segment 的示意圖：
http://wiki.jikexueyuan.com/project/java-collection/images/concurrenthashmap2.jpg" alt="圖2" />
其實從我個人角度來說，Segment結(jié)構(gòu)是與HashMap很像的。
ConcurrentHashMap 的結(jié)構(gòu)中包含的 Segment 的數(shù)組，在默認的并發(fā)級別會創(chuàng)建包含 16 個 Segment 對象的數(shù)組。通過我們上面的知識，我們知道每個 Segment 又包含若干個散列表的桶，每個桶是由 HashEntry 鏈接起來的一個鏈表。如果 key 能夠均勻散列，每個 Segment 大約守護整個散列表桶總數(shù)的 1/16。
下面我們還有通過一個圖來演示一下 ConcurrentHashMap 的結(jié)構(gòu)：
http://wiki.jikexueyuan.com/project/java-collection/images/concurrenthashmap3.jpg" alt="圖3" />
在 ConcurrentHashMap 中，當執(zhí)行 put 方法的時候，會需要加鎖來完成。我們通過代碼來解釋一下具體過程： 當我們 new 一個 ConcurrentHashMap 對象，并且執(zhí)行put操作的時候，首先會執(zhí)行 ConcurrentHashMap 類中的 put 方法，該方法源碼為：
/**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
* <p> The value can be retrieved by calling the <tt>get</tt> method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>
* @throws NullPointerException if the specified key or value is null
*/
@SuppressWarnings("unchecked")
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}我們通過注釋可以了解到，ConcurrentHashMap 不允許空值。該方法首先有一個 Segment 的引用 s，然后會通過 hash() 方法對 key 進行計算，得到哈希值；繼而通過調(diào)用 Segment 的 put(K key, int hash, V value, boolean onlyIfAbsent)方法進行存儲操作。該方法源碼為：
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//加鎖，這里是鎖定的Segment而不是整個ConcurrentHashMap
HashEntry<K,V> node = tryLock() ? null :scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
//得到hash對應(yīng)的table中的索引index
int index = (tab.length - 1) & hash;
//找到hash對應(yīng)的是具體的哪個桶，也就是哪個HashEntry鏈表
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
//解鎖
unlock();
}
return oldValue;
}關(guān)于該方法的某些關(guān)鍵步驟，在源碼上加上了注釋。
需要注意的是：加鎖操作是針對的 hash 值對應(yīng)的某個 Segment，而不是整個 ConcurrentHashMap。因為 put 操作只是在這個 Segment 中完成，所以并不需要對整個 ConcurrentHashMap 加鎖。所以，此時，其他的線程也可以對另外的 Segment 進行 put 操作，因為雖然該 Segment 被鎖住了，但其他的 Segment 并沒有加鎖。同時，讀線程并不會因為本線程的加鎖而阻塞。
正是因為其內(nèi)部的結(jié)構(gòu)以及機制，所以 ConcurrentHashMap 在并發(fā)訪問的性能上要比Hashtable和同步包裝之后的HashMap的性能提高很多。在理想狀態(tài)下，ConcurrentHashMap 可以支持 16 個線程執(zhí)行并發(fā)寫操作（如果并發(fā)級別設(shè)置為 16），及任意數(shù)量線程的讀操作。
在實際的應(yīng)用中，散列表一般的應(yīng)用場景是：除了少數(shù)插入操作和刪除操作外，絕大多數(shù)都是讀取操作，而且讀操作在大多數(shù)時候都是成功的。正是基于這個前提，ConcurrentHashMap 針對讀操作做了大量的優(yōu)化。通過 HashEntry 對象的不變性和用 volatile 型變量協(xié)調(diào)線程間的內(nèi)存可見性，使得 大多數(shù)時候，讀操作不需要加鎖就可以正確獲得值。這個特性使得 ConcurrentHashMap 的并發(fā)性能在分離鎖的基礎(chǔ)上又有了近一步的提高。
ConcurrentHashMap 是一個并發(fā)散列映射表的實現(xiàn)，它允許完全并發(fā)的讀取，并且支持給定數(shù)量的并發(fā)更新。相比于 HashTable 和用同步包裝器包裝的 HashMap（Collections.synchronizedMap(new HashMap())），ConcurrentHashMap 擁有更高的并發(fā)性。在 HashTable 和由同步包裝器包裝的 HashMap 中，使用一個全局的鎖來同步不同線程間的并發(fā)訪問。同一時間點，只能有一個線程持有鎖，也就是說在同一時間點，只能有一個線程能訪問容器。這雖然保證多線程間的安全并發(fā)訪問，但同時也導(dǎo)致對容器的訪問變成串行化的了。
ConcurrentHashMap 的高并發(fā)性主要來自于三個方面：
使用分離鎖，減小了請求 同一個鎖的頻率。
通過 HashEntery 對象的不變性及對同一個 Volatile 變量的讀 / 寫來協(xié)調(diào)內(nèi)存可見性，使得 讀操作大多數(shù)時候不需要加鎖就能成功獲取到需要的值。由于散列映射表在實際應(yīng)用中大多數(shù)操作都是成功的 讀操作，所以 2 和 3 既可以減少請求同一個鎖的頻率，也可以有效減少持有鎖的時間。通過減小請求同一個鎖的頻率和盡量減少持有鎖的時間 ，使得 ConcurrentHashMap 的并發(fā)性相對于 HashTable 和用同步包裝器包裝的 HashMap有了質(zhì)的提高。
掃碼關(guān)注鍍金池微信號
手機訂課，優(yōu)惠多多