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(安全失败)。