ConcurrentHashMap詳解
JDK1.7版本的CurrentHashMap的實(shí)現(xiàn)原理
在JDK1.7中ConcurrentHashMap采用了數(shù)組+Segment+分段鎖的方式實(shí)現(xiàn)仿贬。
1.Segment(分段鎖)
ConcurrentHashMap中的分段鎖稱(chēng)為Segment，它即類(lèi)似于HashMap的結(jié)構(gòu)睬澡，即內(nèi)部擁有一個(gè)Entry數(shù)組艇拍，數(shù)組中的每個(gè)元素又是一個(gè)鏈表,同時(shí)又是一個(gè)ReentrantLock（Segment繼承了ReentrantLock）。
2.內(nèi)部結(jié)構(gòu)
ConcurrentHashMap使用分段鎖技術(shù)骏掀，將數(shù)據(jù)分成一段一段的存儲(chǔ)鸠澈，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段數(shù)據(jù)的時(shí)候截驮，其他段的數(shù)據(jù)也能被其他線程訪問(wèn)笑陈，能夠?qū)崿F(xiàn)真正的并發(fā)訪問(wèn)。如下圖是ConcurrentHashMap的內(nèi)部結(jié)構(gòu)圖：
從上面的結(jié)構(gòu)我們可以了解到葵袭，ConcurrentHashMap定位一個(gè)元素的過(guò)程需要進(jìn)行兩次Hash操作涵妥。
第一次Hash定位到Segment，第二次Hash定位到元素所在的鏈表的頭部坡锡。
3.該結(jié)構(gòu)的優(yōu)劣勢(shì)
壞處
這一種結(jié)構(gòu)的帶來(lái)的副作用是Hash的過(guò)程要比普通的HashMap要長(zhǎng)
好處
寫(xiě)操作的時(shí)候可以只對(duì)元素所在的Segment進(jìn)行加鎖即可蓬网，不會(huì)影響到其他的Segment，這樣鹉勒，在最理想的情況下拳缠，ConcurrentHashMap可以最高同時(shí)支持Segment數(shù)量大小的寫(xiě)操作（剛好這些寫(xiě)操作都非常平均地分布在所有的Segment上）。
所以贸弥，通過(guò)這一種結(jié)構(gòu)窟坐，ConcurrentHashMap的并發(fā)能力可以大大的提高。
JDK1.8中的實(shí)現(xiàn)
ConcurrentHashMap取消了segment分段鎖绵疲，而采用CAS和synchronized來(lái)保證并發(fā)安全哲鸳。數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)一樣，數(shù)組+鏈表/紅黑二叉樹(shù)盔憨。 synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹(shù)的首節(jié)點(diǎn)徙菠，這樣只要hash不沖突，就不會(huì)產(chǎn)生并發(fā)郁岩，效率又提升N倍婿奔。
JDK1.8的ConcurrentHashMap的結(jié)構(gòu)圖如下：
ConcurrentHashMap 源碼分析
ConcurrentHashMap 類(lèi)結(jié)構(gòu)參照HashMap缺狠，這里列出HashMap沒(méi)有的幾個(gè)屬性。
/**
hash表初始化或擴(kuò)容時(shí)的一個(gè)控制位標(biāo)識(shí)量萍摊。
負(fù)數(shù)代表正在進(jìn)行初始化或擴(kuò)容操作
-1代表正在初始化
-N 表示有N-1個(gè)線程正在進(jìn)行擴(kuò)容操作
正數(shù)或0代表hash表還沒(méi)有被初始化挤茄，這個(gè)數(shù)值表示初始化或下一次進(jìn)行擴(kuò)容的大小 */
private transient volatile int sizeCtl;
// 以下兩個(gè)是用來(lái)控制擴(kuò)容的時(shí)候 單線程進(jìn)入的變量
private static int RESIZE_STAMP_BITS = 16;
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
static final int MOVED = -1; // hash值是-1，表示這是一個(gè)forwardNode節(jié)點(diǎn)
static final int TREEBIN = -2; // hash值是-2 表示這時(shí)一個(gè)TreeBin節(jié)點(diǎn)
分析代碼主要目的：分析是如果利用CAS和Synchronized進(jìn)行高效的同步更新數(shù)據(jù)冰木。
下面插入數(shù)據(jù)源碼：
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
//ConcurrentHashMap 不允許插入null鍵穷劈，HashMap允許插入一個(gè)null鍵
if (key == null || value == null) throw new NullPointerException();
//計(jì)算key的hash值
int hash = spread(key.hashCode());
int binCount = 0;
//for循環(huán)的作用：因?yàn)楦略厥鞘褂肅AS機(jī)制更新，需要不斷的失敗重試踊沸，直到成功為止歇终。
for (Node<K,V>[] tab = table;;) {
// f：鏈表或紅黑二叉樹(shù)頭結(jié)點(diǎn)，向鏈表中添加元素時(shí)逼龟，需要synchronized獲取f的鎖评凝。
Node<K,V> f; int n, i, fh;
//判斷Node[]數(shù)組是否初始化，沒(méi)有則進(jìn)行初始化操作
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//通過(guò)hash定位Node[]數(shù)組的索引坐標(biāo)腺律，是否有Node節(jié)點(diǎn)肥哎，如果沒(méi)有則使用CAS進(jìn)行添加（鏈表的頭結(jié)點(diǎn)），添加失敗則進(jìn)入下次循環(huán)疾渣。
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
}
//檢查到內(nèi)部正在移動(dòng)元素（Node[] 數(shù)組擴(kuò)容）
else if ((fh = f.hash) == MOVED)
//幫助它擴(kuò)容
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//鎖住鏈表或紅黑二叉樹(shù)的頭結(jié)點(diǎn)
synchronized (f) {
//判斷f是否是鏈表的頭結(jié)點(diǎn)
if (tabAt(tab, i) == f) {
//如果fh>=0 是鏈表節(jié)點(diǎn)
if (fh >= 0) {
binCount = 1;
//遍歷鏈表所有節(jié)點(diǎn)
for (Node<K,V> e = f;; ++binCount) {
K ek;
//如果節(jié)點(diǎn)存在，則更新value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
//不存在則在鏈表尾部添加新節(jié)點(diǎn)崖飘。
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//TreeBin是紅黑二叉樹(shù)節(jié)點(diǎn)
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
//添加樹(shù)節(jié)點(diǎn)
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//如果鏈表長(zhǎng)度已經(jīng)達(dá)到臨界值8 就需要把鏈表轉(zhuǎn)換為樹(shù)結(jié)構(gòu)
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//將當(dāng)前ConcurrentHashMap的size數(shù)量+1
addCount(1L, binCount);
return null;
}
- 判斷Node[]數(shù)組是否初始化榴捡，沒(méi)有則進(jìn)行初始化操作
- 通過(guò)hash定位Node[]數(shù)組的索引坐標(biāo)，是否有Node節(jié)點(diǎn)朱浴，如果沒(méi)有則使用CAS進(jìn)行添加（鏈表的頭結(jié)點(diǎn)）吊圾，添加失敗則進(jìn)入下次循環(huán)。
- 檢查到內(nèi)部正在擴(kuò)容翰蠢，如果正在擴(kuò)容项乒，就幫助它一塊擴(kuò)容。
- 如果f!=null梁沧，則使用synchronized鎖住f元素（鏈表/紅黑二叉樹(shù)的頭元素）
4.1 如果是Node(鏈表結(jié)構(gòu))則執(zhí)行鏈表的添加操作檀何。
4.2 如果是TreeNode(樹(shù)型結(jié)果)則執(zhí)行樹(shù)添加操作。 - 判斷鏈表長(zhǎng)度已經(jīng)達(dá)到臨界值8 就需要把鏈表轉(zhuǎn)換為樹(shù)結(jié)構(gòu)廷支。
總結(jié)：
????JDK8中的實(shí)現(xiàn)也是鎖分離的思想频鉴，它把鎖分的比segment（JDK1.5）更細(xì)一些，只要hash不沖突恋拍，就不會(huì)出現(xiàn)并發(fā)獲得鎖的情況垛孔。它首先使用無(wú)鎖操作CAS插入頭結(jié)點(diǎn)，如果插入失敗施敢，說(shuō)明已經(jīng)有別的線程插入頭結(jié)點(diǎn)了周荐，再次循環(huán)進(jìn)行操作狭莱。如果頭結(jié)點(diǎn)已經(jīng)存在，則通過(guò)synchronized獲得頭結(jié)點(diǎn)鎖概作，進(jìn)行后續(xù)的操作腋妙。性能比segment分段鎖又再次提升。
