引導(dǎo)語

在 ArrayList 的類注釋上，JDK 就提醒了我們，如果要把 ArrayList 作為共享變量的話，是線程不安全的，推薦我們自己加鎖或者使用 Collections.synchronizedList 方法，其實(shí) JDK 還提供了另外一種線程安全的 List，叫做 CopyOnWriteArrayList，這個(gè) List 具有以下特征：

線程安全的，多線程環(huán)境下可以直接使用，無需加鎖； 通過鎖 + 數(shù)組拷貝 + volatile 關(guān)鍵字保證了線程安全； 每次數(shù)組操作，都會(huì)把數(shù)組拷貝一份出來，在新數(shù)組上進(jìn)行操作，操作成功之后再賦值回去。

1 整體架構(gòu)

從整體架構(gòu)上來說，CopyOnWriteArrayList 數(shù)據(jù)結(jié)構(gòu)和 ArrayList 是一致的，底層是個(gè)數(shù)組，只不過 CopyOnWriteArrayList 在對(duì)數(shù)組進(jìn)行操作的時(shí)候，基本會(huì)分四步走：

1. 加鎖；
2. 從原數(shù)組中拷貝出新數(shù)組；
3. 在新數(shù)組上進(jìn)行操作，并把新數(shù)組賦值給數(shù)組容器；
4. 解鎖

除了加鎖之外，CopyOnWriteArrayList 的底層數(shù)組還被 volatile 關(guān)鍵字修飾，意思是一旦數(shù)組被修改，其它線程立馬能夠感知到，代碼如下：

private transient volatile Object[] array;

整體上來說，CopyOnWriteArrayList 就是利用鎖 + 數(shù)組拷貝 + volatile 關(guān)鍵字保證了 List 的線程安全。

1.1 類注釋

我們看看從 CopyOnWriteArrayList 的類注釋上能得到哪些信息：

1. 所有的操作都是線程安全的，因?yàn)椴僮鞫际窃谛驴截悢?shù)組上進(jìn)行的；
2. 數(shù)組的拷貝雖然有一定的成本，但往往比一般的替代方案效率高；
3. 迭代過程中，不會(huì)影響到原來的數(shù)組，也不會(huì)拋出 ConcurrentModificationException 異常。

接著我們來看下 CopyOnWriteArrayList 的核心方法源碼。

2 新增

新增有很多種情況，比如說：新增到數(shù)組尾部、新增到數(shù)組某一個(gè)索引位置、批量新增等等，操作的思路還是我們開頭說的四步，我們拿新增到數(shù)組尾部的方法舉例，來看看底層源碼的實(shí)現(xiàn)：

// 添加元素到數(shù)組尾部
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 加鎖
    lock.lock();
    try {
        // 得到所有的原數(shù)組
        Object[] elements = getArray();
        int len = elements.length;
        // 拷貝到新數(shù)組里面，新數(shù)組的長(zhǎng)度是 + 1 的，因?yàn)樾略鰰?huì)多一個(gè)元素
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 在新數(shù)組中進(jìn)行賦值，新元素直接放在數(shù)組的尾部
        newElements[len] = e;
        // 替換掉原來的數(shù)組
        setArray(newElements);
        return true;
    // finally 里面釋放鎖，保證即使 try 發(fā)生了異常，仍然能夠釋放鎖   
    } finally {
        lock.unlock();
    }
}

從源碼中，我們發(fā)現(xiàn)整個(gè) add 過程都是在持有鎖的狀態(tài)下進(jìn)行的，通過加鎖，來保證同一時(shí)刻只能有一個(gè)線程能夠?qū)ν粋€(gè)數(shù)組進(jìn)行 add 操作。

除了加鎖之外，還會(huì)從老數(shù)組中創(chuàng)建出一個(gè)新數(shù)組，然后把老數(shù)組的值拷貝到新數(shù)組上，這時(shí)候就有一個(gè)問題：都已經(jīng)加鎖了，為什么需要拷貝數(shù)組，而不是在原來數(shù)組上面進(jìn)行操作呢，原因主要為：

