一、ArrayList線(xiàn)程不安全

在Java的集合框架中，想必大家對(duì)ArrayList肯定不陌生，單線(xiàn)程的情況下使用它去做一些CRUD的操作是非常方便的，先來(lái)看看這個(gè)例子：

public class ListTest {
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        arrayList.add("a");
        arrayList.add("b");
        arrayList.add("c");
        for (String s : arrayList) {
            System.out.println(s);
        }
    }
}

其輸出結(jié)果就是與元素被添加進(jìn)ArrayList的順序一樣，即：

a
b
c

但是到了多線(xiàn)程的情況下，ArrayList還會(huì)像單線(xiàn)程一樣執(zhí)行結(jié)果符合我們的預(yù)期嗎？我們?cè)賮?lái)看下這個(gè)例子：

public class ListTest {
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        for (int i = 0; i < 30; i++) {
            new Thread(()->{
                arrayList.add(UUID.randomUUID().toString().substring(0,5));
                //往list中添加一個(gè)長(zhǎng)為5的隨機(jī)字符串
                System.out.println(arrayList);
                //讀取list
            },"線(xiàn)程"+(i+1)).start();
        }
    }
}

由輸出結(jié)果：

Exception in thread "線(xiàn)程10" 
Exception in thread "線(xiàn)程1" 
Exception in thread "線(xiàn)程14"
Exception in thread "線(xiàn)程3" 
Exception in thread "線(xiàn)程5" 
Exception in thread "線(xiàn)程2"
Exception in thread "線(xiàn)程6" 
Exception in thread "線(xiàn)程21" 
Exception in thread "線(xiàn)程23" 
Exception in thread "線(xiàn)程28" 
Exception in thread "線(xiàn)程29" 
java.util.ConcurrentModificationException

我們發(fā)現(xiàn)，多線(xiàn)程的情況下，有多個(gè)線(xiàn)程對(duì)ArrayList添加元素，同時(shí)又會(huì)有多個(gè)元素對(duì)ArrayList進(jìn)行元素的讀取，這樣使得程序拋出了ConcurrentModificationException并發(fā)修改異常，所以我們可以下定結(jié)論：ArrayList線(xiàn)程不安全！

二、解決ArrayList線(xiàn)程不安全的方案

1、使用Vector類(lèi)

我們知道，Java集合中的Vector類(lèi)是線(xiàn)程安全的，可以用Vector去解決上述的問(wèn)題。

public class ListTest {
    public static void main(String[] args) {
        List<String> arrayList = new Vector<>();
        for (int i = 0; i < 30; i++) {
            new Thread(()->{
                arrayList.add(UUID.randomUUID().toString().substring(0,5));
                //往list中添加一個(gè)長(zhǎng)為5的隨機(jī)字符串
                System.out.println(arrayList);
                //讀取list
            },"線(xiàn)程"+(i+1)).start();
        }
    }
}

翻看Vector的源碼可知，其add方法是使用了synchronized同步鎖，同一時(shí)刻只允許一個(gè)線(xiàn)程對(duì)List進(jìn)行修改。雖然Vector能夠保證線(xiàn)程安全，但通過(guò)前面幾期推文的學(xué)習(xí)，synchronized的方案一般不是最優(yōu)選擇，會(huì)對(duì)程序的性能有一定的影響。

2、使用Collections類(lèi)

Collections類(lèi)中的synchronizedList方法可以使一個(gè)線(xiàn)程不安全的List轉(zhuǎn)為線(xiàn)程安全的。

public class ListTest {
    public static void main(String[] args) {
        List<String> arrayList = Collections.synchronizedList(new ArrayList<>());
        for (int i = 0; i < 30; i++) {
            new Thread(()->{
                arrayList.add(UUID.randomUUID().toString().substring(0,5));
                //往list中添加一個(gè)長(zhǎng)為5的隨機(jī)字符串
                System.out.println(arrayList);
                //讀取list
            },"線(xiàn)程"+(i+1)).start();
        }
    }
}

