ConcurrentHashMap是如何保證線程安全的
文章已同步發(fā)表于微信公眾號(hào)JasonGaoH献幔，ConcurrentHashMap是如何保證線程安全的
之前分析過(guò)HashMap的一些實(shí)現(xiàn)細(xì)節(jié)忘晤，關(guān)于HashMap你需要知道的一些細(xì)節(jié), 今天我們從源碼角度來(lái)看看ConcurrentHashMap是如何實(shí)現(xiàn)線程安全的，其實(shí)網(wǎng)上這類文章分析特別多齿桃，秉著”紙上得來(lái)終覺(jué)淺，絕知此事要躬行“的原則煮盼，我們嘗試自己去分析下短纵，希望這樣對(duì)于ConcurrentHashMap有一個(gè)更深刻的理解。
為什么說(shuō)HashMap線程不安全僵控，而ConcurrentHashMap就線程安全
其實(shí)ConcurrentHashMap在Android開(kāi)發(fā)中使用的場(chǎng)景并不多香到，但是ConcurrentHashMap為了支持多線程并發(fā)這些優(yōu)秀的設(shè)計(jì)卻是最值得我們學(xué)習(xí)的地方，往往”ConcurrentHashMap是如何實(shí)現(xiàn)線程安全“這類問(wèn)題卻是面試官比較喜歡問(wèn)的問(wèn)題报破。
首先悠就，我們嘗試用代碼模擬下HashMap在多線程場(chǎng)景下會(huì)不安全，如果把這個(gè)場(chǎng)景替換成ConcurrentHashMap會(huì)不會(huì)有問(wèn)題充易。
因?yàn)椴煌谄渌木€程同步問(wèn)題梗脾，想模擬出一種場(chǎng)景來(lái)表明HashMap是線程不安全的稍微有點(diǎn)麻煩，可能是hash散列有關(guān)盹靴，在數(shù)據(jù)量較小的情況下炸茧，計(jì)算出來(lái)的hashCode是不太容易產(chǎn)生碰撞的瑞妇，網(wǎng)上很多文章都是嘗試從源碼角度來(lái)分析HashMap可能會(huì)導(dǎo)致的線程安全問(wèn)題。
我們來(lái)看下下面這段代碼,我們構(gòu)造10個(gè)線程梭冠，每個(gè)線程分別往map中put 1000個(gè)數(shù)據(jù)辕狰，為了保證每個(gè)數(shù)據(jù)的key不一樣，我們將i+ 線程名字來(lái)作為map 的key控漠，這樣蔓倍，如果所有的線程都累加完的話，我們預(yù)期的map的size應(yīng)該是10 * 1000 = 10000盐捷。
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class HashMapTest {
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
// Map<String, String> map = new ConcurrentHashMap<String, String>();
for (int i = 0; i < 10; i++) {
MyThread testThread = new MyThread(map, "線程名字：" + i);
testThread.start();
}
//等待所有線程都結(jié)束
while(Thread.activeCount() > 1)
Thread.yield();
System.out.println(map.size());
}
}
class MyThread extends Thread {
public Map<String, String> map;
public String name;
public MyThread(Map<String, String> map, String name) {
this.map = map;
this.name = name;
}
public void run() {
for(int i =0;i<1000;i++) {
map.put(i + name, i + name);
}
}
}
使用HashMap偶翅，程序運(yùn)行，結(jié)果如下：
9930
那我們?nèi)绻堰@里的HashMap換成ConcurrentHashMap來(lái)試試看看效果如何毙驯，輸出結(jié)果如下：
10000
我們發(fā)現(xiàn)不管運(yùn)行幾次倒堕，HashMap的size都是小于10000的，而ConcurrentHashMap的size都是10000爆价。從這個(gè)角度也證明了ConcurrentHashMap是線程安全的垦巴，而HashMap則是線程不安全的。
HashMap在多線程put的時(shí)候铭段，當(dāng)產(chǎn)生hash碰撞的時(shí)候骤宣，會(huì)導(dǎo)致丟失數(shù)據(jù)，因?yàn)橐猵ut的兩個(gè)值hash相同序愚，如果這個(gè)對(duì)于hash桶的位置個(gè)數(shù)小于8憔披，那么應(yīng)該是以鏈表的形式存儲(chǔ)，由于沒(méi)有做通過(guò)爸吮，后面put的元素可能會(huì)直接覆蓋之前那個(gè)線程put的數(shù)據(jù)芬膝，這樣就導(dǎo)致了數(shù)據(jù)丟失。
其實(shí)列舉上面這個(gè)例子只是為了從一個(gè)角度來(lái)展示下為什么說(shuō)HashMap線程不安全形娇，而ConcurrentHashMap則是線程安全的锰霜，鑒于HashMap線程安全例子比較難列舉出來(lái)，所有才通過(guò)打印size這個(gè)角度來(lái)模擬了下桐早。
這篇文章深入解讀HashMap線程安全性問(wèn)題就詳細(xì)介紹了HashMap可能會(huì)出現(xiàn)線程安全問(wèn)題癣缅。
文章主要講了兩個(gè)可能會(huì)出現(xiàn)線程不安全地方，一個(gè)是多線程的put可能導(dǎo)致元素的丟失哄酝，另一個(gè)是put和get并發(fā)時(shí)友存，可能導(dǎo)致get為null，但是也僅是在源碼層面分析了下陶衅，因?yàn)檫@中場(chǎng)景想要完全用代碼展示出來(lái)是稍微有點(diǎn)麻煩的屡立。
接下來(lái)我們來(lái)看看ConcurrentHashMap是如何做到線程安全的。
JDK8的ConcurrentHashMap文檔提煉
- ConcurrentHashMap支持檢索的完全并發(fā)和更新的高預(yù)期并發(fā)性,這里的說(shuō)法很有意思檢索支持完全并發(fā)搀军，更新則支持高預(yù)期并發(fā)性侠驯，因?yàn)樗臋z索操作是沒(méi)有加鎖的抡秆，實(shí)際上檢索也沒(méi)有必要加鎖。
- 實(shí)際上ConcurrentHashMap和Hashtable在不考慮實(shí)現(xiàn)細(xì)節(jié)來(lái)說(shuō)吟策，這兩者完全是可以互相操作的,Hashtable在get儒士，put，remove等這些方法中全部加入了synchronized檩坚，這樣的問(wèn)題是能夠?qū)崿F(xiàn)線程安全着撩，但是缺點(diǎn)是性能太差，幾乎所有的操作都加鎖的匾委，但是ConcurrentHashMap的檢測(cè)操作卻是沒(méi)有加鎖的拖叙。
- ConcurrentHashMap檢索操作(包括get)通常不會(huì)阻塞，因此可能與更新操作(包括put和remove)重疊赂乐。
- ConcurrentHashMap跟Hashtable類似但不同于HashMap薯鳍，它不可以存放空值，key和value都不可以為null挨措。
印象中一直以為ConcurrentHashMap是基于Segment分段鎖來(lái)實(shí)現(xiàn)的挖滤，之前沒(méi)仔細(xì)看過(guò)源碼，一直有這么個(gè)錯(cuò)誤的認(rèn)識(shí)浅役。ConcurrentHashMap是基于Segment分段鎖來(lái)實(shí)現(xiàn)的斩松，這句話也不能說(shuō)不對(duì)，加個(gè)前提條件就是正確的了觉既，ConcurrentHashMap從JDK1.5開(kāi)始隨java.util.concurrent包一起引入JDK中惧盹，在JDK8以前，ConcurrentHashMap都是基于Segment分段鎖來(lái)實(shí)現(xiàn)的瞪讼，在JDK8以后钧椰，就換成synchronized和CAS這套實(shí)現(xiàn)機(jī)制了。
JDK1.8中的ConcurrentHashMap中仍然存在Segment這個(gè)類符欠，而這個(gè)類的聲明則是為了兼容之前的版本序列化而存在的嫡霞。
/**
* Stripped-down version of helper class used in previous version,
* declared for the sake of serialization compatibility.
*/
static class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
final float loadFactor;
Segment(float lf) { this.loadFactor = lf; }
}
JDK1.8中的ConcurrentHashMap不再使用Segment分段鎖，而是以table數(shù)組的頭結(jié)點(diǎn)作為synchronized的鎖背亥。和JDK1.8中的HashMap類似，對(duì)于hashCode相同的時(shí)候悬赏，在Node節(jié)點(diǎn)的數(shù)量少于8個(gè)時(shí)狡汉，這時(shí)的Node存儲(chǔ)結(jié)構(gòu)是鏈表形式，時(shí)間復(fù)雜度為O(N)闽颇，當(dāng)Node節(jié)點(diǎn)的個(gè)數(shù)超過(guò)8個(gè)時(shí)盾戴，則會(huì)轉(zhuǎn)換為紅黑樹(shù)，此時(shí)訪問(wèn)的時(shí)間復(fù)雜度為O(long(N))兵多。
/**
* The array of bins. Lazily initialized upon first insertion.
* Size is always a power of two. Accessed directly by iterators.
*/
transient volatile Node<K,V>[] table;
數(shù)據(jù)結(jié)構(gòu)圖如下所示：
其實(shí)ConcurrentHashMap保證線程安全主要有三個(gè)地方尖啡。
- 一橄仆、使用volatile保證當(dāng)Node中的值變化時(shí)對(duì)于其他線程是可見(jiàn)的
- 二、使用table數(shù)組的頭結(jié)點(diǎn)作為synchronized的鎖來(lái)保證寫(xiě)操作的安全
- 三衅斩、當(dāng)頭結(jié)點(diǎn)為null時(shí)盆顾，使用CAS操作來(lái)保證數(shù)據(jù)能正確的寫(xiě)入。
使用volatile
可以看到畏梆，Node中的val和next都被volatile關(guān)鍵字修飾您宪。
volatile的happens-before規(guī)則：對(duì)一個(gè)volatile變量的寫(xiě)一定可見(jiàn)（happens-before)于隨后對(duì)它的讀。
也就是說(shuō)奠涌，我們改動(dòng)val的值或者next的值對(duì)于其他線程是可見(jiàn)的宪巨，因?yàn)関olatile關(guān)鍵字，會(huì)在讀指令前插入讀屏障溜畅，可以讓高速緩存中的數(shù)據(jù)失效捏卓，重新從主內(nèi)存加載數(shù)據(jù)。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
}
...
另外慈格，ConcurrentHashMap提供類似tabAt來(lái)讀取Table數(shù)組中的元素怠晴，這里是以volatile讀的方式讀取table數(shù)組中的元素，主要通過(guò)Unsafe這個(gè)類來(lái)實(shí)現(xiàn)的峦椰，保證其他線程改變了這個(gè)數(shù)組中的值的情況下龄寞，在當(dāng)前線程get的時(shí)候能拿到。
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);
}
而與之對(duì)應(yīng)的汤功，是setTabAt,這里是以volatile寫(xiě)的方式往數(shù)組寫(xiě)入元素物邑，這樣能保證修改后能對(duì)其他線程可見(jiàn)。
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
我們來(lái)看下ConcurrentHashMap的putVal方法：
/** Implementation for put and putIfAbsent */
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;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//當(dāng)頭結(jié)點(diǎn)為null,則通過(guò)casTabAt方式寫(xiě)入
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
}
else if ((fh = f.hash) == MOVED)
//正在擴(kuò)容
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//頭結(jié)點(diǎn)不為null滔金，使用synchronized加鎖
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
//此時(shí)hash桶是鏈表結(jié)構(gòu)
binCount = 1;
for (Node<K,V> 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<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
//此時(shí)是紅黑樹(shù)
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
//當(dāng)鏈表結(jié)構(gòu)大于等于8色解，則將鏈表轉(zhuǎn)換為紅黑樹(shù)
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
在putVal方法重要的地方都加了注釋，可以幫助理解餐茵，現(xiàn)在我們一步一步來(lái)看putVal方法科阎。
使用CAS
當(dāng)有一個(gè)新的值需要put到ConcurrentHashMap中時(shí)，首先會(huì)遍歷ConcurrentHashMap的table數(shù)組忿族，然后根據(jù)key的hashCode來(lái)定位到需要將這個(gè)value放到數(shù)組的哪個(gè)位置锣笨。
tabAt(tab, i = (n - 1) & hash))就是定位到這個(gè)數(shù)組的位置，如果當(dāng)前這個(gè)位置的Node為null道批，則通過(guò)CAS方式的方法寫(xiě)入错英。所謂的CAS，即即compareAndSwap隆豹，執(zhí)行CAS操作的時(shí)候椭岩，將內(nèi)存位置的值與預(yù)期原值比較，如果相匹配，那么處理器會(huì)自動(dòng)將該位置值更新為新值判哥，否則献雅，處理器不做任何操作。
這里就是調(diào)用casTabAt方法來(lái)實(shí)現(xiàn)的塌计。
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);
}
casTabAt同樣是通過(guò)調(diào)用Unsafe類來(lái)實(shí)現(xiàn)的挺身，調(diào)用Unsafe的compareAndSwapObject來(lái)實(shí)現(xiàn)，其實(shí)如果仔細(xì)去追蹤這條線路夺荒，會(huì)發(fā)現(xiàn)其實(shí)最終調(diào)用的是cmpxchg這個(gè)CPU指令來(lái)實(shí)現(xiàn)的瞒渠，這是一個(gè)CPU的原子指令，能保證數(shù)據(jù)的一致性問(wèn)題技扼。
使用synchronized
當(dāng)頭結(jié)點(diǎn)不為null時(shí)伍玖，則使用該頭結(jié)點(diǎn)加鎖，這樣就能多線程去put hashCode相同的時(shí)候不會(huì)出現(xiàn)數(shù)據(jù)丟失的問(wèn)題剿吻。synchronized是互斥鎖窍箍，有且只有一個(gè)線程能夠拿到這個(gè)鎖，從而保證了put操作是線程安全的丽旅。
下面是ConcurrentHashMap的put操作的示意圖椰棘，圖片來(lái)自于ConcurrentHashMap源碼分析(JDK8)get/put/remove方法分析。