• volatile 關(guān)鍵字修飾的是數(shù)組，如果我們簡(jiǎn)單的在原來數(shù)組上修改其中某幾個(gè)元素的值，是無法觸發(fā)可見性的，我們必須通過修改數(shù)組的內(nèi)存地址才行，也就說要對(duì)數(shù)組進(jìn)行重新賦值才行。
• 在新的數(shù)組上進(jìn)行拷貝，對(duì)老數(shù)組沒有任何影響，只有新數(shù)組完全拷貝完成之后，外部才能訪問到，降低了在賦值過程中，老數(shù)組數(shù)據(jù)變動(dòng)的影響。

簡(jiǎn)單 add 操作是直接添加到數(shù)組的尾部，接著我們來看下指定位置添加元素的關(guān)鍵源碼（部分源碼）：

// len：數(shù)組的長(zhǎng)度、index：插入的位置
int numMoved = len - index;
// 如果要插入的位置正好等于數(shù)組的末尾，直接拷貝數(shù)組即可
if (numMoved == 0)
    newElements = Arrays.copyOf(elements, len + 1);
else {
// 如果要插入的位置在數(shù)組的中間，就需要拷貝 2 次
// 第一次從 0 拷貝到 index。
// 第二次從 index+1 拷貝到末尾。
    newElements = new Object[len + 1];
    System.arraycopy(elements, 0, newElements, 0, index);
    System.arraycopy(elements, index, newElements, index + 1,
         numMoved);
}
// index 索引位置的值是空的，直接賦值即可。
newElements[index] = element;
// 把新數(shù)組的值賦值給數(shù)組的容器中
setArray(newElements);

從源碼中可以看到，當(dāng)插入的位置正好處于末尾時(shí)，只需要拷貝一次，當(dāng)插入的位置處于中間時(shí)，此時(shí)我們會(huì)把原數(shù)組一分為二，進(jìn)行兩次拷貝操作。

最后還有個(gè)批量新增操作，源碼我們就不貼了，底層也是拷貝數(shù)組的操作。

2.1 小結(jié)

從 add 系列方法可以看出，CopyOnWriteArrayList 通過加鎖 + 數(shù)組拷貝+ volatile 來保證了線程安全，每一個(gè)要素都有著其獨(dú)特的含義：

1. 加鎖：保證同一時(shí)刻數(shù)組只能被一個(gè)線程操作；
2. 數(shù)組拷貝：保證數(shù)組的內(nèi)存地址被修改，修改后觸發(fā) volatile 的可見性，其它線程可以立馬知道數(shù)組已經(jīng)被修改；
3. volatile：值被修改后，其它線程能夠立馬感知最新值。

3 個(gè)要素缺一不可，比如說我們只使用 1 和 3 ，去掉 2，這樣當(dāng)我們修改數(shù)組中某個(gè)值時(shí)，并不會(huì)觸發(fā) volatile 的可見特性的，只有當(dāng)數(shù)組內(nèi)存地址被修改后，才能觸發(fā)把最新值通知給其他線程的特性。

3 刪除

接著我們來看下指定數(shù)組索引位置刪除的源碼：

// 刪除某個(gè)索引位置的數(shù)據(jù)
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 加鎖
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        // 先得到老值
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        // 如果要?jiǎng)h除的數(shù)據(jù)正好是數(shù)組的尾部，直接刪除
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 如果刪除的數(shù)據(jù)在數(shù)組的中間，分三步走
            // 1. 設(shè)置新數(shù)組的長(zhǎng)度減一，因?yàn)槭菧p少一個(gè)元素
            // 2. 從 0 拷貝到數(shù)組新位置
            // 3. 從新位置拷貝到數(shù)組尾部
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

步驟分為三步：

