[[439753]]

ArrayList是大家用的再熟悉不過的集合了，而此集合設(shè)計之初也是為了高效率，并未考慮多線程場景下，所以也就有了多線程下的CopyOnWriteArrayList這一集合。

回憶下ArrayList

集合的fail-fast機(jī)制和fail-safe機(jī)制：

• fail-fast快速失敗機(jī)制，一個線程A在用迭代器遍歷集合時，另個線程B這時對集合修改會導(dǎo)致A快速失敗，拋出ConcurrentModificationException 異常。在java.util中的集合類都是快速失敗的。
• fail-safe安全失敗機(jī)制，遍歷時不在原集合上，而是先復(fù)制一個集合，在拷貝的集合上進(jìn)行遍歷。在java.util.concurrent包下的容器類是安全失敗的，建議在并發(fā)環(huán)境下使用這個包下的集合類。

ArrayList定義：

public class ArrayList extends AbstractList 
 
implements List, RandomAccess, Cloneable, java.io.Serializable { } 

ArrayList簡介：

• ArrayList是實(shí)現(xiàn)List接口的可變數(shù)組，并允許null在內(nèi)的重復(fù)元素
• 底層數(shù)組實(shí)現(xiàn)，擴(kuò)容時將老數(shù)組元素拷貝到新數(shù)組中，每次擴(kuò)容是其容量的1.5倍，操作代價高
• 采用了Fail-Fast機(jī)制，面對并發(fā)的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發(fā)生任意不確定行為的風(fēng)險
• ArrayList是線程不安全的，所以在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList

重點(diǎn)關(guān)注問題：

ArrayList默認(rèn)大小(為什么是這個?)，擴(kuò)容機(jī)制?

ArrayList的默認(rèn)初始化大小是10(在新建的時候還是空，只有當(dāng)放入第一個元素的時候才會變成10)，若知道ArrayList的大致容量，可以在初始化的時候指定大小，可以在適當(dāng)程度減少擴(kuò)容的性能消耗(看下一個問題解析)。

至于為何是10

據(jù)說是因?yàn)閟un的程序員對一系列廣泛使用的程序代碼進(jìn)行了調(diào)研，結(jié)果就是10這個長度的數(shù)組是最常用的最有效率的。也有說就是隨便起的一個數(shù)字，8個12個都沒什么區(qū)別，只是因?yàn)?0這個數(shù)組比較的圓滿而已。

ArrayList的擴(kuò)容機(jī)制

當(dāng)添加元素的時候數(shù)組是空的，則直接給一個10長度的數(shù)組。當(dāng)需要長度的數(shù)組大于現(xiàn)在長度的數(shù)組的時候，通過新=舊+舊>>1(即新=1.5倍的舊)來擴(kuò)容，當(dāng)擴(kuò)容的大小還是不夠需要的長度的時候，則將數(shù)組大小直接置為需要的長度(這一點(diǎn)切記!)。

ArrayList特點(diǎn)訪問速度塊，為什么?插入刪除一定慢嗎?適合做隊列嗎?

ArrayList從結(jié)構(gòu)上來看屬于數(shù)組，也就是內(nèi)存中的一塊連續(xù)空間，當(dāng)我們get(index)時，可以直接根據(jù)數(shù)組的首地址和偏移量計算出我們想要元素的位置，我們可以直接訪問該地址的元素，所以查詢速度是O(1)級別的。

我們平時會說ArrayList插入刪除這種操作慢，查詢速度快，其實(shí)也不是絕對的。

當(dāng)數(shù)組很大時，插入刪除的位置決定速度的快慢，假設(shè)數(shù)組當(dāng)前大小是一千萬，我們在數(shù)組的index為0的位置插入或者刪除一個元素，需要移動后面所有的元素，消耗是很大的。但是如果在數(shù)組末端index操作，這樣只會移動少量元素，速度還是挺快的(插入時如果在加上數(shù)組擴(kuò)容，會更消耗內(nèi)存)。

個人覺得不太適合做隊列，基于上面的分析，隊列會涉及到大量的增加和刪除(也就是移位操作)，在ArrayList中效率還是不高。

ArrayList 底層實(shí)現(xiàn)就是數(shù)組，訪問速度本身就很快，為何還要實(shí)現(xiàn) RandomAccess ?

RandomAccess是一個空的接口, 空接口一般只是作為一個標(biāo)識, 如Serializable接口。

JDK文檔說明RandomAccess是一個標(biāo)記接口(Marker interface), 被用于List接口的實(shí)現(xiàn)類, 表明這個實(shí)現(xiàn)類支持快速隨機(jī)訪問功能(如ArrayList). 當(dāng)程序在遍歷這中List的實(shí)現(xiàn)類時, 可以根據(jù)這個標(biāo)識來選擇更高效的遍歷方式。

優(yōu)缺點(diǎn)

上面說的查詢速度快自然就是其中的優(yōu)點(diǎn)，除此之外，還可以存儲相同的元素。

