學(xué)會(huì)了CopyOnWriteArrayList可以再多和面試官對線三分鐘

在這之前的幾篇文章：

• 學(xué)習(xí)并發(fā)先看這一介紹篇
  

• 五分鐘帶你入門線程
  

• Thread類和Runnable接口的源碼剖析
  

• 這一篇我們來了解Synchronized、Volatile、Final關(guān)鍵字

• 一篇搞懂Synchronized底層實(shí)現(xiàn)

• 學(xué)習(xí)volatile這一篇就夠了

• 阿里這樣的公司，為什么總是用final關(guān)鍵字來考驗(yàn)求職者

• 八仙過海，四種同步（感謝你，蘇小落）

• 深入線程池的問題連環(huán)炮

• 學(xué)Java的竟然有人不會(huì)AQS機(jī)制

• 從ReentrantLock的角度思考AQS
  

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

回憶下ArrayList

• fail-fast快速失敗機(jī)制，一個(gè)線程A在用迭代器遍歷集合時(shí)，另個(gè)線程B這時(shí)對集合修改會(huì)導(dǎo)致A快速失敗，拋出ConcurrentModificationException?異常。在java.util中的集合類都是快速失敗的

• fail-safe安全失敗機(jī)制，遍歷時(shí)不在原集合上，而是先復(fù)制一個(gè)集合，在拷貝的集合上進(jìn)行遍歷。在java.util.concurrent包下的容器類是安全失敗的，建議在并發(fā)環(huán)境下使用這個(gè)包下的集合類

? ? ? ? ? ? ? ? ? ? ? ???

ArrayList定義：

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

ArrayList簡介：

• ArrayList是實(shí)現(xiàn)List接口的可變數(shù)組，并允許null在內(nèi)的重復(fù)元素

• 底層數(shù)組實(shí)現(xiàn)，擴(kuò)容時(shí)將老數(shù)組元素拷貝到新數(shù)組中，每次擴(kuò)容是其容量的1.5倍，操作代價(jià)高

• 采用了Fail-Fast機(jī)制，面對并發(fā)的修改時(shí)，迭代器很快就會(huì)完全失敗，而不是冒著在將來某個(gè)不確定時(shí)間發(fā)生任意不確定行為的風(fēng)險(xiǎn)

• ArrayList是線程不安全的，所以在單線程中才使用ArrayList，而在多線程中可以選擇Vector或者CopyOnWriteArrayList
  

• 
  

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

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

??

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

至于為何是10

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

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

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

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

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

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

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

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

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

??

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

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

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

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

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

因?yàn)榭赡軙?huì)涉及到很多元素位置的移動(dòng)

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

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

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

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

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

Vector真的安全嗎

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

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

public class CaptainTest {
    private static Vector 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個(gè)數(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個(gè)數(shù)據(jù)并打印                        System.out.println(vector.get(i));                    }                }            });            removeThread.start();            printThread.start();            //避免同時(shí)產(chǎn)生過多線程            while (Thread.activeCount() > 20) ;        }    }
}

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

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

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

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

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

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

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

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

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

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

CopyOnWriteArrayList

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

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

設(shè)計(jì)的重點(diǎn)其實(shí)就是讀寫分離，這個(gè)思想大家再熟悉不過了吧，讀的時(shí)候不會(huì)加鎖，而寫的時(shí)候會(huì)復(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，使用完了要記得手動(dòng)釋放鎖，繼續(xù)

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

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

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

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

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

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

remove和iterator

分析remove過程

進(jìn)去indexOf看

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

當(dāng)我們想要?jiǎng)h除一個(gè)不存在的元素的時(shí)候，我們在這里會(huì)拿到false，因?yàn)榈讓佣ㄎ徊坏綍?huì)返回-1，我們進(jìn)入remove方法看，這個(gè)是重點(diǎn)

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

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

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

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

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

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

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

看里面的iterator

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

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

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

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

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

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

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

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

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

缺點(diǎn)

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

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

結(jié)束語