1. 简述

并发包中的并发list只有CopyOnWriteArrayList。CopyOnWriteArrayList是一个线程安全的list，对其进行的修改操作都是在底层的一个复制的数组上进行的，也就是写时复制策略。

在CopyOnwriteArrayList的类图中，每个对象里面都有个array数组用来存放元素，ReentrantLock独占锁对象用来保证同时只有一个线程对array进行修改。

2. 思考设计一个写时复制线程安全的list需要考虑哪些？

• 何时初始化list？ 初始化的list元素个数为多少？ list是有限大小吗？
• 如何保证线程安全？多个线程进行读写时线程如何保证安全？
• 如何保证使用迭代器遍历list时的数据一致性？

下面可以看一下CopyOnwriteArrayList如何设计的？

3. copyOnWriteArrayList 主要方法源码解析

3.1 初始化

/**
     * Creates an empty list.
     * 创建了一个大小为0 的Object 数组作为array 的初始值。
     */
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

    /**入参为集合，将集合里面的元素复制到本list
     * Creates a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection of initially held elements
     * @throws NullPointerException if the specified collection is null
     */
    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);
    }

    /**入参为一个数组, 将数组里面的元素复制到list
     * Creates a list holding a copy of the given array.
     *
     * @param toCopyIn the array (a copy of this array is used as the
     *        internal array)
     * @throws NullPointerException if the specified array is null
     */
    public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

3.2 添加元素

CopyOnWrit巳ArrayList 中用来添加元素的函数有add(E e）、add(int index, Eelement）、addifAbsent(E e）和addAllAbsent(Collection<? extends E> c） 等，它们的原理类似，以add(E e） 为例来讲解。

/**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            //(1)
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

代码(1)使用新数组替换原数组，并在返回前释放锁。由于加了锁，所以整个add 过程是个原子性操作。需要注意的是，在添加元素时，首先复制了一个快照，然后在快照上进行添加，而不是直接在原来数组上进行。

3.3 获取指定位置元素

    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];
    }

在如上代码中， 当线程x 调用get 方法获取指定位置的元素时，分两步走， 首先获取array 数组（这里命名为步骤A ），然后通过下标访问指定位置的元素（这里命名为步骤B ) ,这是两步操作， 但是在整个过程中并没有进行加锁同步。假设这时候List 内容如图5-2 所示，里面有l 、2 、3 三个元素。

如上图所示，虽然在线程y中已经删除了index处的元素。但是线程x中还是可以返回index处的元素，这就是写时复制策略产生的弱一致性问题。

3.4 修改指定元素

使用E set ( int index,E element ）修改list 中指定元素的值，如果指定位置的元素不存在则抛出IndexOutOfBoundsException 异常，代码如下。

    /**
     * Replaces the element at the specified position in this list with the
     * specified element.
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    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();
        }
    }

3.5 删除元素

删除list 里面指定的元素，可以使用E remove(int index） 、boolean remove(Object o）和

boolean remove(Object o, Object[] snapshot, int index） 等方法，它们的原理一样。

下面讲解下remove(int index）方法。

    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;
            //如果要删除的是最后一个元素
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                //分两次复制删除后剩余的元素到新数组
                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();
        }
    }

首先获取独占锁以保证删除数据期间其他线程不能对array 进行修改，然后获取数组中要被删除的元素，并把剩余的元素复制到新数组，之后使用新数组替换原来的数组，最后在返回前释放锁。

3.6 弱一致性的迭代器

迭代器的hasNext 方法用于判断列表中是否还有元素， next 方法则具体返回元素。CopyOnWriteArrayList 中迭代器的弱一致性是怎么回事， 所谓弱一致性是指返回迭代器后，其他线程对list 的增删改对迭代器是不可见的。

static final class COWIterator<E> implements ListIterator<E> {
        /** Snapshot of the array */
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor;

        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }

        public boolean hasNext() {
            return cursor < snapshot.length;
        }

        public boolean hasPrevious() {
            return cursor > 0;
        }
	
        @SuppressWarnings("unchecked")
        public E next() {
            if (! hasNext())
                throw new NoSuchElementException();
            return (E) snapshot[cursor++];
        }

为什么说snapshot 是list 的快照呢？明明是指针传递的引用啊，而不是副本？

如果在该线程使用返回的法代器遍历元素的过程中， 其他线程没有对list 进行增删改，那么snapshot 本身就是list 的array ， 因为它们是引用关系。但是如果在遍历期间其他线程对该list 进行了增删改，那么snapshot 就是快照了，因为增删改后list 里面的数组被新数组替换了，这时候老数组被snapshot 引用。

3.6.1 弱一致性迭代器代码验证

package com.example.demo.thread;

import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * @author haoll
 * @date 2021/1/14.
 */
public class CopyList {

    private  static  CopyOnWriteArrayList<Integer> list;

    public static void main(String[] args) {
        list = new CopyOnWriteArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        //获取迭代器
        Iterator<Integer> itr = list.iterator() ;
        MyThread myThread = new MyThread();
        
        myThread.start();
        
        try {
            //需要注意的是，获取迭代器的操作必须在子线程操作之前进行。所以在这停一会
            //不然会出现ConcurrentModificationException 并发修改异常。
            Thread.sleep(5000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        while ( itr.hasNext () ) {
            System.out.println(itr.next());
        }
    }


    static  class MyThread extends Thread{

        @Override
        public void run(){
            list.remove(1);

        }
    }
}

4. 面试题

4.1 CopyOnWriteArrayList为什么并发安全且性能比Vector好

Vector是增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获取锁，性能就会大大降低，而CopyOnWriteArrayList只是在增删改上加ReentrantLock独占锁，但是读操作不加锁，支持并发读，CopyOnWriteArrayList支持读多写少的情况

4.2 CopyOnWriteArrayList使用的场景

它适用于处理“读多写少”的并发场景。在使用的时候需要考虑如下两个方面

1.内存的使用由于CopyOnWriteArrayList使用了“写时复制”，所以在进行写操作的时候，内存里会同时存在两个array数组，如果数组内存占用的太大，那么可能会造成频繁GC,所以CopyOnWriteArrayList并不适合大数据量的场景。

2.数据一致性CopyOnWriteArrayList只能保证数据的最终一致性，不能保证数据的实时一致性——读操作读到的数据只是一份快照。所以如果希望写入的数据可以立刻被读到，那CopyOnWriteArrayList并不适合。

4.3 弱一致性的迭代器原理是怎么样的

CopyOnWriteArrayList对元素进行迭代时，仅仅返回一个当前内部数组的快照，也就是说，如果此时有其它线程正在修改元素，并不会在迭代中反映出来，因为修改都是在新数组中进行的。可以看到，上述iterator方法返回一个迭代器对象——COWIterator，COWIterator的迭代是在旧数组上进行的，当创建迭代器的那一刻就确定了，所以迭代过程中不会抛出并发修改异常——ConcurrentModificationException。另外，迭代器对象也不支持修改方法，全部会抛出UnsupportedOperationException异常。这也说明获取迭代器元素时，其它线程对list进行增删改不可见，因为他们操作的是两个不同的数组，这就是弱一致性。