底層數(shù)據(jù)結(jié)構(gòu)屬于數(shù)組，和數(shù)組的優(yōu)缺點(diǎn)大同小異，數(shù)組屬于線性表，更適合于那種在末尾經(jīng)常添加數(shù)據(jù)的場景，而對于在整個list中各個位置隨機(jī)添加元素比較多的情況則不太合適。

因?yàn)榭赡軙婕暗胶芏嘣匚恢玫囊苿印?/p>

ArrayList還有一個比較大的缺點(diǎn)就是不適應(yīng)于多線程環(huán)境，這個設(shè)計之初也不是用于多線程環(huán)境的，像ArrayList、LinkedList、HashMap這種常見的都是以效率優(yōu)先的，都是沒有考慮線程安全的，也就自然不是線程安全的。

而這，恰恰也就是本文的重點(diǎn)，也是面試官最愛的菜。

ArrayList中的Fail-fast機(jī)制

fail-fast快速失敗機(jī)制，一個線程A在用迭代器遍歷集合時，此時另一個線程B如果對集合進(jìn)行修改，就會導(dǎo)致線程A快速失敗，然后線程會拋出.。ConcurrentModificationException異常。

在java.util中的集合類都是快速失敗的，快速失敗機(jī)制就是應(yīng)對多線程場景的。

Vector真的安全嗎

如何使用安全的ArrayList，很多人的答案可能是Vector，而Vector的實(shí)現(xiàn)其實(shí)也很簡單，我給大家看段代碼。

是的，道理也很簡單，就是直接在每個方法加上synchronized關(guān)鍵字。

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個數(shù)據(jù) 
                        vector.remove(i); 
                    } 
                } 
            }); 
            Thread printThread = new Thread(new Runnable() { 
                @Override 
                public void run() { 
                    for (int i = 0; i < vector.size(); i++) { 
                        Thread.yield(); 
                        //獲取第i個數(shù)據(jù)并打印 
                        System.out.println(vector.get(i)); 
                    } 
                } 
            }); 
            removeThread.start(); 
            printThread.start(); 
            //避免同時產(chǎn)生過多線程 
            while (Thread.activeCount() > 20) ; 
        } 
    } 
 
} 

我們來執(zhí)行上面的這段代碼，這段代碼會產(chǎn)生兩種線程，一種remove移除元素，一種是get獲取元素，但是都調(diào)用了size方法獲取大小。

執(zhí)行之后會報一個越界的異常，這是為啥呢，Vector不是每個方法都加上了synchronized關(guān)鍵字了嗎，怎么會出現(xiàn)這種錯誤。

加上關(guān)鍵字保證其它線程不能同時調(diào)用這些方法了，也就是，不能出現(xiàn)兩個及兩個以上的線程在同時調(diào)用這些同步方法。

圖中報錯的問題的原因是：例子中的線程連續(xù)調(diào)用了兩個或者兩個以上的同步方法，聽起來很奇怪是嗎?我來解釋下。

例子中的removeThread線程會首先調(diào)用size方法獲取大小，接著調(diào)用remove方法移除相應(yīng)位置的元素，而printThread線程也是先調(diào)用size方法獲取大小，接著調(diào)用get方法獲取相應(yīng)位置的元素。

假設(shè)vector大小是5，此時printThread線程執(zhí)行到i=4的時候，進(jìn)入for循環(huán)但是在執(zhí)行輸出之前，線程的CPU時間片到了，此時printThread則轉(zhuǎn)入到就緒狀態(tài)。

此時removeThread線程獲得CPU的執(zhí)行權(quán)，然后把vector中的5個元素都刪除了，此時removeThread的CPU時間片到了。

而此時printThread再獲取到CPU的執(zhí)行權(quán)，此時執(zhí)行輸出中的get(4)方法就會出現(xiàn)越界的錯誤，因?yàn)榇藭rvector中的元素已經(jīng)被remove線程刪除了。

synchronized關(guān)鍵字保證的是同一時間片只有一個線程進(jìn)入該方法執(zhí)行，但是無法保證多個線程之間的數(shù)據(jù)同步，也就是remove線程刪除vector元素之后無法通知到print線程。

聰明的你應(yīng)該已經(jīng)理解這個場景了吧，所以，vector在多線程使用的時候也不是絕對安全的。

CopyOnWriteArrayList

這個就是為了解決多線程下的ArrayList而生的，位于java.util.cocurrent包下，就是為并發(fā)而設(shè)計的。

我們聽名字其實(shí)也可以簡單的讀懂，就是寫的時候會復(fù)制一份新的數(shù)據(jù)，而事實(shí)是每一次的數(shù)據(jù)改動都會伴隨這一次數(shù)據(jù)的復(fù)制。

設(shè)計的重點(diǎn)其實(shí)就是讀寫分離，這個思想大家再熟悉不過了吧，讀的時候不會加鎖，而寫的時候會復(fù)制一份新數(shù)據(jù)，然后加上鎖之后進(jìn)行修改。

