并发编程学习之写时复制CopyOnWriteArrayList

目录

一、简介

二、常用API

三、使用示例

四、源码阅读

五、总结

一、简介

CopyOnWriteArrayList是JDK1.5时JUC包引入了一个新的集合工具类，方便在并发环境下使用List集合。

public class CopyOnWriteArrayList<E>
extends Object
implements List<E>, RandomAccess, Cloneable, Serializable

可以看到，CopyOnWriteArrayList实现了List接口和随机访问接口RandomAccess。

CopyOnWriteArrayList是ArrayList的线程安全变体，CopyOnWriteArrayList，运用了一种“写时复制”的思想，其中所有的可变操作(添加、设置值等)都是通过创建底层数组的新副本来实现的。

实际项目中，一般都是“读多写少”的场景比较多，CopyOnWriteArrayList就非常适合这样的场景。

通俗理解就是： 当我们需要修改（增/删/改）列表中的元素时，不会直接对原有数组进行修改，而是复制多一个数组的副本，然后在新的副本上进行修改，修改完成之后，再将引用从原列表指向新列表。这样做的好处是读/写是不会冲突的，可以并发进行，读操作还是在原列表，写操作在新列表。仅仅当有多个线程同时进行写操作时，才会进行同步。

二、常用API

【a】构造方法

【b】常用方法

可以看到，其中很大部分的方法都跟我们熟悉的ArrayList作用一样，用法也一样，唯一的区别就是底层实现稍微有点区别。

三、使用示例

下面通过一个简单的示例说明CopyOnWriteArrayList的使用方法：

public class T12_CopyOnWriteArrayList {

    private static List<String> list = new CopyOnWriteArrayList<>();

    static {
        for (int i = 0; i < 10; i++) {
            list.add(String.valueOf(i));
        }
    }

    public static void main(String[] args) {
        new Thread(() -> {
            for (int i = 100; i < 110; i++) {
                list.add(String.valueOf(i));
                try {
                    TimeUnit.MILLISECONDS.sleep(500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
    }

}

其中一次的运行结果：

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 100 

在程序中，有一个线程向CopyOnWriteArrayList中添加一个元素，并且两次使用了迭代器，迭代器输出的内容都是生成迭代器时，CopyOnWriteArrayList的Object数组的快照的内容，在迭代的过程中，往CopyOnWriteArrayList中添加元素也不会抛出异常。

四、源码阅读

【a】重要属性说明

/** 可重入锁，全局独占锁 */
final transient ReentrantLock lock = new ReentrantLock();

/** 对象数组，只能通过getArray/setArray访问. */
private transient volatile Object[] array;

final Object[] getArray() {
    return array;
}

final void setArray(Object[] a) {
    array = a;
}

【b】三个构造方法：最终都是创建一个数组，并通过setArray方法赋给array字段

/**
 * 创建一个空列表
 */
public CopyOnWriteArrayList() {
    //创建一个空对象数组赋值给array
    setArray(new Object[0]);
}

/**
 * 创建包含指定集合的元素的列表，按集合的迭代器返回元素的顺序排列
 */
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    //如果CopyOnWriteArrayList类型,直接设置
    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)
            //通过Arrays.copyOf将elements转换成Object[]类型
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    //内部array引用指向新数组
    setArray(elements);
}

/**
 * 创建包含给定数组副本的列表
 */
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

/**
 * 设置数组.
 */
final void setArray(Object[] a) {
    array = a;
}

【c】add(E e)、add(int index, E element)：首先会进行加锁，保证只有一个线程能进行修改；然后会创建一个新数组（大小为n+1），并将原数组的值复制到新数组，新元素插入到新数组的最后；最后，将字段array指向新数组。

/**
 * 将指定的元素附加到此列表的末尾
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        //获取当前对象数组array
        Object[] elements = getArray();
        //数组长度
        int len = elements.length;
        //通过Arrays.copyOf数组拷贝出新数组副本
        //可见，CopyOnWriteArrayList对元素的修改不会影响原数组的值，全是在副本上修改
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //将元素插入到数组最后一个下标位置
        newElements[len] = e;
        //内部array引用指向新数组
        setArray(newElements);
        //返回true
        return true;
    } finally {
        lock.unlock();
    }
}

/**
 * 将指定元素插入到列表中的指定位置。将当前位于该位置的元素(如果有)和任何后续元素向右移动(将一个元素添加到它们的索引中).
 */
public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        //获取当前对象数组array
        Object[] elements = getArray();
        //数组长度
        int len = elements.length;
        //如果索引大于数组长度或者小于0，抛出数组下标越界异常
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+len);
        //新数组                                        
        Object[] newElements;
        //需要移动元素的长度
        int numMoved = len - index;
        if (numMoved == 0)
            //不需要移动，说明在最后面添加
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            //创建长度+1的对象数组
            newElements = new Object[len + 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            //将原先index索引处后面的元素都往后移一位
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        //替换index索引处的元素值
        newElements[index] = element;
        //内部array引用指向新数组
        setArray(newElements);
    } finally {
        lock.unlock();
    }
}

【d】get(Object[] a, int index)、get(int index)

@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
    return (E) a[index];
}

