ConcurrentHashMap源碼分析_JDK1.8版本
聲明
文章均為本人技術筆記，轉載請注明出處
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/
JDK1.6版本
ConcurrentHashMap結構
在JDK1.6中，ConcurrentHashMap將數據分成一段一段存儲，給每一段數據配一把鎖，當一個線程獲得鎖互斥訪問一個段數據時，其他段的數據也可被其他線程訪問；每個Segment擁有一把可重入鎖，因此ConcurrentHashMap的分段鎖數目即為Segment數組長度。ConcurrentHashMap結構：每一個segment都是一個HashEntry[] table， table中的每一個元素本質上都是一個HashEntry的單向隊列（單向鏈表實現）。每一個segment都是一個HashEntry[] table， table中的每一個元素本質上都是一個HashEntry的單向隊列。
鎖分離實現
當一個線程訪問Node/鍵值對數據時，必須獲得與它對應的segment鎖，其他線程可以訪問其他Segment中的數據（鎖分離）；
ConcurrentHashMap聲明
public class ConcurrentHashMap extends AbstractMap implements ConcurrentMap, Serializable
無鎖算法：CAS
樂觀鎖與悲觀鎖
悲觀鎖比如synchronized鎖，為確保其他線程不會干擾當前線程工作，因此掛起其他需要鎖的線程，等待持有鎖的線程釋放；
樂觀鎖總是假設沒有沖突發生去做操作，如果檢測到沖突就失敗重試，知道成功為止；
CAS算法
CAS(Compare And Swap)：CAS算法包含三個參數CAS(V, E, N)，判斷預期值E和內存舊值是否相同(Compare)，如果相等用新值N覆蓋舊值V(Swap)，否則失敗；
當多個線程嘗試使用CAS同時更新同一個變量時，只有其中一個線程能更新變量的值，其他線程失敗（失敗線程不會被阻塞，而是被告知“失敗”，可以繼續嘗試）；
CAS在硬件層面可以被編譯為機器指令執行，因此性能高于基于鎖占有方式實現線程安全；
ConcurrentHashMap結構圖示
與JDK1.6對比
JDK 1.8取消類segments字段，直接用table數組存儲鍵值對，JDK1.6中每個bucket中鍵值對組織方式是單向鏈表，查找復雜度是O(n)，JDK1.8中當鏈表長度超過TREEIFY_THRESHOLD時，鏈表轉換為紅黑樹，查詢復雜度可以降低到O(log n)，改進性能；
鎖分離
JDK1.8中，一個線程每次對一個桶（鏈表 or 紅黑樹）進行加鎖，其他線程仍然可以訪問其他桶；
線程安全
ConcurrentHashMap底層數據結構與HashMap相同，仍然采用table數組+鏈表+紅黑樹結構；
一個線程進行put/remove操作時，對桶（鏈表 or 紅黑樹）加上synchronized獨占鎖；
ConcurrentHashMap采用CAS算法保證線程安全；
ConcurrentHashMap基本數據結構
transient volatile Node[] table：鍵值對桶數組
private transient volatile Node[] nextTable： rehash擴容時用到的新鍵值對數組
private transient volatile long baseCount：記錄當前鍵值對總數，通過CAS更新，對所有線程可見
private transient volatile int sizeCtl
sizeCtl表示鍵值對總數閾值，通過CAS更新, 對所有線程可見
當sizeCtl < 0時，表示多個線程在等待擴容；
當sizeCtl = 0時，默認值；
當sizeCtl > 0時，表示擴容的閾值；
private transient volatile int cellBusy：自旋鎖；
private transient volatile CounterCell[] counterCells: counter cell表，長度總為2的冪次；
static class Segment：在JDK1.8中，Segment類僅僅在序列化和反序列化時發揮作用；
// 視圖
private transient KeySetView keySet
private transient ValuesView values
private transient EntrySetView entrySet
描述鍵值對：Node
static class Node implements Map.Entry {
final int hash;
final K key;
// 鍵值對的value和next均為volatile類型
volatile V val;
volatile Node next;
...
}
ConcurrentHashMap重要方法分析
構造函數
ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
該構造器會根據輸入的initialCapacity確定一個 >= initialCapacity的最小2的次冪；
concurrentLevel：在JDK1.8之前本質是ConcurrentHashMap分段鎖總數，表示同時更新ConcurrentHashMap且不產生鎖競爭的最大線程數；在JDK1.8中，僅在構造器中確保初始容量>=concurrentLevel，為兼容舊版本而保留；
添加/更新鍵值對：putVal
putVal方法分析
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
// 不斷CAS探測，如果其他線程正在修改tab，CAS嘗試失敗，直到成功為止
for (Node[] tab = table;;) {
Node f; int n, i, fh;
// 空表，對tab進行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
/**
* CAS探測空桶
* 計算key所在bucket表中數組索引: i = (n - 1) & hash)
*/
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// CAS添加新鍵值對
if (casTabAt(tab, i, null,
new Node(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 檢測到tab[i]桶正在進行rehash,
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 對桶的首元素上鎖獨占
synchronized (f) {
if (tabAt(tab, i) == f) {
// 桶中鍵值對組織形式是鏈表
if (fh >= 0) {
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
// 查找到對應鍵值對，更新值
if (!onlyIfAbsent)
e.val = value;
break;
}
// 桶中沒有對應鍵值對，插入到鏈表尾部
Node pred = e;
if ((e = e.next) == null) {
pred.next = new Node(hash, key,
value, null);
break;
}
}
}
// 桶中鍵值對組織形式是紅黑樹
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// 檢查桶中鍵值對總數
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
// 鏈表轉換為紅黑樹
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 更新baseCount
addCount(1L, binCount);
return null;
}
synchronized (f) {}操作通過對桶的首元素 = 鏈表表頭 Or 紅黑樹根節點加鎖，從而實現對整個桶進行加鎖，有鎖分離思想的體現；
獲取鍵值對：get
public V get(Object key) {
Node[] tab; Node 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;
}
get方法通過CAS保證鍵值對的原子性，當tab[i]被鎖住，CAS失敗并不斷重試，保證get不會出錯；
刪除鍵值對：remove
擴容機制
transfer
當baseCount超過sizeCtl，將table中所有bin內的鍵值對拷貝到nextTable；
待補充；
helpTransfer
待補充；
table原子操作方法
獲取tab[i]：tabAt
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
tabAt方法原子讀取table[i]；調用Unsafe對象的getObjectVolatile方法獲取tab[i]，由于對volatile寫操作happen-before于volatile讀操作，因此其他線程對table的修改均對get讀取可見；
((long)i << ASHIFT) + ABASE)計算i元素的地址
CAS算法更新鍵值對：casTabAt
static final boolean casTabAt(Node[] tab, int i,
Node c, Node v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
casTabAt通過compareAndSwapObject方法比較tabp[i]和v是否相等，相等就用c更新tab[i];
更新鍵值對：setTabAt
static final void setTabAt(Node[] tab, int i, Node v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
僅在synchronized同步塊中被調用，更新鍵值對；
CAS更新baseCount
addCountaddCount
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// s = b + x，完成baseCount++操作；
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
// 多線程CAS發生失敗時執行
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
s = sumCount();
}
if (check >= 0) {
Node[] tab, nt; int n, sc;
// 當更新后的鍵值對總數baseCount >= 閾值sizeCtl時，進行rehash
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
// sc < 0 表示其他線程已經在rehash
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 其他線程的rehash操作已經完成，當前線程可以進行rehash
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// sc >= 0 表示只有當前線程在進行rehash操作，調用輔助擴容方法transfer
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
addCount負責對baseCount + 1操作，CounterCell是Striped64類型，否則應對高并發問題；
fullAddCount
待補充；
參考
[1] 《Java并發編程的藝術》
[2] ??http://www.cnblogs.com/leesf4...
[3] ??http://blog.csdn.net/u0108877...
[4] ??http://www.cnblogs.com/Mainz/...
[5] ??http://www.cnblogs.com/huaizu...
[6] ??http://www.cnblogs.com/everSe...
