全網(wǎng)最細(xì) | 21張圖帶你領(lǐng)略集合的線程不安全
來(lái)源 | 悟空聊架構(gòu)（ID：PassJava666）
本篇主要內(nèi)容如下：
本篇所有示例代碼已更新到 我的Github
本篇文章已收納到我的Java在線文檔
一、線程不安全之ArrayList
集合框架有Map和Collection兩大類，Collection下面有List、Set、Queue。List下面有ArrayList、Vector、LinkedList。如下圖所示：
JUC并發(fā)包下的集合類Collections有Queue、CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentMap
我們先來(lái)看看ArrayList。
1.1、ArrayList的底層初始化操作
首先我們來(lái)復(fù)習(xí)下ArrayList的使用，下面是初始化一個(gè)ArrayList，數(shù)組存放的是Integer類型的值。
new?ArrayList();
那么底層做了什么操作呢？
1.2、ArrayList的底層原理
1.2.1 初始化數(shù)組
/**
?*?Constructs?an?empty?list?with?an?initial?capacity?of?ten.
?*/
public?ArrayList()?{
????this.elementData?=?DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
創(chuàng)建了一個(gè)空數(shù)組，容量為0，根據(jù)官方的英文注釋，這里容量應(yīng)該為10，但其實(shí)是0，后續(xù)會(huì)講到為什么不是10。
1.2.1 ArrayList的add操作
public?boolean?add(E?e)?{
????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!
????elementData[size++]?=?e;
????return?true;
}
重點(diǎn)是這一步：elementData[size++] = e; size++和elementData[xx]=e，這兩個(gè)操作都不是原子操作（不可分割的一個(gè)或一系列操作，要么都成功執(zhí)行，要么都不執(zhí)行）。
1.2.2 ArrayList擴(kuò)容源碼解析
（1）執(zhí)行add操作時(shí)，會(huì)先確認(rèn)是否超過(guò)數(shù)組大小
ensureCapacityInternal(size?+?1);
（2）計(jì)算數(shù)組的當(dāng)前容量calculateCapacity
private?void?ensureCapacityInternal(int?minCapacity)?{
????ensureExplicitCapacity(calculateCapacity(elementData,?minCapacity));
}
minCapacity : 值為1
elementData：代表當(dāng)前數(shù)組
我們先看ensureCapacityInternal調(diào)用的ensureCapacityInternal方法
calculateCapacity(elementData,?minCapacity)
calculateCapacity方法如下：
private?static?int?calculateCapacity(Object[]?elementData,?int?minCapacity)?{
????if?(elementData?==?DEFAULTCAPACITY_EMPTY_ELEMENTDATA)?{
????????return?Math.max(DEFAULT_CAPACITY,?minCapacity);
????}
????return?minCapacity;
}
elementData：代表當(dāng)前數(shù)組，添加第一個(gè)元素時(shí)，elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA（空數(shù)組）
minCapacity：等于1
DEFAULT_CAPACITY：等于10
返回 Math.max(DEFAULT_CAPACITY, minCapacity) = 10
小結(jié)：所以第一次添加元素時(shí)，計(jì)算數(shù)組的大小為10
（3）確定當(dāng)前容量ensureExplicitCapacity
minCapacity = 10
elementData.length=0
小結(jié)：因minCapacity > elementData.length，所以進(jìn)行第一次擴(kuò)容，調(diào)用grow()方法從0擴(kuò)大到10。
（4）調(diào)用grow方法
oldCapacity=0，newCapacity=10。
然后執(zhí)行 elementData = Arrays.copyOf(elementData, newCapacity);
將當(dāng)前數(shù)組和容量大小進(jìn)行數(shù)組拷貝操作，賦值給elementData。數(shù)組的容量設(shè)置為10
elementData的值和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的值將會(huì)不一樣。
（5）然后將元素賦值給數(shù)組第一個(gè)元素，且size自增1
elementData[size++]?=?e;
（6）添加第二個(gè)元素時(shí)，傳給ensureCapacityInternal的是2
ensureCapacityInternal(size?+?1)
size=1，size+1=2
（7）第二次添加元素時(shí)，執(zhí)行calculateCapacity
elementData的值和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的值不相等，所以直接返回2
（8）第二次添加元素時(shí)，執(zhí)行ensureExplicitCapacity
因minCapacity等于2，小于當(dāng)前數(shù)組的長(zhǎng)度10，所以不進(jìn)行擴(kuò)容，不執(zhí)行g(shù)row方法。
（9）將第二個(gè)元素添加到數(shù)組中，size自增1
elementData[size++]?=?e
（10）當(dāng)添加第11個(gè)元素時(shí)調(diào)用grow方法進(jìn)行擴(kuò)容
minCapacity=11， elementData.length=10，調(diào)用grow方法。
（11）擴(kuò)容1.5倍
int?newCapacity?=?oldCapacity?+?(oldCapacity?>>?1);
oldCapacity=10，先換算成二級(jí)制1010，然后右移一位，變成0101，對(duì)應(yīng)十進(jìn)制5，所以newCapacity=10+5=15，擴(kuò)容1.5倍后是15。
（12）小結(jié)
-
1.ArrayList初始化為一個(gè) 空數(shù)組 -
2.ArrayList的Add操作不是線程安全的 -
3.ArrayList添加第一個(gè)元素時(shí)，數(shù)組的容量設(shè)置為 10 -
4.當(dāng)ArrayList數(shù)組超過(guò)當(dāng)前容量時(shí)，擴(kuò)容至 1.5倍（遇到計(jì)算結(jié)果為小數(shù)的，向下取整），第一次擴(kuò)容后，容量為15，第二次擴(kuò)容至22... -
5.ArrayList在第一次和擴(kuò)容后都會(huì)對(duì)數(shù)組進(jìn)行拷貝，調(diào)用 Arrays.copyOf方法。
1.3、ArrayList單線程環(huán)境是否安全？
場(chǎng)景：
我們通過(guò)一個(gè)添加積木的例子來(lái)說(shuō)明單線程下ArrayList是線程安全的。
將 積木 三角形A、四邊形B、五邊形C、六邊形D、五角星E依次添加到一個(gè)盒子中，盒子中共有5個(gè)方格，每一個(gè)方格可以放一個(gè)積木。
代碼實(shí)現(xiàn)：
（1）這次我們用新的積木類BuildingBlockWithName
這個(gè)積木類可以傳形狀shape和名字name
/**
?*?積木類
?*?@author:?悟空聊架構(gòu)
?*?@create:?2020-08-27
?*/
class?BuildingBlockWithName?{
????String?shape;
????String?name;
????public?BuildingBlockWithName(String?shape,?String?name)?{
????????this.shape?=?shape;
????????this.name?=?name;
????}
????@Override
????public?String?toString()?{
????????return?"BuildingBlockWithName{"?+?"shape='"?+?shape?+?",name="?+?name?+'}';
????}
}
（2）初始化一個(gè)ArrayList
ArrayList?arrayList?=?new?ArrayList<>();
（3）依次添加三角形A、四邊形B、五邊形C、六邊形D、五角星E
arrayList.add(new?BuildingBlockWithName("三角形",?"A"));
arrayList.add(new?BuildingBlockWithName("四邊形",?"B"));
arrayList.add(new?BuildingBlockWithName("五邊形",?"C"));
arrayList.add(new?BuildingBlockWithName("六邊形",?"D"));
arrayList.add(new?BuildingBlockWithName("五角星",?"E"));
（4）驗(yàn)證arrayList中元素的內(nèi)容和順序是否和添加的一致
BuildingBlockWithName{shape='三角形,name=A}
BuildingBlockWithName{shape='四邊形,name=B}
BuildingBlockWithName{shape='五邊形,name=C}
BuildingBlockWithName{shape='六邊形,name=D}
BuildingBlockWithName{shape='五角星,name=E}
我們看到結(jié)果確實(shí)是一致的。
小結(jié)： 單線程環(huán)境中，ArrayList是線程安全的。
1.4、多線程下ArrayList是不安全的
場(chǎng)景如下： 20個(gè)線程隨機(jī)往ArrayList添加一個(gè)任意形狀的積木。
（1）代碼實(shí)現(xiàn)：20個(gè)線程往數(shù)組中隨機(jī)存放一個(gè)積木。
（2）打印結(jié)果：程序開(kāi)始運(yùn)行后，每個(gè)線程只存放一個(gè)隨機(jī)的積木。
數(shù)組中會(huì)不斷存放積木，多個(gè)線程會(huì)爭(zhēng)搶數(shù)組的存放資格，在存放過(guò)程中，會(huì)拋出一個(gè)異常: ConcurrentModificationException（并行修改異常）
Exception?in?thread?"10"?Exception?in?thread?"13"?java.util.ConcurrentModificationException
這個(gè)就是常見(jiàn)的并發(fā)異常：java.util.ConcurrentModificationException
1.5 那如何解決ArrayList線程不安全問(wèn)題呢？
有如下方案：
-
1.用Vector代替ArrayList -
2.用Collections.synchronized(new ArrayList<>()) -
3.CopyOnWriteArrayList
1.6 Vector是保證線程安全的？
下面就來(lái)分析vector的源碼。
1.6.1 初始化Vector
初始化容量為10
public?Vector()?{
????this(10);
}
1.6.2 Add操作是線程安全的
Add方法加了synchronized，來(lái)保證add操作是線程安全的（保證可見(jiàn)性、原子性、有序性），對(duì)這幾個(gè)概念有不懂的可以看下之前的寫(xiě)的文章-》 反制面試官 | 14張?jiān)韴D | 再也不怕被問(wèn) volatile!
1.6.3 Vector擴(kuò)容至2倍
int?newCapacity?=?oldCapacity?+?((capacityIncrement?>?0)???capacityIncrement?:?oldCapacity);
注意： capacityIncrement 在初始化的時(shí)候可以傳值，不傳則默認(rèn)為0。如果傳了，則第一次擴(kuò)容時(shí)為設(shè)置的oldCapacity+capacityIncrement，第二次擴(kuò)容時(shí)擴(kuò)大1倍。
缺點(diǎn)： 雖然保證了線程安全，但因?yàn)榧恿伺懦怄isynchronized，會(huì)造成阻塞，所以性能降低。
1.6.4 用積木模擬Vector的add操作
當(dāng)往vector存放元素時(shí)，給盒子加了一個(gè)鎖，只有一個(gè)人可以存放積木，放完后，釋放鎖，放第二元素時(shí)，再進(jìn)行加鎖，依次往復(fù)進(jìn)行。
1.7 使用Collections.synchronizedList保證線程安全
我們可以使用Collections.synchronizedList方法來(lái)封裝一個(gè)ArrayList。
List為什么這樣封裝后，就是線程安全的？
源碼解析： 因?yàn)镃ollections.synchronizedList封裝后的list，list的所有操作方法都是帶synchronized關(guān)鍵字的（除iterator()之外），相當(dāng)于所有操作都會(huì)進(jìn)行加鎖，所以使用它是線程安全的（除迭代數(shù)組之外）。
注意： 當(dāng)?shù)鷶?shù)組時(shí)，需要手動(dòng)做同步。官方示例如下：
synchronized?(list)?{
?????Iterator?i?=?list.iterator();?//?Must?be?in?synchronized?block
?????while?(i.hasNext())
?????????foo(i.next());
}
1.8 使用CopyOnWriteArrayList保證線程安全
1.8.1 CopyOnWriteArrayList思想
-
Copy on write：寫(xiě)時(shí)復(fù)制，一種讀寫(xiě)分離的思想。 -
寫(xiě)操作：添加元素時(shí)，不直接往當(dāng)前容器添加，而是先拷貝一份數(shù)組，在新的數(shù)組中添加元素后，在將原容器的引用指向新的容器。因?yàn)閿?shù)組時(shí)用volatile關(guān)鍵字修飾的，所以當(dāng)array重新賦值后，其他線程可以立即知道（volatile的可見(jiàn)性） -
讀操作：讀取數(shù)組時(shí)，讀老的數(shù)組，不需要加鎖。 -
讀寫(xiě)分離：寫(xiě)操作是copy了一份新的數(shù)組進(jìn)行寫(xiě)，讀操作是讀老的數(shù)組，所以是讀寫(xiě)分離。
1.8.2 使用方式
CopyOnWriteArrayList?arrayList?=?new?CopyOnWriteArrayList<>();
1.8.3 底層源碼分析
add的流程：
-
先定義了一個(gè)可重入鎖 ReentrantLock -
添加元素前，先獲取鎖 lock.lock() -
添加元素時(shí)，先拷貝當(dāng)前數(shù)組 Arrays.copyOf -
添加元素時(shí)，擴(kuò)容+1（ len + 1） -
添加元素后，將數(shù)組引用指向新加了元素后的數(shù)組 setArray(newElements)
為什么數(shù)組重新賦值后，其他線程可以立即知道？
因?yàn)檫@里的數(shù)組是用volatile修飾的，哇，又是volatile，這個(gè)關(guān)鍵字真妙^_^
?private?transient?volatile?Object[]?array;
1.8.4 ReentrantLock 和synchronized的區(qū)別
劃重點(diǎn)
相同點(diǎn)：
-
1.都是用來(lái)協(xié)調(diào)多線程對(duì)共享對(duì)象、變量的訪問(wèn) -
2.都是可重入鎖，同一線程可以多次獲得同一個(gè)鎖 -
3.都保證了可見(jiàn)性和互斥性
不同點(diǎn)：
-
1.ReentrantLock 顯示的獲得、釋放鎖， synchronized 隱式獲得釋放鎖 -
2.ReentrantLock 可響應(yīng)中斷， synchronized 是不可以響應(yīng)中斷的，為處理鎖的不可用性提供了更高的靈活性 -
3.ReentrantLock 是 API 級(jí)別的， synchronized 是 JVM 級(jí)別的 -
4.ReentrantLock 可以實(shí)現(xiàn)公平鎖、非公平鎖 -
5.ReentrantLock 通過(guò) Condition 可以綁定多個(gè)條件 -
6.底層實(shí)現(xiàn)不一樣， synchronized 是同步阻塞，使用的是悲觀并發(fā)策略， lock 是同步非阻塞，采用的是樂(lè)觀并發(fā)策略
1.8.5 Lock和synchronized的區(qū)別
-
1.Lock需要手動(dòng)獲取鎖和釋放鎖。就好比自動(dòng)擋和手動(dòng)擋的區(qū)別 -
1.Lock 是一個(gè)接口，而 synchronized 是 Java 中的關(guān)鍵字， synchronized 是內(nèi)置的語(yǔ)言實(shí)現(xiàn)。 -
2.synchronized 在發(fā)生異常時(shí)，會(huì)自動(dòng)釋放線程占有的鎖，因此不會(huì)導(dǎo)致死鎖現(xiàn)象發(fā)生；而 Lock 在發(fā)生異常時(shí)，如果沒(méi)有主動(dòng)通過(guò) unLock()去釋放鎖，則很可能造成死鎖現(xiàn)象，因此使用 Lock 時(shí)需要在 finally 塊中釋放鎖。 -
3.Lock 可以讓等待鎖的線程響應(yīng)中斷，而 synchronized 卻不行，使用 synchronized 時(shí)，等待的線程會(huì)一直等待下去，不能夠響應(yīng)中斷。 -
4.通過(guò) Lock 可以知道有沒(méi)有成功獲取鎖，而 synchronized 卻無(wú)法辦到。 -
5.Lock 可以通過(guò)實(shí)現(xiàn)讀寫(xiě)鎖提高多個(gè)線程進(jìn)行讀操作的效率。
二、線程不安全之HashSet
有了前面大篇幅的講解ArrayList的線程不安全，以及如何使用其他方式來(lái)保證線程安全，現(xiàn)在講HashSet應(yīng)該更容易理解一些。
2.1 HashSet的用法
用法如下：
Set?Set?=?new?HashSet<>();
set.add("a");
初始容量=10，負(fù)載因子=0.75（當(dāng)元素個(gè)數(shù)達(dá)到容量的75%，啟動(dòng)擴(kuò)容）
2.2 HashSet的底層原理
public?HashSet()?{
????map?=?new?HashMap<>();
}
底層用的還是HashMap()。
考點(diǎn)： 為什么HashSet的add操作只用傳一個(gè)參數(shù)（value)，而HashMap需要傳兩個(gè)參數(shù)（key和value)
2.3 HashSet的add操作
private?static?final?Object?PRESENT?=?new?Object();
public?boolean?add(E?e)?{
????return?map.put(e,?PRESENT)==null;
}
考點(diǎn)回答： 因?yàn)镠ashSet的add操作中，key等于傳的value值，而value是PRESENT，PRESENT是new Object();，所以傳給map的是 key=e, ?value=new Object。Hash只關(guān)心key，不考慮value。
為什么HashSet不安全： 底層add操作不保證可見(jiàn)性、原子性。所以不是線程安全的。
2.4 如何保證線程安全
-
1.使用Collections.synchronizedSet
Set?set?=?Collections.synchronizedSet(new?HashSet<>()); -
2.使用CopyOnWriteArraySet
CopyOnWriteArraySet?set?=?new?CopyOnWriteArraySet<>();
2.5 CopyOnWriteArraySet的底層還是使用的是CopyOnWriteArrayList
public?CopyOnWriteArraySet()?{
????al?=?new?CopyOnWriteArrayList();
}
三、線程不安全之HashMap
3.1 HashMap的使用
同理，HashMap和HashSet一樣，在多線程環(huán)境下也是線程不安全的。
Map?map?=?new?HashMap<>();
map.put("A",?new?BuildingBlockWithName("三角形",?"A"));
3.2 HashMap線程不安全解決方案：
-
1.Collections.synchronizedMap
Map?map2?=?Collections.synchronizedMap(new?HashMap<>());
-
2.ConcurrentHashMap
ConcurrentHashMap?set3?=?new?ConcurrentHashMap<>();
3.3 ConcurrentHashMap原理
ConcurrentHashMap，它內(nèi)部細(xì)分了若干個(gè)小的 HashMap，稱之為段(Segment)。默認(rèn)情況下一個(gè) ConcurrentHashMap 被進(jìn)一步細(xì)分為 16 個(gè)段，既就是鎖的并發(fā)度。如果需要在 ConcurrentHashMap 中添加一個(gè)新的表項(xiàng)，并不是將整個(gè) HashMap 加鎖，而是首先根據(jù) hashcode 得到該表項(xiàng)應(yīng)該存放在哪個(gè)段中，然后對(duì)該段加鎖，并完成 put 操作。在多線程環(huán)境中，如果多個(gè)線程同時(shí)進(jìn)行put操作，只要被加入的表項(xiàng)不存放在同一個(gè)段中，則線程間可以做到真正的并行。
四、其他的集合類
LinkedList: 線程不安全，同ArrayListTreeSet： 線程不安全，同HashSetLinkedHashSet： 線程不安全，同HashSetTreeMap： 同HashMap，線程不安全HashTable： 線程安全
總結(jié)
本篇第一個(gè)部分詳細(xì)講述了ArrayList集合的底層擴(kuò)容原理，演示了ArrayList的線程不安全會(huì)導(dǎo)致拋出并發(fā)修改異常。然后通過(guò)源碼解析的方式講解了三種方式來(lái)保證線程安全：
-
Vector是通過(guò)在add等方法前加synchronized來(lái)保證線程安全 -
Collections.synchronized()是通過(guò)包裝數(shù)組，在數(shù)組的操作方法前加synchronized來(lái)保證線程安全 -
CopyOnWriteArrayList通過(guò)寫(xiě)時(shí)復(fù)制來(lái)保證線程安全的。
第二部分講解了HashSet的線程不安全性，通過(guò)兩種方式保證線程安全：
-
Collections.synchronizedSet -
CopyOnWriteArraySet
第三部分講解了HashMap的線程不安全性，通過(guò)兩種方式保證線程安全：
-
Collections.synchronizedMap -
ConcurrentHashMap
另外在講解的過(guò)程中，也詳細(xì)對(duì)比了ReentrantLock和synchronized及Lock和synchronized的區(qū)別。
特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