public E get(int index) {
    //通过数组下标取出对应的值
    //get方法并没有加锁,因为是操作的原数组的值，其他修改操作都是操作新复制出来的数组副本
    return get(getArray(), index);
}

【e】remove(int index)、remove(Object o)、remove(Object o, Object[] snapshot, int index)

/**
 * 删除列表中指定位置的元素。将任何后续元素向左移动(从它们的索引中减去1)。返回从列表中删除的元素。
 */
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        //获取当前对象数组array
        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);
            //原先index处后面的元素都往前移一位
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            //内部array引用指向新数组
            setArray(newElements);
        }
        //返回删除的元素
        return oldValue;
    } finally {
        lock.unlock();
    }
}

/**
 * 从该列表中删除指定元素的第一个匹配项(如果存在)。如果此列表不包含该元素，则它将保持不变.
 */
public boolean remove(Object o) {
    Object[] snapshot = getArray();
    //根据元素值找出对应下标
    int index = indexOf(o, snapshot, 0, snapshot.length);
    return (index < 0) ? false : remove(o, snapshot, index);
}

/**
 * 一个版本的删除(对象)使用强提示，给定的最近快照在给定的索引中包含o.
 */
private boolean remove(Object o, Object[] snapshot, int index) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        //获取array
        Object[] current = getArray();
        //数组长度
        int len = current.length;
        if (snapshot != current) findIndex: {
            int prefix = Math.min(index, len);
            for (int i = 0; i < prefix; i++) {
                //挨个进行比较
                if (current[i] != snapshot[i] && eq(o, current[i])) {
                    index = i;
                    break findIndex;
                }
            }
            if (index >= len)
                return false;
            if (current[index] == o)
                break findIndex;
            index = indexOf(o, current, index, len);
            if (index < 0)
                return false;
        }
        //同样是移动数组
        Object[] newElements = new Object[len - 1];
        System.arraycopy(current, 0, newElements, 0, index);
        System.arraycopy(current, index + 1,
                         newElements, index,
                         len - index - 1);
        //内部array引用指向新数组                 
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

【f】indexOf(Object o)、indexOf(E e, int index) 、contains(Object o)

public int indexOf(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length);
}

/**
 * 返回该列表中指定元素第一次出现时的索引，从{@code index}向前搜索，如果没有找到该元素，则返回-1.
 */
public int indexOf(E e, int index) {
    Object[] elements = getArray();
    return indexOf(e, elements, index, elements.length);
}

/**
 * 如果此列表包含指定的元素，则返回true.
 */
public boolean contains(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length) >= 0;
}

