[TOC]
一、頂部注釋分析
1.1 數(shù)據(jù)結(jié)構(gòu)
1.1.1 JDK1.7實(shí)現(xiàn)
- 在 JDK1.7中，ConcurrentHashMap 通過“鎖分段”來實(shí)現(xiàn)線程安全
- 通過將哈希表分成許多片段 (segments) ，每一個(gè)片段 (table) 都類似于 HashMap，有一個(gè)HashEntry 數(shù)組，數(shù)組的每項(xiàng)又是 HashEntry 組成的鏈表
- Segment 繼承了ReentrantLock，所以 Segment 本質(zhì)上是一個(gè)可重入的互斥鎖
- 在訪問某個(gè)鍵值對(duì)時(shí)，需要先獲取該鍵值對(duì)所在的 segment 上的鎖，獲取鎖后，其他線程就不能訪問此segment了，但可以訪問其他的segment，從而避免了把整個(gè)哈希表都鎖住
image
1.1.2 JDK1.8實(shí)現(xiàn)
- JDK1.8中放棄了鎖分段的方式，結(jié)構(gòu)和 HashMap 相同，也是數(shù)組+鏈表+紅黑樹的方式
- 但是通過 CAS 和部分加鎖的方式來實(shí)現(xiàn)線程安全
image
1.2 從注釋中得到的結(jié)論
-
A hash table supporting full concurrency of retrievals and high expected concurrency for updates：ConcurrentHashMap 是一個(gè)支持高并發(fā)檢索和更新的哈希表 - ConcurrentHashMap 是線程安全的，但不是靠阻塞和封鎖整個(gè)哈希表來實(shí)現(xiàn)的
- get 操作不是阻塞的，因此可以和一些更新操作并行，如 put 和 remove
- 一些和統(tǒng)計(jì)相關(guān)的方法，如
size、isEmpty、containsValue最好在單線程環(huán)境下使用，在多線程環(huán)境下只能反應(yīng)一個(gè)暫時(shí)的狀態(tài)，可用于估計(jì)或監(jiān)視，但可能無法返回準(zhǔn)確值，除非此時(shí)沒有發(fā)生并發(fā)的修改 - 當(dāng)散列碰撞過多時(shí)，ConcurrentHashMap 會(huì)動(dòng)態(tài)增長。但是擴(kuò)容非常消耗資源，因此最好提前估計(jì)好容量
- ConcurrentHashMap 不允許 key 或 value 為 null
二、源碼分析
2.1 定義
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable
- ConcurrentHashMap<K,V>：HashMap 是以 key-value 形式存儲(chǔ)數(shù)據(jù)的
- extends AbstractMap<K,V>：繼承自 AbstractMap，大大減少了實(shí)現(xiàn) Map 接口時(shí)需要的工作量
- implements ConcurrentMap<K,V>：實(shí)現(xiàn)了 ConcurrentMap 接口，一個(gè)提供線程安全性和原子性保證的 Map
- implements Serializable：可以序列化
2.2 字段
// 哈希表數(shù)組，用volatile修飾，大小總是為2的整數(shù)次冪
transient volatile Node<K,V>[] table;
// 基礎(chǔ)計(jì)數(shù)器，通過CAS來更新
private transient volatile long baseCount;
/**
* 用于控制初始化和擴(kuò)容
* 當(dāng)為負(fù)數(shù)時(shí)，表示正在進(jìn)行初始化或擴(kuò)容操作：
* -1 表示正在初始化
* -N 表示有N-1個(gè)線程正在進(jìn)行擴(kuò)容操作
*
* 默認(rèn)值為0
* 當(dāng)初始化之后，保存下一次的擴(kuò)容值
*/
private transient volatile int sizeCtl;
// 用于計(jì)算size
private transient volatile CounterCell[] counterCells
2.3 Node靜態(tài)內(nèi)部類
- 與 HashMap 中的 Node 相似，但有如下區(qū)別：
- 對(duì) value 和 next 屬性設(shè)置了 volatile 同步鎖；
- 不允許調(diào)用 setValue 方法直接改變 Node 的 value，否則會(huì)拋出異常
- 增加了 find 方法用于輔助 get 方法
static class Node<K,V> implements Map.Entry<K,V>
{
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next)
{
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
public final V setValue(V value)
{
throw new UnsupportedOperationException();
}
Node<K,V> find(int h, Object k)
{
Node<K,V> e = this;
if (k != null) {
do {
K ek;
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
} while ((e = e.next) != null);
}
return null;
}
}
2.4 構(gòu)造方法
-
public ConcurrentHashMap()：構(gòu)建一個(gè)空ConcurrentHashMap，默認(rèn)容量為16 -
public ConcurrentHashMap(int initialCapacity)：構(gòu)建一個(gè)空ConcurrentHashMap并根據(jù)參數(shù)設(shè)置下次擴(kuò)容值 -
public ConcurrentHashMap(Map<? extends K, ? extends V> m)：根據(jù)給定的 Map 進(jìn)行構(gòu)建 -
public ConcurrentHashMap(int initialCapacity, float loadFactor)：根據(jù)給定的參數(shù)設(shè)置下次擴(kuò)容值和加載因子，默認(rèn)并行度為1 -
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)：根據(jù)給定的參數(shù)設(shè)置下次擴(kuò)容值和加載因子，且容量至少為估計(jì)的線程數(shù)concurrencyLevel
2.5 put 操作
2.5.1 put 方法大致步驟
- 計(jì)算 key 的哈希值；
- 如果 table 數(shù)組為空，則先進(jìn)行初始化 (2.5.2節(jié))；
- 根據(jù) hash 值計(jì)算出 key 在表中所處的位置，即
(n - 1) & hash：
- 如果該位置沒有值 ，則直接放入，且不需要加鎖；
- 如果插入位置是連接點(diǎn)，說明正在進(jìn)行擴(kuò)容，則幫助當(dāng)前線程擴(kuò)容；
- 否則加鎖，然后根據(jù)鏈表或樹結(jié)構(gòu)遍歷查找 key 值，找到則進(jìn)行更新，否則新增節(jié)點(diǎn)插入；
- 與 HashMap 類似，若鏈表長度超過閾值，則轉(zhuǎn)為紅黑樹；
- 如果操作3中執(zhí)行的是替換操作，返回被替換的value；
- 否則說明節(jié)點(diǎn)是被新插入的，因此將元素?cái)?shù)量加1
整個(gè)過程中只有3中的第三步需要加鎖，從而提高并行性能
2.5.2 初始化 table 數(shù)組
- 調(diào)用 ConcurrentHashMap 的構(gòu)造方法僅僅只是設(shè)置了一些參數(shù)，而整個(gè) table 的初始化是在向其中插入元素的時(shí)候發(fā)生的，例如 put 方法
- 初始化方法主要應(yīng)用了關(guān)鍵屬性 sizeCtl，如果
sizeCtl < 0，表示其他線程正在進(jìn)行初始化，就放棄操作，從而保證只讓一個(gè)線程對(duì) table 進(jìn)行初始化 - 如果獲得了初始化權(quán)限，就先用 CAS 方法將 sizeCtl 置為-1，防止后續(xù)其他線程進(jìn)入
- 初始化完成后，將 sizeCtl 的值設(shè)為
n - (n >>> 2))，即 0.75 × n
private final Node<K,V>[] initTable()
{
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0)
{
// 其他線程正在進(jìn)行初始化
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1))
{
try
{
if ((tab = table) == null || tab.length == 0)
{
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2); // 0.75 × n
}
}
finally
{
sizeCtl = sc;
}
break;
}
}
return tab;
}
2.6 get 操作
- get 方法沒有進(jìn)行加鎖，其大致步驟為：
- 計(jì)算 key 的哈希值；
- 根據(jù)哈希值查找節(jié)點(diǎn)位置；
- 如果節(jié)點(diǎn)直接在桶的頭節(jié)點(diǎn)上，則直接返回；
- 否則說明有碰撞，根據(jù)樹形結(jié)構(gòu)或鏈表結(jié)構(gòu)使用不同的方法繼續(xù)查找；
- 如果找到則返回對(duì)應(yīng)值，否則返回 null
// 從源碼中可以看出，get方法沒有加鎖
public V get(Object key)
{
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null)
{
if ((eh = e.hash) == h)
{
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null)
{
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