老規(guī)矩，先看一段代碼，我們通過debug的方式來學(xué)習(xí)下先。

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，使用完了要記得手動釋放鎖，繼續(xù)：

add的過程也是比較簡單的，先是加鎖，加鎖之后調(diào)用getArray，這個就是拿到現(xiàn)在的數(shù)組，然后取得數(shù)組的大小。

接著是將原數(shù)組復(fù)制到一個大小加一的一個更大的數(shù)組中，然后將要添加的元素復(fù)制到最后的位置，最后再調(diào)用SetArray進(jìn)行賦值，完成替換。

我們可以通過地址很清晰的看到，新數(shù)組就是又重新開辟了一塊內(nèi)存空間，和原來數(shù)組是完全不一樣的。

其實(shí)這也就意味著每次add增加元素都需要一次數(shù)組的復(fù)制。

對于get獲取元素來說也沒有太多需要注意的，這個里面沒有什么額外的操作，沒有什么復(fù)制新數(shù)組一類的操作，只是簡單的從原數(shù)組取值即可。

這也就意味著在多線程運(yùn)行的時候，線程讀取到的數(shù)據(jù)可能不是最新的我們想要的數(shù)據(jù)，但是這種情況是需要我們考慮到的，必須在可以接受的情況下來使用。

remove和iterator

分析remove過程：

進(jìn)去indexOf看：

這個其實(shí)也很好理解，就是循環(huán)遍歷，然后通過equals判斷，相同則返回定位到的位置。

當(dāng)我們想要刪除一個不存在的元素的時候，我們在這里會拿到false，因?yàn)榈讓佣ㄎ徊坏綍祷?1，我們進(jìn)入remove方法看，這個是重點(diǎn)。

我們再重新看一下remove的源碼。

剛剛的調(diào)試是沒有走到這里面的，我們把目光聚集到這塊代碼。

snapshot是剛剛的鏡像數(shù)據(jù)，這里考慮到了多線程的情況，即原有的數(shù)組可能已經(jīng)被其它的線程修改了，snapshot已經(jīng)過時的數(shù)據(jù)了，而這段處理的就是如果該數(shù)組被別的線程修改了的情況下，是如何處理的。

其實(shí)根本目的就是重新定位index的值，防止誤刪別的元素。

先是找到index和當(dāng)前長度中的最小值，進(jìn)行遍歷，findIndex就是做這個的，在其中重新找相應(yīng)的元素，找到就就直接跳出，重新判斷。

如果沒有找到元素下標(biāo)，就進(jìn)行下面的判斷，index大于len的時候，代表元素被刪除或者不存在了。

也不是很難理解，大家看一下這塊就可以理解了。

看里面的iterator

這個迭代器和原來ArrayList中的迭代器區(qū)別點(diǎn)就是增加了一個快照機(jī)制，這個快照就是把遍歷時的這個最新鏈表狀態(tài)記錄了下來。

此快照數(shù)組在迭代器的生存期內(nèi)是不會更改的，因此也就不可能發(fā)生沖突，也就保證了迭代器不會拋出并發(fā)修改異常。

創(chuàng)建迭代器以后，迭代器不會反映列表的添加、移除和更改等修改的操作，但是也就同時帶來了一個小小的問題，遍歷拿到的數(shù)據(jù)可能不是最新的數(shù)據(jù)。

需要注意的一點(diǎn)，ArrayList在迭代器上進(jìn)行元素的更改操作是不被允許的，比如remove、set和add操作，這些方法將拋出UnsupportedOperationException異常。

CopyOnWriteArrayList優(yōu)缺點(diǎn)分析

優(yōu)點(diǎn)

讀操作性能高，無需要任何的同步措施，比較適合于讀多寫少的并發(fā)場景。

采用讀寫分離的思想，讀的時候讀取鏡像的數(shù)據(jù)，寫的時候復(fù)制一份新的數(shù)據(jù)進(jìn)行修改操作，所以也就不會拋出并發(fā)修改異常了。

存儲的數(shù)據(jù)有序，剛剛在看源碼的時候你應(yīng)該注意到了，它是先進(jìn)行原數(shù)據(jù)的復(fù)制，然后再在最后位置上賦值這個要添加的數(shù)據(jù)。

缺點(diǎn)

內(nèi)存占用問題，每次寫操作都需要將原容器數(shù)據(jù)拷貝一份，數(shù)據(jù)量比較大的時候，對內(nèi)存壓力會比較多，也有可能引起頻繁的GC。 

讀取的時候無法保證實(shí)時性，這也是讀寫分離付出的代價，Vector可以保證讀寫的強(qiáng)一致性，但是缺點(diǎn)上面也已經(jīng)說過了，不同的場景使用不同的容器。

哦對了，后續(xù)所有的文章都會更新到這里。 

https://github.com/DayuMM2021/Java

本文轉(zhuǎn)載自微信公眾號「Java賊船  」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系Java賊船公眾號。