/**
 * 静态版本的indexOf，允许重复调用而无需每次重新获取数组.
 * @param o 要搜索的元素
 * @param elements 数组
 * @param index 第一个搜索索引
 * @param fence 过去的最后一个索引搜索
 * @return 元素的索引，如果没有则为-1
 */
private static int indexOf(Object o, Object[] elements,
                           int index, int fence) {
    if (o == null) {
        for (int i = index; i < fence; i++)
            //循环数组元素，挨个进行比较
            if (elements[i] == null)
                //找到返回数组下标，找不到返回-1
                return i;
    } else {
        for (int i = index; i < fence; i++)
            //循环数组元素，挨个进行比较
            if (o.equals(elements[i]))
                //找到返回数组下标，找不到返回-1
                return i;
    }
    return -1;
}

【g】set(int index, E element)

/**
 * 将列表中指定位置的元素替换为指定元素
 */
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;
            //内部array引用指向新数组
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        //返回原来位置处的元素值
        return oldValue;
    } finally {
        lock.unlock();
    }
}

【h】size() 、isEmpty()

/**
 * 返回列表中元素的数目
 */
public int size() {
    return getArray().length;
}

/**
 * 如果此列表不包含元素，则返回true，否则返回false
 */
public boolean isEmpty() {
    return size() == 0;
}

【i】迭代：CopyOnWriteArrayList对元素进行迭代时，仅仅返回一个当前内部数组的快照，也就是说，如果此时有其它线程正在修改元素，并不会在迭代中反映出来，因为修改都是在新数组中进行的。

public Iterator<E> iterator() {
    //根据底层对象数组array创建COWIterator迭代器
    //迭代过程中不会抛出并发修改异常
    return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
    /** 数组快照 */
    private final Object[] snapshot;
    /** 游标，对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++];
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        if (! hasPrevious())
            throw new NoSuchElementException();
        return (E) snapshot[--cursor];
    }

    // 下一项索引
    public int nextIndex() {
        return cursor;
    }

    //前一个索引
    public int previousIndex() {
        return cursor-1;
    }

    /**
     * 不受支持的。总是抛出UnsupportedOperationException
     */
    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
     * 不受支持的。总是抛出UnsupportedOperationException
     */
    public void set(E e) {
        throw new UnsupportedOperationException();
    }

    /**
     * 不受支持的。总是抛出UnsupportedOperationException
     */
    public void add(E e) {
        throw new UnsupportedOperationException();
    }

    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        Object[] elements = snapshot;
        final int size = elements.length;
        for (int i = cursor; i < size; i++) {
            @SuppressWarnings("unchecked") E e = (E) elements[i];
            action.accept(e);
        }
        cursor = size;
    }
}

五、总结

如果之前阅读过ArrayList源码的话，CopyOnWriteArrayList的源码应该是比较轻松可以看得懂的，主要区别就是对于修改操作都加了一把全局独占锁RenentrantLock，并且是通过复制出新数组的副本来操作的，不会影响另外的线程进行读操作，但是同一个时刻只能有一个线程进行写操作。CopyOnWriteArrayList适合在“读操作多，写操作少”的场景下。

总结一下CopyOnWriteArrayList的一些优缺点：

优点：

• 在读操作多的时候，效率比较高，并发性较好；

缺点：

• 由于采用写时复制技术，在进行写操作时，需要复制多一个对象数组，如果数组过大，可能造成频繁垃圾回收，CopyOnWriteArrayList不太适合用在大数据量场景；
• CopyOnWriteArrayList只是保证数据的最终一致性，在添加到拷贝数据而还没进行替换的时候，读到的仍然是旧数据(数组快照)，所以CopyOnWriteArrayList不太适合在实时性要求高的场景；

最后

以上就是会撒娇火为你收集整理的并发编程学习之写时复制CopyOnWriteArrayList的全部内容，希望文章能够帮你解决并发编程学习之写时复制CopyOnWriteArrayList所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。