即使是不看synchronizedList的源碼我們也可以通過(guò)它的名字猜到其底層也是使用synchronized來(lái)保證線(xiàn)程安全的，這也不是最優(yōu)解。

3、使用CopyOnWriteArrayList類(lèi)

CopyOnWriteArrayList類(lèi)就是我們今天要主要探討的重頭。

public class ListTest {
    public static void main(String[] args) {
        List<String> arrayList = Collections.synchronizedList(new ArrayList<>());
        for (int i = 0; i < 30; i++) {
            new Thread(()->{
                arrayList.add(UUID.randomUUID().toString().substring(0,5));
                //往list中添加一個(gè)長(zhǎng)為5的隨機(jī)字符串
                System.out.println(arrayList);
                //讀取list
            },"線(xiàn)程"+(i+1)).start();
        }
    }
}

下面我們來(lái)聊聊CopyOnWriteArrayList是這么實(shí)現(xiàn)線(xiàn)程安全的。

三、CopyOnWriteArrayList

1、簡(jiǎn)介

java.util.concurrent包下的并發(fā)List只有CopyOnWriteArrayList。CopyOnWriteArrayList是一個(gè)線(xiàn)程安全的ArrrayList，對(duì)其進(jìn)行的修改操作都是在底層的一個(gè)復(fù)制的數(shù)組上進(jìn)行的，采用了寫(xiě)時(shí)復(fù)制，讀寫(xiě)分離的思想。其類(lèi)圖結(jié)構(gòu)如下：

通過(guò)類(lèi)圖可以清楚下面幾點(diǎn)：

• 每個(gè)CopyOnWriteArrayList對(duì)象中有一個(gè)array數(shù)組對(duì)象用來(lái)存放具體元素
• ReentrantLock獨(dú)占鎖對(duì)象用來(lái)保證同一時(shí)刻只有一個(gè)線(xiàn)程對(duì)array進(jìn)行修改

如果要我們自己來(lái)實(shí)現(xiàn)一個(gè)寫(xiě)時(shí)復(fù)制的線(xiàn)程安全的List，要考慮哪些點(diǎn)呢？

下面我們帶著以下的問(wèn)題與思考，來(lái)學(xué)習(xí)下CopyOnWriteArrayList吧！

• 何時(shí)初試化list，初始化的list元素個(gè)數(shù)為多少，list的大小是是有限的嗎？
• 如何保證線(xiàn)程安全，多個(gè)線(xiàn)程對(duì)list進(jìn)行讀寫(xiě)時(shí)是如何保證線(xiàn)程安全的？
• 如何確保使用迭代器變量list時(shí)的數(shù)據(jù)一致性？

2、主要方法源碼分析

1、初始化

無(wú)參構(gòu)造函數(shù)，其實(shí)是在內(nèi)部創(chuàng)建了一個(gè)大小為0的Object數(shù)組作為array的初始值

 	public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

有參構(gòu)造函數(shù)有兩個(gè)：

	public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

CopyOnWriteArrayList中的array數(shù)組元素是入?yún)oCopyIn數(shù)組元素的拷貝。

	public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements;
        if (c.getClass() == CopyOnWriteArrayList.class)
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
            elements = c.toArray();
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elements.getClass() != Object[].class)
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        setArray(elements);
    }

入?yún)榧蠒r(shí)，將集合里的元素復(fù)制到CopyOnWriteArrayList中。

2、添加元素

CopyOnWriteArrayList中用來(lái)添加元素的方法有很多，原理均類(lèi)似，故選取add(E e)方法來(lái)進(jìn)行學(xué)習(xí)。

	 public boolean add(E e) {
	 	//(1)
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
        	//(2)
            Object[] elements = getArray();
            //(3)
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            //(4)
            setArray(newElements);
            return true;
        } finally {
        	//(5)
            lock.unlock();
        }
    }

上述代碼中，獨(dú)占鎖的思想非常值得學(xué)習(xí)。

