1.簡(jiǎn)介
HashMap是Java程序員使用頻率最高的用于映射(鍵值對(duì))處理的數(shù)據(jù)類型。但HashMap不是線程安全的，即在多線程并發(fā)操作HashMap時(shí)可能會(huì)發(fā)生意向不到的結(jié)果。想在并發(fā)下操作Map,主要有以下方法：
第一種：使用Hashtable線程安全類（現(xiàn)在已經(jīng)被高效ConcurrentHashMap替代）
第二種：使用Collections.synchronizedMap方法，對(duì)方法進(jìn)行加同步鎖；
第三種：使用并發(fā)包中的ConcurrentHashMap類；
第一種方法是通過(guò)對(duì)Hashtable中的方法添加synchronized同步鎖來(lái)保證線程安全的，第二種是通過(guò)對(duì)對(duì)象加synchronized鎖來(lái)保證線程安全，相當(dāng)于給整個(gè)哈希表加了一把大鎖，多線程訪問(wèn)時(shí)候，只要有一個(gè)線程訪問(wèn)或操作該對(duì)象，那其他線程只能阻塞等待需要的鎖被釋放，在競(jìng)爭(zhēng)激烈的多線程場(chǎng)景中性能就會(huì)非常差。前兩種方法在多線程操作時(shí)效率都比較低下，所以不建議采用。ConcurrentHashMap是線程安全且高效的HashMap，JDK7中ConcurrentHashMap采用鎖分段技術(shù)，首先將數(shù)據(jù)分成一段段的存儲(chǔ)，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段數(shù)據(jù)的時(shí)候，其他段的數(shù)據(jù)也能被其他線程方法，這樣我們就不用像前兩種方法直接對(duì)整個(gè)HashMap加鎖，采用鎖分段技術(shù)來(lái)提升性能。JDK7中ConcurrentHashMap結(jié)構(gòu)如下圖所示：
其中Segment是一種可重入鎖（ReentrantLock），在JDK7的ConcurrentHashMap中扮演鎖的角色。Segment結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)。
JDK8中對(duì)HashMap做了改造，當(dāng)沖突鏈表長(zhǎng)度大于8時(shí)，會(huì)將鏈表轉(zhuǎn)變成紅黑樹結(jié)構(gòu)，JDK8中ConcurrentHashMap類取消了Segment分段鎖，采用CAS+sychronized來(lái)保證并發(fā)安全，數(shù)據(jù)結(jié)構(gòu)跟JDK8中的HashMap結(jié)構(gòu)類似，都是數(shù)組加鏈表（當(dāng)鏈表長(zhǎng)度大于8時(shí)，鏈表結(jié)構(gòu)轉(zhuǎn)為紅黑樹）結(jié)構(gòu)。JDK8中的、ConcurrentHashMapsynchronized只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點(diǎn)，只要節(jié)點(diǎn)hash不沖突，就不會(huì)產(chǎn)生并發(fā)，相比 JDK7中的ConcurrentHashMap效率又提升了N倍。JDK8中ConcurrentHashMap的結(jié)構(gòu)如下所示：
誤區(qū)：印象中一直以為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ī)制了。
2.JDK7中ConcurrentHashMap實(shí)現(xiàn)同步的方式
Segment繼承自ReentrantLock，所以我們可以很方便的對(duì)每一個(gè)Segment上鎖。
讀操作：獲取Key所在的Segment時(shí)，需要保證可見(jiàn)性，具體實(shí)現(xiàn)上可以使用volatile關(guān)鍵字，也可使用鎖。但使用鎖開(kāi)銷太大，而使用volatile時(shí)每次寫操作都會(huì)讓所有CPU內(nèi)緩存無(wú)效，也有一定開(kāi)銷。ConcurrentHashMap使用如下方法保證可見(jiàn)性，取得最新的Segment。
Segment<K,V> s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)；
獲取Segment中的HashEntry時(shí)也使用了類似方法：
HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE)
寫操作：并不要求同時(shí)獲取所有Segment的鎖，因?yàn)槟菢酉喈?dāng)于鎖住了整個(gè)Map。它會(huì)先獲取該Key-Value對(duì)所在的Segment的鎖，獲取成功后就可以像操作一個(gè)普通的HashMap一樣操作該Segment，并保證該Segment的安全性。同時(shí)由于其它Segment的鎖并未被獲取，因此理論上可支持concurrencyLevel（等于Segment的個(gè)數(shù)）個(gè)線程安全的并發(fā)讀寫。獲取鎖時(shí)，并不直接使用lock來(lái)獲取，因?yàn)樵摲椒ǐ@取鎖失敗時(shí)會(huì)掛起（參考可重入鎖）。事實(shí)上，它使用了自旋鎖，如果tryLock獲取鎖失敗，說(shuō)明鎖被其它線程占用，此時(shí)通過(guò)循環(huán)再次以tryLock的方式申請(qǐng)鎖。如果在循環(huán)過(guò)程中該Key所對(duì)應(yīng)的鏈表頭被修改，則重置retry次數(shù)。如果retry次數(shù)超過(guò)一定值，則使用lock方法申請(qǐng)鎖。
3.JDK8中ConcurrentHashMap實(shí)現(xiàn)同步的方式
JDK8中ConcurrentHashMap保證線程安全主要有三個(gè)地方。
（1）使用volatile保證當(dāng)Node中的值變化時(shí)對(duì)于其他線程是可見(jiàn)的，以此來(lái)保證讀安全
（2）寫安全（頭結(jié)點(diǎn)不為null）：使用table數(shù)組的頭結(jié)點(diǎn)作為synchronized的鎖來(lái)保證寫操作的安全。
（3）寫安全（頭結(jié)點(diǎn)為null）：使用CAS操作來(lái)保證數(shù)據(jù)能正確的寫入。
使用volatile保證讀安全
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中的val和next都被volatile關(guān)鍵字修飾。也就是說(shuō)，我們改動(dòng)val的值或者next的值對(duì)于其他線程是可見(jiàn)的，因?yàn)関olatile關(guān)鍵字，會(huì)在讀指令前插入讀屏障，可以讓高速緩存中的數(shù)據(jù)失效，重新從主內(nèi)存加載數(shù)據(jù)。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寫的方式往數(shù)組寫入元素，這樣能保證修改后能對(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);
}
寫安全（頭結(jié)點(diǎn)為null）
當(dāng)table數(shù)組的頭結(jié)點(diǎn)為null時(shí)，使用for循環(huán)+CAS來(lái)保證線程安全，頭結(jié)點(diǎn)為null時(shí)，可能多個(gè)線程并發(fā)寫入頭結(jié)點(diǎn)，所以需要保證線程安全。當(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方式的方法寫入。所謂的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)題。
Java原子類的自增操作，也是通過(guò)for循環(huán)+CAS操作的方式實(shí)現(xiàn)的
// AtomicInteger 類的原子自增操作
public final int getAndIncrement() {
for (;;) {
//獲取value
int current = get();
int next = current + 1;
//value值沒(méi)有變，說(shuō)明其他線程沒(méi)有自增過(guò),將value設(shè)置為next
if (compareAndSet(current, next))
return current;
//否則說(shuō)明value值已經(jīng)改變，回到循環(huán)開(kāi)始處，重新獲取value。
}
}
寫安全（頭結(jié)點(diǎn)不為bull）
當(dāng)頭結(jié)點(diǎn)不為null時(shí)，對(duì)頭結(jié)點(diǎn)使用sychronized加鎖來(lái)保證線程安全：當(dāng)頭結(jié)點(diǎn)不為null時(shí)，則使用該頭結(jié)點(diǎn)加鎖，這樣就能多線程去put hashCode相同的時(shí)候不會(huì)出現(xiàn)數(shù)據(jù)丟失的問(wèn)題。synchronized是互斥鎖，有且只有一個(gè)線程能夠拿到這個(gè)鎖，從而保證了put操作是線程安全的。
寫安全總結(jié)：頭結(jié)點(diǎn)為null使用for循環(huán)+cas保證線程安全，頭結(jié)點(diǎn)不為null使用sychronized保證線程安全，如下圖所示：
4.JDK7與JDK8主要區(qū)別
（1）更小的鎖粒度
JDK8中摒棄了Segment鎖，直接將hash桶的頭結(jié)點(diǎn)當(dāng)做鎖。舊版本的一個(gè)segment鎖，保護(hù)了多個(gè)hash桶，而JDK8版本的一個(gè)鎖只保護(hù)一個(gè)hash桶，由于鎖的粒度變小了，寫操作的并發(fā)性得到了極大的提升。 可以參考下圖：
（2）更高效的擴(kuò)容
更多的擴(kuò)容線程：擴(kuò)容時(shí)，需要鎖的保護(hù)。因此：舊版本最多可以同時(shí)擴(kuò)容的線程數(shù)是segment鎖的個(gè)數(shù)。而JDK8的版本，理論上最多可以同時(shí)擴(kuò)容的線程數(shù)是：hash桶的個(gè)數(shù)。擴(kuò)容期間，依然保證較高的并發(fā)度，舊版本的segment鎖，鎖定范圍太大，導(dǎo)致擴(kuò)容期間，寫并發(fā)度，嚴(yán)重下降。而新版本的采用更加細(xì)粒度的hash桶級(jí)別鎖，擴(kuò)容期間，依然可以保證寫操作的并發(fā)度。如下圖所示：
5.相關(guān)問(wèn)題
（1）談?wù)勀憷斫獾?HashMap，講講其中的 get put 過(guò)程。
（2）JDK 做了什么優(yōu)化？
（3）是線程安全的嘛？
（4）不安全會(huì)導(dǎo)致哪些問(wèn)題？
（5）如何解決？有沒(méi)有線程安全的并發(fā)容器？
（6）ConcurrentHashMap 是如何實(shí)現(xiàn)的？ JDK7、JDK8 實(shí)現(xiàn)有何不同？為什么這么做？
（7）HashMap如何保證數(shù)據(jù)有序存放，LRU算法如何實(shí)現(xiàn)？
搞明白以上幾個(gè)問(wèn)題以后，對(duì)HashMap、LinkedHashMap、ConcurrentHashMap也就熟悉了。
參考資料及相關(guān)好文
美團(tuán)技術(shù)文章Java 8系列之重新認(rèn)識(shí)HashMap
講述 ConcurrentHashMap 線程安全最牛逼的一篇文章
ConcurrentHashMap是如何保證線程安全的
從ConcurrentHashMap的演進(jìn)看Java多線程核心技術(shù)
ConcurrentHashMap源碼分析（JDK8）
徹頭徹尾理解 LinkedHashMap
《Java并發(fā)編程的藝術(shù)》
