一、概述
??從本篇文章開始，我將會對concurrent包下常用的類的使用以及源碼學(xué)習(xí)進(jìn)行一個記錄，本篇文章主要是來了解下ConcurrentHashMap的源碼。ConcurrentHashMap其實我們都不陌生了惩淳，是一種線程安全的Map集合，接下來我們就來看下的內(nèi)部實現(xiàn)。
本文中的源碼是基于JDK1.8的思犁。
二代虾、源碼
1. 繼承結(jié)構(gòu)及構(gòu)造方法
首先，我們來看下ConcurrentHashMap的繼承機(jī)構(gòu)：
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable {
首先激蹲，ConcurrentHashMap繼承自AbstractMap棉磨，前面學(xué)習(xí)HashMap的時候曾簡單說過，AbstractMap這個類提供了Map接口的一些簡單實現(xiàn)学辱，用來減少該接口實現(xiàn)的一些重復(fù)操作乘瓤，以最小化實現(xiàn)該接口所需的工作量；而接口ConcurrentMap策泣，根據(jù)文檔描述衙傀，這個接口是用來提供線程安全性和原子性保證的映射；最后萨咕，實現(xiàn)了Serializable统抬，表明該類支持序列化。
public ConcurrentHashMap()
public ConcurrentHashMap(int initialCapacity)
public ConcurrentHashMap(Map<? extends K, ? extends V> m)
public ConcurrentHashMap(int initialCapacity, float loadFactor)
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel)
構(gòu)造方法的話危队，都比較常規(guī)聪建，不多說了。
2. 常用屬性
首先說下茫陆，JDK1.8之后金麸，ConcurrentHashMap的內(nèi)部存儲結(jié)構(gòu)其實和HashMap是一樣的，都是通過數(shù)組 + 鏈表 + 紅黑樹來實現(xiàn)的簿盅。有一些屬性和HashMap是相似的挥下，我們這里就簡單略過。
// 默認(rèn)初始化容量
private static final int DEFAULT_CAPACITY = 16;
// 最大容量挪鹏，2的30次方
private static final int MAXIMUM_CAPACITY = 1 << 30;
//最大數(shù)組容量
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//負(fù)載因子
private static final float LOAD_FACTOR = 0.75f;
//樹形化的三個參數(shù)见秽，不多說
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
然后再看下兩個比較特殊的屬性：
private transient volatile int sizeCtl;
該屬性是用于控制數(shù)組大小和擴(kuò)容的標(biāo)識符愉烙，值不同有不同的含義：
- 如果是負(fù)數(shù)讨盒，表示數(shù)組正在初始化或者擴(kuò)容；如果是-1步责，表示正在初始化返顺，-N 表示有N-1個線程正在進(jìn)行擴(kuò)容操作；
- 如果是0或者是正數(shù)蔓肯，表示table還沒有被初始化遂鹊，該值表示初始化或下此擴(kuò)容的大小，類似于擴(kuò)容閾值蔗包；它的值始終是當(dāng)前ConcurrentHashMap容量的0.75倍秉扑，這與loadfactor是對應(yīng)的。實際容量>=sizeCtl，則擴(kuò)容舟陆。
另外的一個參數(shù)：
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
該參數(shù)是默認(rèn)的并發(fā)級別误澳，JDK1.8中已經(jīng)不再使用，只是為了與以前的版本兼容才定義的秦躯。由于JDK1.8之前ConcurrentHashMap是通過分段鎖來實現(xiàn)的忆谓，ConcurrentHashMap由多個Segment組成，而每個Segment都有對應(yīng)的一把鎖來實現(xiàn)線程安全踱承。JDK1.8之后倡缠，Segment仍然存在，而該字段是服務(wù)于Segment的茎活，所以昙沦，兩者都是為了兼容原先的版本而存在的。
3. 相關(guān)節(jié)點類
3.1 Node類
保存table數(shù)組的元素载荔，一個Node就是table中的一個元素桅滋。該類無法進(jìn)行修改，只能進(jìn)行只讀遍歷操作：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
//構(gòu)造方法身辨，get方法
public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
public final String toString(){ return key + "=" + val; }
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
public final boolean equals(Object o) {
Object k, v, u; Map.Entry<?,?> e;
return ((o instanceof Map.Entry) &&
(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == (u = val) || v.equals(u)));
}
/**
* Virtualized support for map.get(); overridden in subclasses.
*/
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;
}
}
Node類的valu及next屬性都使用了volatile關(guān)鍵字修飾丐谋，表示在并發(fā)環(huán)境下的修改對其他線程都是可見的，并且Node類提供了一個find方法用于輔助get方法的調(diào)用煌珊。
3.2 TreeNode和TreeBin
/**
* Nodes for use in TreeBins
*/
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
static final class TreeBin<K,V> extends Node<K,V> {
TreeNode<K,V> root;
volatile TreeNode<K,V> first;
volatile Thread waiter;
volatile int lockState;
// values for lockState
static final int WRITER = 1; // set while holding write lock
static final int WAITER = 2; // set when waiting for write lock
static final int READER = 4; // increment value for setting read lock
}
TreeNode表示紅黑樹的具體實現(xiàn)号俐，但正如該類的注釋而言：Nodes for use in TreeBins，該類只是為TreeBin類服務(wù)定庵，最終有TreeBin來操作紅黑樹吏饿。TreeBin用于封裝維護(hù)TreeNode，包含了一系列對樹的操作方法蔬浙。
4. 實現(xiàn)
ConcurrentHashMap中使用了大量的CAS算法猪落，總體上實現(xiàn)線程安全的方式是通過CAS + synchronized來實現(xiàn)的，至于CAS畴博，可以參考該文章：CAS原理深度分析笨忌，接下來我們來分析下幾個主要的方法，首先俱病，還是來看下put方法官疲。
4.1 put方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 1. key和value都不能為空
if (key == null || value == null) throw new NullPointerException();
// 2. 對key的hashCode再進(jìn)行一次計算得到hash值
int hash = spread(key.hashCode());
int binCount = 0;
// 3. 無限循環(huán)操作，直到插入成功
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 如果表為空亮隙，或表的容量為0途凫，初始化表
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 表不為空，且表中對應(yīng)元素已經(jīng)存在溢吻，比較并替換
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 如果該節(jié)點的hash值為MOVED维费，說明正在進(jìn)行擴(kuò)容操作，則當(dāng)前線程會優(yōu)先進(jìn)行幫助擴(kuò)容操作
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 其他情況下的操作
else {
V oldVal = null;
// 對hash桶進(jìn)行加鎖操作，
synchronized (f) {
// 再次檢查表中下標(biāo)為i的節(jié)點是否為同一個節(jié)點
if (tabAt(tab, i) == f) {
// 鏈表節(jié)點
if (fh >= 0) {
// 這里的bitCount = 1
binCount = 1;
// 又一個無限循環(huán)犀盟，這里bitCount自增噪漾，表示鏈表中的節(jié)點數(shù)量
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 如果節(jié)點的hash值相等，并且key也相等且蓬，那么先將舊值取出欣硼，然后進(jìn)行替換操作
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
// 其他情況，如果當(dāng)前節(jié)點的下一個節(jié)點為空恶阴，也就是最后一個節(jié)點
// 則將新節(jié)點在尾部插入
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 如果節(jié)點是樹類型
else if (f instanceof TreeBin) {
Node<K,V> p;
// 這里的bitCount = 2
binCount = 2;
// 執(zhí)行樹的插入邏輯
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// bitCount判斷
if (binCount != 0) {
// 大于樹形化閾值诈胜，進(jìn)行樹形化操作
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
// 返回舊的值
if (oldVal != null)
return oldVal;
break;
}
}
}
// bitCount加1
addCount(1L, binCount);
return null;
}
方法有點長，我們來依次說下：
- 首先冯事，ConcurrentHashMap的key和value都不能為空焦匈，這點和HashMap有點不同；
- 首先昵仅，計算key的hash值缓熟，然后進(jìn)入循環(huán)；如果表為空摔笤，初始化表够滑；如果不為空，通過key的hash在表中查找元素吕世，如果找不到彰触，說明該hash桶為空，通過CAS操作將值放入桶中命辖；如果hash值為-1况毅，也即是MOVED，則說明桶正在進(jìn)行擴(kuò)容尔艇，幫助進(jìn)行擴(kuò)容操作尔许；
- 上面情況都不滿足，則開始進(jìn)行分段加鎖终娃，遍歷操作味廊。首先對桶中的第一個節(jié)點進(jìn)行加鎖，然后對鏈表進(jìn)行遍歷尝抖，根據(jù)hash值和key值進(jìn)行比較毡们，存在更新迅皇，不存在插入進(jìn)去昧辽；如果該節(jié)點是紅黑樹類型，則進(jìn)行紅黑樹的插入邏輯登颓；
- 判斷鏈表的長度是否達(dá)到樹形化閾值搅荞，如果達(dá)到了，進(jìn)行樹形化；
在進(jìn)行put操作的時候咕痛，會涉及到一些方法痢甘，我們來簡單看下。先看下初始化方法initTable：
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// 如果sizeCtl小于0茉贡，說明table正在進(jìn)行初始化或擴(kuò)容塞栅，則當(dāng)前線程讓出CPU資源
// 讓其他線程執(zhí)行
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// 比較SIZECTL與sc，相等設(shè)置為-1腔丧，不相等說明其他線程正在初始化或者已經(jīng)初始化完成
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// 再次判斷數(shù)組是否初始化
if ((tab = table) == null || tab.length == 0) {
// 然后比較sc的值是否大于0放椰，大于0則n為sc，否則愉粤，n為默認(rèn)初始容量
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// sc = n * 3/4砾医，注意這里無符號右移的計算
sc = n - (n >>> 2);
}
} finally {
// 最后設(shè)置sizeCtl的值
sizeCtl = sc;
}
break;
}
}
return tab;
}
從這里可以看到，table的值是與sizeCtl相關(guān)的衣厘。
然后來看下另一個方法：tabAt方法如蚜，該方法是一個CAS方法，為了方便CAS方法的調(diào)用影暴，在ConcurrentHashMap中定義了Unsafe的一個實例：
private static final sun.misc.Unsafe U;
而該方法則是用于獲取table中下標(biāo)為i的節(jié)點：
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
另一個CAS方法casTabAt错邦，則是一個比較交換的操作：
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
比較下標(biāo)為i的節(jié)點是否是c，如果是型宙，替換為v節(jié)點兴猩；
另外，還涉及到樹形化方法treeifyBin早歇，及擴(kuò)容方法tryPresize倾芝，樹形化方法就不說了，來看下擴(kuò)容方法：
private final void tryPresize(int size) {
// 如果給定的容量大于了最大值的1/2，則直接擴(kuò)為最大值淆储，否則走tableSizeFor方法
// tableSizeFor方法是找到大于等于count的最小的2的冪次方
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
// sizeCtl大于等于0档玻，擴(kuò)容
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
// 同樣先判斷是否初始化
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
// 比較并設(shè)置為-1，表示正在進(jìn)行初始化
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
// 如果要擴(kuò)容的值小于等于原閥值借尿，或現(xiàn)有容量>=最大值，什么都不用做了
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
4.2 get方法
接下來來看下get方法屉来。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 1. 計算key的hash
int h = spread(key.hashCode());
// 2. 對table是否為空判斷路翻，并判斷key所對應(yīng)的桶tab[i]是否存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 第一個節(jié)點
if ((eh = e.hash) == h) {
// hash相等，key相等茄靠，返回值
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// hash值小于0茂契，去樹中查找
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方法就相對簡單些了慨绳，與HashMap的get方法差不多：
- 計算key的hash值掉冶；
- 對table進(jìn)行為空判斷真竖，不為空，根據(jù)hash定位到table中的位置厌小；
- 先檢查tab[i]的頭節(jié)點是否滿足恢共，不滿足再去遍歷樹或者鏈表；
4.3 size方法
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
size方法用于計算Map中的容量璧亚，該方法從JDK1.2就有了讨韭，不過不建議使用了，因為推薦了新的方法：mappingCount方法癣蟋。
public long mappingCount() {
long n = sumCount();
return (n < 0L) ? 0L : n; // ignore transient negative values
}
在mappingCount的注釋中拐袜，我們可以看出：
- 該方法建議用來代替size()方法使用，因為ConcurrentHashMap可能會包含更多的映射結(jié)果梢薪，即超過int類型的最大值蹬铺；
- 該方法返回的是一個估計值，由于存在并發(fā)的插入和刪除秉撇，因此返回值可能與實際值會有出入；
看到源碼會發(fā)現(xiàn)兩者其實調(diào)用的都是sumCount方法琐馆，看下sumCount的源碼：
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
最終結(jié)果值還是通過屬性baseCount計算來的。而baseCount是基于CAS來更新的瘦麸，所以實際值并不一定是當(dāng)前Map的真實元素個數(shù)。
三滋饲、總結(jié)
1. 問題
（1）put操作的時候，為什么當(dāng)hash值為MOVED的時候屠缭，桶正在進(jìn)行擴(kuò)容操作呢？
??通過查看調(diào)用軌跡呵曹，我們可以看到是類型為ForwardingNode的節(jié)點，構(gòu)造了一個hash值為MOVED的Node奄喂，我們來看下這個類：
/**
* A node inserted at head of bins during transfer operations.
*/
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
}
這個類是一個特殊的Node節(jié)點铐殃，該節(jié)點的hash值是-1，也就是MOVED跨新，該類只會在擴(kuò)容的時候用到富腊，用于在擴(kuò)容期間，插入到桶的頭部的節(jié)點玻蝌。也可以理解為一個占位符蟹肘，表示當(dāng)前節(jié)點正在被移動词疼。
2. 總結(jié)
JDK1.8中的ConcurrentHashMap的數(shù)據(jù)結(jié)果和HashMap的是一樣的俯树，然后通過CAS和 synchronized 關(guān)鍵字來保證線程安全帘腹。本次內(nèi)容只簡單了解了ConcurrentHashMap的put和get操作，其他的操作其實步驟都差不太多许饿，等有時間了阳欲，再去了解下。
本文參考自：
《Java源碼分析》：ConcurrentHashMap JDK1.8
docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html
【JUC】JDK1.8源碼分析之ConcurrentHashMap（一）
http://www.cnblogs.com/huaizuo/archive/2016/04/20/5413069.html