• 調(diào)用add方法的線(xiàn)程會(huì)首先執(zhí)行代碼(1)去獲取獨(dú)占鎖，如果有多個(gè)線(xiàn)程都調(diào)用add方法時(shí)則只有一個(gè)線(xiàn)程會(huì)去獲取到該鎖，其他線(xiàn)程會(huì)被阻塞掛起直到鎖被釋放。
• 一個(gè)線(xiàn)程獲取到鎖后，就保證了該線(xiàn)程添加元素的過(guò)程中其他線(xiàn)程不會(huì)對(duì)array數(shù)組進(jìn)行修改。
• 線(xiàn)程獲取到所后執(zhí)行代碼(2)獲取array，然后執(zhí)行代碼(3)復(fù)制array到一個(gè)新數(shù)組中，新數(shù)組的大小是array數(shù)組的大小+1，所以CopyOnWriteArrayList是無(wú)界的List，并把新的元素添加進(jìn)新數(shù)組中。
• 代碼(4)使用新數(shù)組替換原數(shù)組，并在返回前執(zhí)行(5)釋放鎖。由于加了鎖，所以整個(gè)add的過(guò)程是原子性操作。

小結(jié)一下就是，添加元素時(shí)，線(xiàn)程先獲取獨(dú)占鎖，然后復(fù)制原數(shù)組到新數(shù)組，給新數(shù)組添加元素，再把添加完元素后的新數(shù)組復(fù)制回原數(shù)組，最后釋放鎖返回。這就是所謂的寫(xiě)時(shí)復(fù)制。

3、獲取指定位置元素

使用 E get(int index)獲取下班為index的元素，如果元素不存在則拋出IndexOutOfBoundsException異常。

	public E get(int index) {
        return get(getArray(), index);
    }
    final Object[] getArray() {
        return array;
    }
    private E get(Object[] a, int index) {
        return (E) a[index];
    }

上述的代碼中，當(dāng)線(xiàn)程x調(diào)用get方法獲取指定位置的元素時(shí)，需要分兩步，首先獲取array數(shù)組，然后通過(guò)下標(biāo)訪(fǎng)問(wèn)指定位置的元素，這個(gè)過(guò)程是沒(méi)有加鎖同步的。假設(shè)這時(shí)候List的內(nèi)容如圖所示，里面有1、2、3的元素：

由于線(xiàn)程x調(diào)用get方法時(shí)是沒(méi)有加鎖的，這就可能導(dǎo)致線(xiàn)程x在獲取完array數(shù)組之后、訪(fǎng)問(wèn)指定位置元素之前，另外一個(gè)線(xiàn)程y進(jìn)行了remove操作，假設(shè)要?jiǎng)h除元素1，remove操作首先或獲取獨(dú)占鎖，然后進(jìn)行寫(xiě)時(shí)復(fù)制，也就是復(fù)制一份當(dāng)前array數(shù)組，然后在復(fù)制的數(shù)組里刪除線(xiàn)程x要調(diào)用get方法訪(fǎng)問(wèn)的元素1，然后讓array指向復(fù)制的數(shù)組。所以這個(gè)時(shí)候array之前指向的數(shù)組的引用計(jì)數(shù)為1而不為0，因?yàn)榫€(xiàn)程x還在使用它，這是線(xiàn)程x要訪(fǎng)問(wèn)指定位置的元素了，而它操作的數(shù)組就是線(xiàn)程B刪除元素之前的數(shù)組。如下示意圖：

雖然線(xiàn)程y刪除了index處的元素，但是線(xiàn)程x還是能夠讀到index處的元素，這就是寫(xiě)時(shí)復(fù)制策略產(chǎn)生的弱一致性問(wèn)題。

4、修改指定元素