1. 加鎖；
2. 判斷刪除索引的位置，從而進(jìn)行不同策略的拷貝；
3. 解鎖。

代碼整體的結(jié)構(gòu)風(fēng)格也比較統(tǒng)一：鎖 + try finally +數(shù)組拷貝，鎖被 final 修飾的，保證了在加鎖過程中，鎖的內(nèi)存地址肯定不會(huì)被修改，finally 保證鎖一定能夠被釋放，數(shù)組拷貝是為了刪除其中某個(gè)位置的元素。

4 批量刪除

數(shù)組的批量刪除很有意思，接下來我們來看下 CopyOnWriteArrayList 的批量刪除的實(shí)現(xiàn)過程：

// 批量刪除包含在 c 中的元素
public boolean removeAll(Collection<?> c) {
    if (c == null) throw new NullPointerException();
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        // 說明數(shù)組有值，數(shù)組無值直接返回 false
        if (len != 0) {
            // newlen 表示新數(shù)組的索引位置，新數(shù)組中存在不包含在 c 中的元素
            int newlen = 0;
            Object[] temp = new Object[len];
            // 循環(huán)，把不包含在 c 里面的元素，放到新數(shù)組中
            for (int i = 0;
 i < len;
 ++i) {
                Object element = elements[i];
                // 不包含在 c 中的元素，從 0 開始放到新數(shù)組中
                if (!c.contains(element))
                    temp[newlen++] = element;
            }
            // 拷貝新數(shù)組，變相的刪除了不包含在 c 中的元素
            if (newlen != len) {
                setArray(Arrays.copyOf(temp, newlen));
                return true;
            }
        }
        return false;
    } finally {
        lock.unlock();
    }
}

從源碼中，我們可以看到，我們并不會(huì)直接對(duì)數(shù)組中的元素進(jìn)行挨個(gè)刪除，而是先對(duì)數(shù)組中的值進(jìn)行循環(huán)判斷，把我們不需要?jiǎng)h除的數(shù)據(jù)放到臨時(shí)數(shù)組中，最后臨時(shí)數(shù)組中的數(shù)據(jù)就是我們不需要?jiǎng)h除的數(shù)據(jù)。

不知道大家有木有似曾相識(shí)的感覺，ArrayList 的批量刪除的思想也是和這個(gè)類似的，所以我們?cè)谛枰獎(jiǎng)h除多個(gè)元素的時(shí)候，最好都使用這種批量刪除的思想，而不是采用在 for 循環(huán)中使用單個(gè)刪除的方法，單個(gè)刪除的話，在每次刪除的時(shí)候都會(huì)進(jìn)行一次數(shù)組拷貝(刪除最后一個(gè)元素時(shí)不會(huì)拷貝)，很消耗性能，也耗時(shí)，會(huì)導(dǎo)致加鎖時(shí)間太長(zhǎng)，并發(fā)大的情況下，會(huì)造成大量請(qǐng)求在等待鎖，這也會(huì)占用一定的內(nèi)存。

5 其它方法

5.1 indexOf

indexOf 方法的主要用處是查找元素在數(shù)組中的下標(biāo)位置，如果元素存在就返回元素的下標(biāo)位置，元素不存在的話返回 -1，不但支持 null 值的搜索，還支持正向和反向的查找，我們以正向查找為例，通過源碼來說明一下其底層的實(shí)現(xiàn)方式：

// o：我們需要搜索的元素
// elements：我們搜索的目標(biāo)數(shù)組
// index：搜索的開始位置
// fence：搜索的結(jié)束位置
private static int indexOf(Object o, Object[] elements,
                           int index, int fence) {
    // 支持對(duì) null 的搜索
    if (o == null) {
        for (int i = index;i < fence;i++)
            // 找到第一個(gè) null 值，返回下標(biāo)索引的位置
            if (elements[i] == null)
                return i;
    } else {
        // 通過 equals 方法來判斷元素是否相等
        // 如果相等，返回元素的下標(biāo)位置
        for (int i = index;i < fence;i++)
            if (o.equals(elements[i]))
                return i;
    }
    return -1;
}

