學會了 CopyOnWriteArrayList 可以再多和面試官對線三分鐘
ArrayList是大家用的再熟悉不過的集合了，而此集合設計之初也是為了高效率，并未考慮多線程場景下，所以也就有了多線程下的CopyOnWriteArrayList這一集合。
回憶下ArrayList
集合的fail-fast機制和fail-safe機制：
- fail-fast快速失敗機制，一個線程A在用迭代器遍歷集合時，另個線程B這時對集合修改會導致A快速失敗，拋出ConcurrentModificationException 異常。在java.util中的集合類都是快速失敗的。
- fail-safe安全失敗機制，遍歷時不在原集合上，而是先復制一個集合，在拷貝的集合上進行遍歷。在java.util.concurrent包下的容器類是安全失敗的，建議在并發環境下使用這個包下的集合類。
ArrayList定義：
- public class ArrayList extends AbstractList
- implements List, RandomAccess, Cloneable, java.io.Serializable { }
ArrayList簡介：
- ArrayList是實現List接口的可變數組，并允許null在內的重復元素
- 底層數組實現，擴容時將老數組元素拷貝到新數組中，每次擴容是其容量的1.5倍，操作代價高
- 采用了Fail-Fast機制，面對并發的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發生任意不確定行為的風險
- ArrayList是線程不安全的，所以在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList
重點關注問題：
ArrayList默認大小(為什么是這個?)，擴容機制?
ArrayList的默認初始化大小是10(在新建的時候還是空，只有當放入第一個元素的時候才會變成10)，若知道ArrayList的大致容量，可以在初始化的時候指定大小，可以在適當程度減少擴容的性能消耗(看下一個問題解析)。
至于為何是10
據說是因為sun的程序員對一系列廣泛使用的程序代碼進行了調研，結果就是10這個長度的數組是最常用的最有效率的。也有說就是隨便起的一個數字，8個12個都沒什么區別，只是因為10這個數組比較的圓滿而已。
ArrayList的擴容機制
當添加元素的時候數組是空的，則直接給一個10長度的數組。當需要長度的數組大于現在長度的數組的時候，通過新=舊+舊>>1(即新=1.5倍的舊)來擴容，當擴容的大小還是不夠需要的長度的時候，則將數組大小直接置為需要的長度(這一點切記!)。
ArrayList特點訪問速度塊，為什么?插入刪除一定慢嗎?適合做隊列嗎?
ArrayList從結構上來看屬于數組，也就是內存中的一塊連續空間，當我們get(index)時，可以直接根據數組的首地址和偏移量計算出我們想要元素的位置，我們可以直接訪問該地址的元素，所以查詢速度是O(1)級別的。
我們平時會說ArrayList插入刪除這種操作慢，查詢速度快，其實也不是絕對的。
當數組很大時，插入刪除的位置決定速度的快慢，假設數組當前大小是一千萬，我們在數組的index為0的位置插入或者刪除一個元素，需要移動后面所有的元素，消耗是很大的。但是如果在數組末端index操作，這樣只會移動少量元素，速度還是挺快的(插入時如果在加上數組擴容，會更消耗內存)。
個人覺得不太適合做隊列，基于上面的分析，隊列會涉及到大量的增加和刪除(也就是移位操作)，在ArrayList中效率還是不高。
ArrayList 底層實現就是數組，訪問速度本身就很快，為何還要實現 RandomAccess ?
RandomAccess是一個空的接口, 空接口一般只是作為一個標識, 如Serializable接口。
JDK文檔說明RandomAccess是一個標記接口(Marker interface), 被用于List接口的實現類, 表明這個實現類支持快速隨機訪問功能(如ArrayList). 當程序在遍歷這中List的實現類時, 可以根據這個標識來選擇更高效的遍歷方式。
優缺點
上面說的查詢速度快自然就是其中的優點，除此之外，還可以存儲相同的元素。
底層數據結構屬于數組，和數組的優缺點大同小異，數組屬于線性表，更適合于那種在末尾經常添加數據的場景，而對于在整個list中各個位置隨機添加元素比較多的情況則不太合適。
因為可能會涉及到很多元素位置的移動。
ArrayList還有一個比較大的缺點就是不適應于多線程環境，這個設計之初也不是用于多線程環境的，像ArrayList、LinkedList、HashMap這種常見的都是以效率優先的，都是沒有考慮線程安全的，也就自然不是線程安全的。
而這，恰恰也就是本文的重點，也是面試官最愛的菜。
ArrayList中的Fail-fast機制
fail-fast快速失敗機制，一個線程A在用迭代器遍歷集合時，此時另一個線程B如果對集合進行修改，就會導致線程A快速失敗，然后線程會拋出.。ConcurrentModificationException異常。
在java.util中的集合類都是快速失敗的，快速失敗機制就是應對多線程場景的。
Vector真的安全嗎
如何使用安全的ArrayList，很多人的答案可能是Vector，而Vector的實現其實也很簡單，我給大家看段代碼。
是的，道理也很簡單，就是直接在每個方法加上synchronized關鍵字。
- public class CaptainTest {
- private static Vector<Integer> vector = new Vector();
- public static void main(String[] args) {
- while (true) {
- for (int i = 0; i < 10; i++) {
- vector.add(i); //往vector中添加元素
- }
- Thread removeThread = new Thread(new Runnable() {
- @Override
- public void run() {
- for (int i = 0; i < vector.size(); i++) {
- Thread.yield();
- //移除第i個數據
- vector.remove(i);
- }
- }
- });
- Thread printThread = new Thread(new Runnable() {
- @Override
- public void run() {
- for (int i = 0; i < vector.size(); i++) {
- Thread.yield();
- //獲取第i個數據并打印
- System.out.println(vector.get(i));
- }
- }
- });
- removeThread.start();
- printThread.start();
- //避免同時產生過多線程
- while (Thread.activeCount() > 20) ;
- }
- }
- }
我們來執行上面的這段代碼，這段代碼會產生兩種線程，一種remove移除元素，一種是get獲取元素，但是都調用了size方法獲取大小。
執行之后會報一個越界的異常，這是為啥呢，Vector不是每個方法都加上了synchronized關鍵字了嗎，怎么會出現這種錯誤。
加上關鍵字保證其它線程不能同時調用這些方法了，也就是，不能出現兩個及兩個以上的線程在同時調用這些同步方法。
圖中報錯的問題的原因是：例子中的線程連續調用了兩個或者兩個以上的同步方法，聽起來很奇怪是嗎?我來解釋下。
例子中的removeThread線程會首先調用size方法獲取大小，接著調用remove方法移除相應位置的元素，而printThread線程也是先調用size方法獲取大小，接著調用get方法獲取相應位置的元素。
假設vector大小是5，此時printThread線程執行到i=4的時候，進入for循環但是在執行輸出之前，線程的CPU時間片到了，此時printThread則轉入到就緒狀態。
此時removeThread線程獲得CPU的執行權，然后把vector中的5個元素都刪除了，此時removeThread的CPU時間片到了。
而此時printThread再獲取到CPU的執行權，此時執行輸出中的get(4)方法就會出現越界的錯誤，因為此時vector中的元素已經被remove線程刪除了。
synchronized關鍵字保證的是同一時間片只有一個線程進入該方法執行，但是無法保證多個線程之間的數據同步，也就是remove線程刪除vector元素之后無法通知到print線程。
聰明的你應該已經理解這個場景了吧，所以，vector在多線程使用的時候也不是絕對安全的。
CopyOnWriteArrayList
這個就是為了解決多線程下的ArrayList而生的，位于java.util.cocurrent包下，就是為并發而設計的。
我們聽名字其實也可以簡單的讀懂，就是寫的時候會復制一份新的數據，而事實是每一次的數據改動都會伴隨這一次數據的復制。
設計的重點其實就是讀寫分離，這個思想大家再熟悉不過了吧，讀的時候不會加鎖，而寫的時候會復制一份新數據，然后加上鎖之后進行修改。
老規矩，先看一段代碼，我們通過debug的方式來學習下先。
- public static void main(String[] args) {
- CopyOnWriteArrayList list = new CopyOnWriteArrayList();
- list.add("test1");
- Thread addThread = new Thread(new Runnable() {
- @Override
- public void run() {
- list.add("test4");
- try {
- Thread.sleep(1000);
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- });
- addThread.start();
- }
來吧，我們一起debug看下過程，順便看下源碼：
加鎖用的是ReentrantLock，使用完了要記得手動釋放鎖，繼續：
add的過程也是比較簡單的，先是加鎖，加鎖之后調用getArray，這個就是拿到現在的數組，然后取得數組的大小。
接著是將原數組復制到一個大小加一的一個更大的數組中，然后將要添加的元素復制到最后的位置，最后再調用SetArray進行賦值，完成替換。
我們可以通過地址很清晰的看到，新數組就是又重新開辟了一塊內存空間，和原來數組是完全不一樣的。
其實這也就意味著每次add增加元素都需要一次數組的復制。
對于get獲取元素來說也沒有太多需要注意的，這個里面沒有什么額外的操作，沒有什么復制新數組一類的操作，只是簡單的從原數組取值即可。
這也就意味著在多線程運行的時候，線程讀取到的數據可能不是最新的我們想要的數據，但是這種情況是需要我們考慮到的，必須在可以接受的情況下來使用。
remove和iterator
分析remove過程：
進去indexOf看：
這個其實也很好理解，就是循環遍歷，然后通過equals判斷，相同則返回定位到的位置。
當我們想要刪除一個不存在的元素的時候，我們在這里會拿到false，因為底層定位不到會返回-1，我們進入remove方法看，這個是重點。
我們再重新看一下remove的源碼。
剛剛的調試是沒有走到這里面的，我們把目光聚集到這塊代碼。
snapshot是剛剛的鏡像數據，這里考慮到了多線程的情況，即原有的數組可能已經被其它的線程修改了，snapshot已經過時的數據了，而這段處理的就是如果該數組被別的線程修改了的情況下，是如何處理的。
其實根本目的就是重新定位index的值，防止誤刪別的元素。
先是找到index和當前長度中的最小值，進行遍歷，findIndex就是做這個的，在其中重新找相應的元素，找到就就直接跳出，重新判斷。
如果沒有找到元素下標，就進行下面的判斷，index大于len的時候，代表元素被刪除或者不存在了。
也不是很難理解，大家看一下這塊就可以理解了。
看里面的iterator
這個迭代器和原來ArrayList中的迭代器區別點就是增加了一個快照機制，這個快照就是把遍歷時的這個最新鏈表狀態記錄了下來。
此快照數組在迭代器的生存期內是不會更改的，因此也就不可能發生沖突，也就保證了迭代器不會拋出并發修改異常。
創建迭代器以后，迭代器不會反映列表的添加、移除和更改等修改的操作，但是也就同時帶來了一個小小的問題，遍歷拿到的數據可能不是最新的數據。
需要注意的一點，ArrayList在迭代器上進行元素的更改操作是不被允許的，比如remove、set和add操作，這些方法將拋出UnsupportedOperationException異常。
CopyOnWriteArrayList優缺點分析
優點
讀操作性能高，無需要任何的同步措施，比較適合于讀多寫少的并發場景。
采用讀寫分離的思想，讀的時候讀取鏡像的數據，寫的時候復制一份新的數據進行修改操作，所以也就不會拋出并發修改異常了。
存儲的數據有序，剛剛在看源碼的時候你應該注意到了，它是先進行原數據的復制，然后再在最后位置上賦值這個要添加的數據。
缺點
內存占用問題，每次寫操作都需要將原容器數據拷貝一份，數據量比較大的時候，對內存壓力會比較多，也有可能引起頻繁的GC。
讀取的時候無法保證實時性，這也是讀寫分離付出的代價，Vector可以保證讀寫的強一致性，但是缺點上面也已經說過了，不同的場景使用不同的容器。
哦對了，后續所有的文章都會更新到這里。
https://github.com/DayuMM2021/Java
本文轉載自微信公眾號「Java賊船 」，可以通過以下二維碼關注。轉載本文請聯系Java賊船公眾號。