使用E set(int index, E element)方法修改list中指定元素的值時(shí)，如果指定位置元素不存在則拋出IndexOutOfBoundsException異常。

 	public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            E oldValue = get(elements, index);
            if (oldValue != element) {
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

上述代碼也是先獲取獨(dú)占鎖，從而阻止其他線(xiàn)程對(duì)array數(shù)組進(jìn)行修改，然后獲取當(dāng)前數(shù)組，調(diào)用get方法獲取指定位置的元素，若指定位置的元素值與新值不一致，則創(chuàng)建新數(shù)組并復(fù)制元素，然后在新數(shù)組上修改元素值，再將array指向新數(shù)組；如果指定位置的元素值與新值一直，則為了保證volatile語(yǔ)義，還是要重新設(shè)置array，雖然其值為改變。

5、刪除元素

這里介紹E remove(int index)方法。

	public E remove(int index) {
		//獲取獨(dú)占鎖
        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除的是最后一個(gè)元素
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
            	//刪除的不是最后一個(gè)元素，則分兩次復(fù)制刪除后剩余的元素到新數(shù)組中
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                //使用新數(shù)組替換原數(shù)組
                setArray(newElements);
            }
            return oldValue;
        } finally {
        	//釋放鎖
            lock.unlock();
        }
    }

如上代碼其實(shí)和新增元素的代碼類(lèi)似，首先獲取獨(dú)占鎖以保證刪除數(shù)據(jù)期間其他線(xiàn)程不能對(duì) array 進(jìn)行修改，然后獲取數(shù)組中要被刪除的元素，并把剩余的元素復(fù)制到新數(shù)組，之后使用新數(shù)組替換原來(lái)的數(shù)組，最后在返回前釋放鎖。

6、弱一致性的迭代器

在講解什么是迭代器的弱一致性前，先看看下面的例子：

public class ListTest {
    public static void main(String[] args) {
        List<String> arrayList =new CopyOnWriteArrayList<>();
        arrayList.add("Hello");
        arrayList.add("HuYa");
        Iterator<String> iterator = arrayList.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

輸出如下：

Hello
HuYa

iterator的hasNext方法用于判斷集合中是否還有元素，next用于返回具體元素。 那么CopyOnWriteArrayList中迭代器的弱一致性又是啥意思？所謂弱一致性，是指返回迭代器后，其他線(xiàn)程對(duì)list的增刪改對(duì)迭代器是不可見(jiàn)的。

  	public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }
    static final class COWIterator<E> implements ListIterator<E> {
        //array的快照版本
        private final Object[] snapshot;
        //數(shù)組下標(biāo)
        private int cursor;
        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }
        public boolean hasNext() {
            return cursor < snapshot.length;
        }
        public E next() {
            if (! hasNext())
                throw new NoSuchElementException();
            return (E) snapshot[cursor++];
        }
    }

上述代碼中，當(dāng)CopyOnWriteArrayList對(duì)象調(diào)用iterator()方法獲取迭代器時(shí)實(shí)際上會(huì)返回COWIterator對(duì)象，COWIterator對(duì)象的snapshot變量保存了當(dāng)前l(fā)ist的內(nèi)容， cursor是遍歷list時(shí)數(shù)據(jù)的下標(biāo)。

特別對(duì)snapshot快照進(jìn)行一個(gè)說(shuō)明：

• 如果在一個(gè)線(xiàn)程使用list返回的迭代器遍歷元素的過(guò)程中，其他線(xiàn)程沒(méi)有對(duì)list進(jìn)行修改，那么snapshot本身就是list的array了。
• 如果在一個(gè)線(xiàn)程使用list返回的迭代器遍歷元素的過(guò)程中，其他線(xiàn)程有對(duì)list進(jìn)行修改，那么snapshot就是array的一個(gè)快照了，因?yàn)樾薷暮髄ist里面的數(shù)組其實(shí)是被新數(shù)組替換了，這時(shí)候原來(lái)的數(shù)組是被snapshot繼續(xù)引用。