indexOf 方法在 CopyOnWriteArrayList 內(nèi)部使用也比較廣泛，比如在判斷元素是否存在時(shí)（contains），在刪除元素方法中校驗(yàn)元素是否存在時(shí)，都會(huì)使用到 indexOf 方法，indexOf 方法通過一次 for 循環(huán)來查找元素，我們?cè)谡{(diào)用此方法時(shí)，需要注意如果找不到元素時(shí)，返回的是 -1，所以有可能我們會(huì)對(duì)這個(gè)特殊值進(jìn)行判斷。

5.2 迭代

在 CopyOnWriteArrayList 類注釋中，明確說明了，在其迭代過程中，即使數(shù)組的原值被改變，也不會(huì)拋出 ConcurrentModificationException 異常，其根源在于數(shù)組的每次變動(dòng)，都會(huì)生成新的數(shù)組，不會(huì)影響老數(shù)組，這樣的話，迭代過程中，根本就不會(huì)發(fā)生迭代數(shù)組的變動(dòng)，我們截幾個(gè)圖說明一下：

迭代是直接持有原有數(shù)組的引用，也就是說迭代過程中，一旦原有數(shù)組的值內(nèi)存地址發(fā)生變化，必然會(huì)影響到迭代過程，下圖源碼演示的是 CopyOnWriteArrayList 的迭代方法，我們可以看到迭代器是直接持有原數(shù)組的引用：

我們寫了一個(gè) demo，在 CopyOnWriteArrayList 迭代之后，往 CopyOnWriteArrayList 里面新增值，從下圖中可以看到在 CopyOnWriteArrayList 迭代之前，數(shù)組的內(nèi)存地址是 962，請(qǐng)記住這個(gè)數(shù)字：

CopyOnWriteArrayList 迭代之后，我們使用 add(“50”) 代碼給數(shù)組新增一個(gè)數(shù)據(jù)后，數(shù)組內(nèi)存地址發(fā)生了變化，內(nèi)存地址從原來的 962 變成了 968，這是因?yàn)?CopyOnWriteArrayList 的 add 操作，會(huì)生成新的數(shù)組，所以數(shù)組的內(nèi)存地址發(fā)生了變化：

迭代繼續(xù)進(jìn)行時(shí)，我們發(fā)現(xiàn)迭代器中的地址仍然是迭代之前引用的地址，是 962，而不是新的數(shù)組的內(nèi)存地址：

從上面 4 張截圖，我們可以得到迭代過程中，即使 CopyOnWriteArrayList 的結(jié)構(gòu)發(fā)生變動(dòng)了，也不會(huì)拋出 ConcurrentModificationException 異常的原因：CopyOnWriteArrayList 迭代持有的是老數(shù)組的引用，而 CopyOnWriteArrayList 每次的數(shù)據(jù)變動(dòng)，都會(huì)產(chǎn)生新的數(shù)組，對(duì)老數(shù)組的值不會(huì)產(chǎn)生影響，所以迭代也可以正常進(jìn)行。

6 總結(jié)

當(dāng)我們需要在線程不安全場(chǎng)景下使用 List 時(shí)，建議使用 CopyOnWriteArrayList，CopyOnWriteArrayList 通過鎖 + 數(shù)組拷貝 + volatile 之間的相互配合，實(shí)現(xiàn)了 List 的線程安全，我們拋棄 Java 的這種實(shí)現(xiàn)，如果讓我們自己實(shí)現(xiàn)，你又將如何實(shí)現(xiàn)呢？

到此這篇關(guān)于Java中的CopyOnWriteArrayList深入解讀的文章就介紹到這了,更多相關(guān)CopyOnWriteArrayList深入解讀內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論