JUC并发编程18 CopyOnWriteArrayList源码也就够看2分钟

1、CopyOnWriteArrayList概述

CopyOnWriteArrayList相当于线程安全的ArrayList，底层是一个可变数组。

特点如下：

1. 线程安全：基于ReentrantLock实现同步；
2. add/set/remove操作均是基于数组的copy进行；
3. 迭代器进行遍历的速度很快，不会与其他线程发生冲突；
4. 在迭代器上不允许进行的元素更改操作（remove、set和add），因为迭代器依赖于不变的数组快照。

适用于List 大小通常很小，只读操作远多于可变操作，并且需要在遍历期间防止线程冲突。

2、原理 / 源码

在⼤多数的应⽤场景中，读操作的⽐例远远⼤于写操作。当执⾏读操作的时候，对数据是没有修改的，所以，⽆须对数据进⾏加锁操作。⽽针对于写操作的场景中，则需要加锁来保证数据的正确性。

因此，CopyOnWriteArrayList基于volatile关键字 ReentrantLock 实现互斥访问、保证线程安全性。

• 内部采用数组存储数据，并且数据被volatile修饰，并且在add/set/remove操作是都会新建一个数组，操作数据都体现在新数组中。操作数据完成之后会将新数组的引用赋值给volatile数组。
  • 保存数据的数组array采用volatile修饰，保证了array在线程之间的可见性。当写操作完成后，读操作可以立即感知到新数组的引用。
  • 这也是为什么这个List叫CopyOnWrite的原因。
• 因为操作数据都需要新建一个数组，所以它的数据操作效率不高；但是在遍历的时候，效率比较高，并且写操作也不会阻塞读的操作。
  • 写的过程中，从旧数据中读取；保证写数据的同时不影响读数据操作。
• 在add/set/remove操作数据时，都会先获取互斥锁ReentrantLock，数据操作完毕之后，再释放互斥锁，以达到线程安全的效果。

1）构造函数

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    /**
     * 监视器锁
     */
    final transient Object lock = new Object();

    /** 一个缓存数组，使用volatile修饰。 */
    private transient volatile Object[] array;

    /**
     * Gets the array.  Non-private so as to also be accessible
     * from CopyOnWriteArraySet class.
     */
    final Object[] getArray() {
        return array;
    }

    /**
     * Sets the array.
     */
    final void setArray(Object[] a) {
        array = a;
    }
}

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

public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        elements = c.toArray();
        if (c.getClass() != java.util.ArrayList.class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}

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

• CopyOnWriteArrayList的主体是volatile修饰Object[]；线程安全由互斥锁ReentrantLock保证。
• 并且由于数组也被transient关键字修饰，所以array数组不会被自动序列化。

2、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;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

方法解析：

• 执⾏写操作时，⾸先进⾏lock加锁，然后复制原数组创建⼀个⻓度加1的新数组，即：副本数组；
  • 当操作新增操作完毕后，将副本数组替换旧的数组。
  • 由于array是volatile修饰的，所以替换后，array在多线程之间是可⻅的。
• 带来的效果就是：
  • 执⾏写操作的时候，针对的是副本数组；
  • 而读操作，⼀直是针对着原数组；
  • 以此做到写操作不会阻塞读操作；

3）get()

//根据index直接获取数组元素
public E get(int index) {
    return elementAt(getArray(), index);
}

读操作非常简单，就是以不加锁的方式从数组中获取对应下标为index的元素。

4）remove()

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();
    }
}

方法解析：

• 只要操作数组中的数据，都是先加互斥锁ReentrantLock。
• 如果被删除的是最后一个元素，则直接通过Arrays.copyOf()进行处理，截取旧数组的前array.length - 1，实际也是新建了一个数组。
• 否则，直接新建一个数组，将旧数组以index为界限，分两块（不包括index位置的数据）拷贝到新数组中。
• 操作完成时，更新volatile数组的引用，释放互斥锁。

5）iterator()

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

基于COWIterator进行遍历。

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

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

    /**
     * Not supported. Always throws UnsupportedOperationException.
     * @throws UnsupportedOperationException always; {@code remove}
     *         is not supported by this iterator.
     */
    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
     * Not supported. Always throws UnsupportedOperationException.
     * @throws UnsupportedOperationException always; {@code set}
     *         is not supported by this iterator.
     */
    public void set(E e) {
        throw new UnsupportedOperationException();
    }

    /**
     * Not supported. Always throws UnsupportedOperationException.
     * @throws UnsupportedOperationException always; {@code add}
     *         is not supported by this iterator.
     */
    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;
    }
}

从COWIterator源码可以看出：CopyOnWriteArrayList的迭代器中不支持修改元素的操作。

• 因为迭代器的remove()、set()、add()操作，COWIterator都会抛出异常UnsupportedOperationException。

另外，CopyOnWriteArrayList迭代器不会抛出ConcurrentModificationException异常，因此它不是fail-fast（快速失败），而是fail-safe（安全失败）。

这篇好文章是转载于：学新通技术网