這也說(shuō)明一個(gè)線(xiàn)程獲取了迭代器后，使用該迭代器元素時(shí)，其他線(xiàn)程對(duì)該list進(jìn)行的修改是不可見(jiàn)的，因?yàn)樗鼈儾僮鞯氖莾蓚€(gè)不同的數(shù)組，這也就是弱一致性。

最后再來(lái)看看一個(gè)例子：

public class ListTest {
    public static void main(String[] args) throws InterruptedException {
        List<String> arrayList =new CopyOnWriteArrayList<>( );
        arrayList.add("Hello");
        arrayList.add("HuYa");
        arrayList.add("Welcome");
        arrayList.add("to");
        arrayList.add("Guangzhou");
        Thread thread = new Thread(() -> {
            arrayList.set(1, "WeiXin");
            arrayList.remove(2);
            arrayList.remove(3);
        });
        //保證在修改線(xiàn)程啟動(dòng)前先獲取迭代器
        Iterator<String> iterator = arrayList.iterator();
        Thread.sleep(1000);
        //修改線(xiàn)程啟動(dòng)
        thread.start();
        //等待修改執(zhí)行完畢
        thread.join();
        //迭代元素
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

輸出結(jié)果如下：

Hello
HuYa
Welcome
to
Guangzhou

雖然說(shuō)子線(xiàn)程對(duì)arrayList進(jìn)行了修改，但是主線(xiàn)程在arrayList被修改之前先獲取到了其迭代器，拿到了原來(lái)數(shù)組的快照，所以子線(xiàn)程的修改對(duì)于主線(xiàn)程使用迭代器進(jìn)行迭代并沒(méi)有影響。這就體現(xiàn)了CopyOnWriteArrayList迭代器的弱一致性。

四、總結(jié)

本期主要學(xué)習(xí)了CopyOnWriteArrayList一些主要方法的源碼、思想，總結(jié)一下：

• 最主要的是它寫(xiě)時(shí)復(fù)制的策略，來(lái)保證List的一致性，獲取、修改、寫(xiě)入三步操作不是原子性的，故在增刪改的過(guò)程中都使用了獨(dú)占鎖，來(lái)保證同一時(shí)刻只能有一個(gè)線(xiàn)程對(duì)list進(jìn)行修改。
• CopyOnWriteArrayList提供了弱一致性的迭代器，從而保證在獲取迭代器后，其他線(xiàn)程對(duì)list的修改對(duì)于迭代器是不可見(jiàn)的。
• 綜合CopyOnWriteArrayList上述的特性，它適用于讀多寫(xiě)少的高并發(fā)場(chǎng)景。

但是CopyOnWriteArrayList也有缺點(diǎn)，開(kāi)發(fā)時(shí)要注意一下：

• 內(nèi)存占用問(wèn)題。因?yàn)镃opyOnWriteArrayList的寫(xiě)時(shí)復(fù)制機(jī)制，所以在進(jìn)行寫(xiě)操作的時(shí)候，內(nèi)存里會(huì)同時(shí)駐扎兩個(gè)對(duì)象的內(nèi)存，即舊的對(duì)象和新寫(xiě)入的對(duì)象（注意:在復(fù)制的時(shí)候只是復(fù)制容器里的引用，只是在寫(xiě)的時(shí)候會(huì)創(chuàng)建新對(duì)象添加到新容器里，而舊容器的對(duì)象還在使用，所以有兩份對(duì)象內(nèi)存）。如果這些對(duì)象占用的內(nèi)存比較大，這個(gè)時(shí)候很有可能造成頻繁的GC，應(yīng)用響應(yīng)時(shí)間也隨之變長(zhǎng)。
• 數(shù)據(jù)一致性問(wèn)題。CopyOnWriteArrayList容器只能保證數(shù)據(jù)的最終一致性，不能保證數(shù)據(jù)的實(shí)時(shí)一致性。

以上就是java高并發(fā)下CopyOnWriteArrayList替代ArrayList的詳細(xì)內(nèi)容，更多關(guān)于java高并發(fā)CopyOnWriteArrayList的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！