前言
List、Set、HashMap作為Java中常用的集合，需要深入認(rèn)識其原理和特性。
本篇博客介紹常見的關(guān)于Java中線程安全的ConcurrentHashMap集合的面試問題，結(jié)合源碼分析題目背后的知識點(diǎn)。
關(guān)于List的博客文章如下：
- Java進(jìn)階（List）——面試時(shí)List常見問題解讀 & 結(jié)合源碼分析
關(guān)于的Set的博客文章如下：
- Java進(jìn)階（Set）——面試時(shí)Set常見問題解讀 & 結(jié)合源碼分析
關(guān)于HaseMap的博客文章如下：
- Java進(jìn)階（HashMap）——面試時(shí)HashMap常見問題解讀 & 結(jié)合源碼分析
其他關(guān)于 數(shù)據(jù)結(jié)構(gòu) 以及 多線程 的文章如下：
- 數(shù)據(jù)結(jié)構(gòu)與算法（Data Structures and Algorithm）——跟著Mark Allen Weiss用Java語言學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法
- 【合集】Java進(jìn)階——Java深入學(xué)習(xí)的筆記匯總 & 再論面向?qū)ο?、?shù)據(jù)結(jié)構(gòu)和算法、JVM底層、多線程、類加載 …
引出
1.從結(jié)構(gòu)上來說jdk7中，ConcurentHashMap是采用Segment段數(shù)組 + Entry數(shù)組 + 單鏈表結(jié)構(gòu)；
2.從結(jié)構(gòu)上來說jdk8中，ConcurentHashMap 與 HashMap的結(jié)構(gòu)是一模一樣的；
3.ConcurrentHashMap 不支持 key 或者 value 為 null ，避免歧義；
4.JDK1.7和1.8的區(qū)別：文章來源：http://www.zghlxwxcb.cn/news/detail-735860.html
- 數(shù)據(jù)結(jié)構(gòu)：取消了 Segment 分段鎖的數(shù)據(jù)結(jié)構(gòu)，取而代之的是數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)。
- 保證線程安全機(jī)制：JDK1.7 采用 Segment 的分段鎖機(jī)制實(shí)現(xiàn)線程安全，其中 Segment 繼承自 ReentrantLock 。JDK1.8 采用CAS+sizeCtl+synchronized保證線程安全。
- 鎖的粒度：JDK1.7 是對需要進(jìn)行數(shù)據(jù)操作的 Segment 加鎖，JDK1.8 調(diào)整為對每個(gè)數(shù)組元素加鎖（Node）。
- 鏈表轉(zhuǎn)化為紅黑樹：定位節(jié)點(diǎn)的 hash 算法簡化會(huì)帶來弊端，hash 沖突加劇，因此在鏈表節(jié)點(diǎn)數(shù)量到達(dá) 8（且數(shù)據(jù)總量大于等于 64）時(shí)，會(huì)將鏈表轉(zhuǎn)化為紅黑樹進(jìn)行存儲。
- 查詢時(shí)間復(fù)雜度：從 JDK1.7的遍歷鏈表O(n)， JDK1.8 變成遍歷紅黑樹O(logN)。
5.CAS是一種樂觀鎖機(jī)制，也被稱為無鎖機(jī)制文章來源地址http://www.zghlxwxcb.cn/news/detail-735860.html
核心：線程安全
ConcurentHashMap 在JDK1.7 和JDK1.8的區(qū)別？ConcurentHashMap 是怎么保證線程安全的？
- 從結(jié)構(gòu)上來說jdk7中，ConcurentHashMap是采用Segment段數(shù)組 + Entry數(shù)組 + 單鏈表結(jié)構(gòu)
分段，每個(gè)段里面都是hashmap，本質(zhì)還是以hashmap為單位上鎖
-
從結(jié)構(gòu)上來說jdk8中，ConcurentHashMap 與 HashMap的結(jié)構(gòu)是一模一樣的
-
從線程安全來說，jdk7中，ConcurentHashMap 內(nèi)部維護(hù)的是一個(gè)Segment(段)數(shù)組，Segment數(shù)組中每個(gè)元素又是一個(gè)HashEntry數(shù)組
Segment繼承了ReentrantLock這個(gè)類，所以segment自然就可以扮演鎖的角色，每一個(gè)segment相當(dāng)于一把鎖，這就是分段鎖
當(dāng)其他線程在需要進(jìn)行put操作時(shí)，需要先去獲取該對象的鎖資源，然而當(dāng)發(fā)現(xiàn)鎖資源被占用的時(shí)候，該線程會(huì)先去進(jìn)行節(jié)點(diǎn)的創(chuàng)建避免線程的空閑，這種思想也叫作預(yù)創(chuàng)建的思想
因?yàn)閟egment在初始化后是不會(huì)擴(kuò)容的，HashEntry數(shù)組是會(huì)擴(kuò)容的，與HashMap機(jī)制一樣，所以HashEntry是依靠于segment鎖來維護(hù)安全，所以HashEntry的擴(kuò)容也是線程安全的
1.什么時(shí)候初始化
jdk8中，ConcurentHashMap 因?yàn)榻Y(jié)構(gòu)變?yōu)榱?數(shù)組+鏈表+紅黑樹 結(jié)構(gòu)，所以維護(hù)線程安全的機(jī)制頁相對發(fā)生了一些變化，和HashMap同樣的，ConcurentHashMap 在put第一個(gè)元素時(shí)，才會(huì)執(zhí)行初始化
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode()); //根據(jù)KEY計(jì)算hash值
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(); //如果數(shù)組為null時(shí)，表示第一次put，則先進(jì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
}
...
2.如何保證初始化安全 sizeCtl
此處核心為sizeCtl
- sizeCtl的不同值表示不同的含義
- sizeCtl = 0 代表數(shù)組還未初始化
- sizeCtl > 0 如果數(shù)組已經(jīng)初始化，那么表示 擴(kuò)容閾值
- sizeCtl = -1 表示數(shù)組正在初始化
- sizeCtl < -1 表示數(shù)組正在擴(kuò)容，并且正在被多線程初始化中
sizeCtl 這個(gè)值，就保證了多線程并發(fā)狀態(tài)下，數(shù)組的初始化安全
核心為compareAndSwapInt，比較主存中數(shù)據(jù)和當(dāng)前內(nèi)存中數(shù)據(jù)是否相同，如果不同代表有別的線程正在操作這個(gè)數(shù)據(jù)那么就返回false，退回重新爭取時(shí)間片，此處就是保證并發(fā)時(shí)線程安全的核心。
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
//循環(huán)判斷數(shù)組是否為空/null
while ((tab = table) == null || tab.length == 0) {
//此處核心為sizeCtl
/*
sizeCtl的不同值表示不同的含義
sizeCtl = 0 代表數(shù)組還未初始化
sizeCtl > 0 如果數(shù)組已經(jīng)初始化，那么表示 擴(kuò)容閾值
sizeCtl = -1 表示數(shù)組正在初始化
sizeCtl < -1 表示數(shù)組正在擴(kuò)容，并且正在被多線程初始化中
*/
if ((sc = sizeCtl) < 0) //此處表示數(shù)組正在被某個(gè)線程初始化
Thread.yield(); // lost initialization race; just spin //釋放CPU時(shí)間片
//核心為compareAndSwapInt，比較主存中數(shù)據(jù)和當(dāng)前內(nèi)存中數(shù)據(jù)是否相同，如果不同代表有別的線程正在操作這個(gè)數(shù)據(jù)那么就返回false，退回重新爭取
//時(shí)間片
//此處就是保證并發(fā)時(shí)線程安全的核心
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY; //得到了數(shù)組長度是否為自己設(shè)置還是默認(rèn)16
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; //new出數(shù)組
table = tab = nt;//數(shù)組賦值
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
CAS + sizeCtl 保證了初始化數(shù)據(jù)的安全
3.putval方法存入元素，加鎖
數(shù)組的初始完成后，回到putval方法存入元素
真正存入元素時(shí)，是加入了synchronized來加鎖保證線程安全
CAS + sizeCtl 和 synchronized 兩者共同保證了ConcurentHashMap 的線程安全！
ConcurrentHashMap 不支持 key 或者 value 為 null 的原因？
- 假設(shè) ConcurrentHashMap 允許存放值為 null 的 value，這時(shí)有A、B兩個(gè)線程，線程A調(diào)用ConcurrentHashMap.get(key)方法，返回為 null ，我們不知道這個(gè) null 是沒有映射的 null ，還是存的值就是 null 。
- 假設(shè)此時(shí)，返回為 null 的真實(shí)情況是沒有找到對應(yīng)的 key。那么，我們可以用 ConcurrentHashMap.containsKey(key)來驗(yàn)證我們的假設(shè)是否成立，我們期望的結(jié)果是返回 false 。
- 但是在我們調(diào)用 ConcurrentHashMap.get(key)方法之后，containsKey方法之前，線程B執(zhí)行了ConcurrentHashMap.put(key, null)的操作。那么我們調(diào)用containsKey方法返回的就是 true 了，這就與我們的假設(shè)的真實(shí)情況不符合了，這就有了二義性。
JDK1.7 與 JDK1.8 中ConcurrentHashMap 的區(qū)別？
- 數(shù)據(jù)結(jié)構(gòu)：取消了 Segment 分段鎖的數(shù)據(jù)結(jié)構(gòu)，取而代之的是數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)。
- 保證線程安全機(jī)制：JDK1.7 采用 Segment 的分段鎖機(jī)制實(shí)現(xiàn)線程安全，其中 Segment 繼承自 ReentrantLock 。JDK1.8 采用CAS+sizeCtl+synchronized保證線程安全。
- 鎖的粒度：JDK1.7 是對需要進(jìn)行數(shù)據(jù)操作的 Segment 加鎖，JDK1.8 調(diào)整為對每個(gè)數(shù)組元素加鎖（Node）。
- 鏈表轉(zhuǎn)化為紅黑樹：定位節(jié)點(diǎn)的 hash 算法簡化會(huì)帶來弊端，hash 沖突加劇，因此在鏈表節(jié)點(diǎn)數(shù)量到達(dá) 8（且數(shù)據(jù)總量大于等于 64）時(shí)，會(huì)將鏈表轉(zhuǎn)化為紅黑樹進(jìn)行存儲。
- 查詢時(shí)間復(fù)雜度：從 JDK1.7的遍歷鏈表O(n)， JDK1.8 變成遍歷紅黑樹O(logN)。
涉及到的多線程知識
CAS是啥？
CAS(CompareAnd Swap)，就是比較并交換，是解決多線程情況下，解決使用鎖造成性能損耗問題的一種機(jī)制。
CAS是一種樂觀鎖機(jī)制，也被稱為無鎖機(jī)制。全稱: Compare-And-Swap。它是并發(fā)編程中的一種原子操作，通常用于多線程環(huán)境下實(shí)現(xiàn)同步和線程安全。CAS操作通過比較內(nèi)存中的值與期望值是否相等來確定是否執(zhí)行交換操作。如果相等，則執(zhí)行交換操作，否則不執(zhí)行。由于CAS是一種無鎖機(jī)制，因此它避免了使用傳統(tǒng)鎖所帶來的性能開銷和死鎖問題，提高了程序的并發(fā)性能。
CAS包含三個(gè)操作數(shù)：
- 變量內(nèi)存位置(V)
- 預(yù)期的變量原值(A)
- 變量的新值(B)
當(dāng)要對變量進(jìn)行修改時(shí)，先會(huì)將內(nèi)存位置的值與預(yù)期的變量原值進(jìn)行比較，如果一致則將內(nèi)存位置更新為新值，否則不做操作，無論哪種情況都會(huì)返回內(nèi)存位置當(dāng)前的值。
比較并交換是啥？
package com.tianju.test2;
import java.util.concurrent.atomic.AtomicInteger;
public class CASTest {
public static void main(String[] args) {
AtomicInteger atomicInteger = new AtomicInteger(5);
System.out.println(atomicInteger.compareAndSet(5,2019));
System.out.println(atomicInteger);
System.out.println(atomicInteger.compareAndSet(5,2020));
System.out.println(atomicInteger.compareAndSet(2019,2020));
System.out.println(atomicInteger);
System.out.println(atomicInteger.compareAndSet(2020,5));
System.out.println(atomicInteger);
}
}
CAS的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
CAS是一種無鎖機(jī)制，因此它避免了使用傳統(tǒng)鎖所帶來的性能開銷和死鎖問題，提高了程序的并發(fā)性能。
缺點(diǎn)：
CAS 有自旋鎖，如果不成功會(huì)一直循環(huán)，可能會(huì)給 cpu 帶來很大開銷；
問題就是可能會(huì)造成 “ABA”；
解決方案：解決的思路就是引入類似樂觀鎖的版本號控制，不止比較預(yù)期值和內(nèi)存位置的值，還要比較版本號是否正確。
AtomicStampedReference atomicStampedReference = new AtomicStampedReference(5, 1);
package com.tianju.test2;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicStampedReference;
public class CASTest {
public static void main(String[] args) {
AtomicInteger atomicInteger = new AtomicInteger(5);
System.out.println(atomicInteger.compareAndSet(5,2019));
System.out.println(atomicInteger);
System.out.println(atomicInteger.compareAndSet(5,2020));
System.out.println(atomicInteger.compareAndSet(2019,2020));
System.out.println(atomicInteger);
System.out.println(atomicInteger.compareAndSet(2020,5));
System.out.println(atomicInteger);
System.out.println(" ########################################## ");
AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(5, 1);
boolean flag1 = atomicStampedReference.compareAndSet(atomicStampedReference.getReference(), 2019,
atomicStampedReference.getStamp(), 2);
System.out.println("從5修改為2019："+flag1);
System.out.println(atomicStampedReference.getReference());
boolean flag2 = atomicStampedReference.compareAndSet(atomicStampedReference.getReference(), 2020,
atomicStampedReference.getStamp(), 3);
System.out.println("從2019修改為2020："+flag2);
System.out.println(atomicStampedReference.getReference());
boolean flag3 = atomicStampedReference.compareAndSet(2020, 5, 3, 4);
System.out.println("從2020修改回5："+flag3);
System.out.println(atomicStampedReference.getReference());
}
}
什么是CAS機(jī)制compareAndSwapInt
CAS是Java中Unsafe類里面的方法，它的全稱是CompareAndSwap，比較并交換的意思。它的主要功能是能夠保證在多線程環(huán)境下，對于共享變量的修改的原子性。
如下，成員變量state，默認(rèn)值是0，定義了一個(gè)方法doSomething()，這個(gè)方法的邏輯是判斷state是否為0，如果為0就修改成1。這個(gè)邏輯看起來沒有任何問題，但是在多線程環(huán)境下，會(huì)存在原子性的問題，因?yàn)檫@里是一個(gè)典型的，Read-Write的操作。
一般情況下，我們會(huì)在doSomething()這個(gè)方法上加同步鎖來解決原子性問題。
package com.tianju.test2;
public class Demo1 {
private int state = 0;
public void doSomething(){
if (state==0){
state=1;
}
}
}
但是，加同步鎖，會(huì)帶來性能上的損耗，所以，對于這類場景，我們就可以使用CAS機(jī)制來進(jìn)行優(yōu)化
package com.tianju.test2;
import sun.misc.Unsafe;
public class Demo2 {
private volatile int state = 0;
private static final Unsafe UNSAFE = Unsafe.getUnsafe();
private static final long stateOffset;
static {
try {
stateOffset = UNSAFE.objectFieldOffset(
Demo2.class.getDeclaredField("state")
);
} catch (NoSuchFieldException e) {
throw new RuntimeException(e);
}
}
public void doSomething(){
if (UNSAFE.compareAndSwapInt(this,stateOffset,0,1)){
state=1;
}
}
}
在doSomething()方法中，我們調(diào)用了unsafe類中的compareAndSwapInt()方法來達(dá)到同樣的目的，這個(gè)方法有四個(gè)參數(shù)，分別是：
當(dāng)前對象實(shí)例、成員變量state在內(nèi)存地址中的偏移量、預(yù)期值0、期望更改之后的值1。
CAS機(jī)制會(huì)比較state內(nèi)存地址偏移量對應(yīng)的值和傳入的預(yù)期值0是否相等，如果相等，就直接修改內(nèi)存地址中state的值為1。否則，返回false，表示修改失敗，而這個(gè)過程是原子的，不會(huì)存在線程安全問題。
CompareAndSwap是一個(gè)native方法，實(shí)際上它最終還是會(huì)面臨同樣的問題，就是先從內(nèi)存地址中讀取state的值，然后去比較，最后再修改。
這個(gè)過程不管是在什么層面上實(shí)現(xiàn)，都會(huì)存在原子性問題。所以，CompareAndSwap的底層實(shí)現(xiàn)中，在多核CPU環(huán)境下，會(huì)增加一個(gè)Lock指令對緩存或者總線加鎖，從而保證比較并替換這兩個(gè)指令的原子性。
CAS主要用在并發(fā)場景中，比較典型的使用場景有兩個(gè)：
- 第一個(gè)是J.U.C里面Atomic的原子實(shí)現(xiàn)，比如AtomicInteger，AtomicLong。
- 第二個(gè)是實(shí)現(xiàn)多線程對共享資源競爭的互斥性質(zhì)，比如在AQS、ConcurrentHashMap、ConcurrentLinkedQueue等都有用到。
總結(jié)
1.從結(jié)構(gòu)上來說jdk7中，ConcurentHashMap是采用Segment段數(shù)組 + Entry數(shù)組 + 單鏈表結(jié)構(gòu)；
2.從結(jié)構(gòu)上來說jdk8中，ConcurentHashMap 與 HashMap的結(jié)構(gòu)是一模一樣的；
3.ConcurrentHashMap 不支持 key 或者 value 為 null ，避免歧義；
4.JDK1.7和1.8的區(qū)別：
- 數(shù)據(jù)結(jié)構(gòu)：取消了 Segment 分段鎖的數(shù)據(jù)結(jié)構(gòu)，取而代之的是數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)。
- 保證線程安全機(jī)制：JDK1.7 采用 Segment 的分段鎖機(jī)制實(shí)現(xiàn)線程安全，其中 Segment 繼承自 ReentrantLock 。JDK1.8 采用CAS+sizeCtl+synchronized保證線程安全。
- 鎖的粒度：JDK1.7 是對需要進(jìn)行數(shù)據(jù)操作的 Segment 加鎖，JDK1.8 調(diào)整為對每個(gè)數(shù)組元素加鎖（Node）。
- 鏈表轉(zhuǎn)化為紅黑樹：定位節(jié)點(diǎn)的 hash 算法簡化會(huì)帶來弊端，hash 沖突加劇，因此在鏈表節(jié)點(diǎn)數(shù)量到達(dá) 8（且數(shù)據(jù)總量大于等于 64）時(shí)，會(huì)將鏈表轉(zhuǎn)化為紅黑樹進(jìn)行存儲。
- 查詢時(shí)間復(fù)雜度：從 JDK1.7的遍歷鏈表O(n)， JDK1.8 變成遍歷紅黑樹O(logN)。
5.CAS是一種樂觀鎖機(jī)制，也被稱為無鎖機(jī)制
到了這里，關(guān)于Java進(jìn)階（ConcurrentHashMap）——面試時(shí)ConcurrentHashMap常見問題解讀 & 結(jié)合源碼分析 & 多線程CAS比較并交換 初識的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
