CopyOnWriteArrayList源码学习笔记

CopyOnWriteArrayList是JUC并发包下的一个线程安全List。对于类的作用，注释是这么写的

A thread-safe variant of {@link java.util.ArrayList} in which all mutative operations ({@code add}, {@code set}, and so on) are implemented by making a fresh copy of the underlying array ArrayList的线程安全的变体，所有的可变操作(例如add，set等)都是通过创建一个新的数组的副本来实现的

This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don’t want to synchronize traversals, yet need to preclude interference among concurrent threads 一般情况下这么搞代价有点高，适合读远远多于写的情况，或者读的时候不希望加锁的情况。

All elements are permitted, including {@code null} 所有元素都允许存放，包括null

从注释我们建立了CopyOnWriteArrayList的大致印象。它内部维护了一个object数组来存放数据，当有修改出现时，创建一个新的数组，将原数组的值和新加的值放入新数组，在此期间，读操作还是读的原数组，因此读写分离，不会出现线程竞争的场景。

set

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

我们已经知道，在往list中加元素的过程中，会同时存在新老两个数组。在数组复制之前，获取内部的锁，所有对数组进行添加的线程都得获取到这个锁，因此，对数组的修改是同步的，同一时刻只会有一个线程在修改数组，这就保证了多线程环境下写的安全。这点就跟ConcurrentHashMap不太一样了，虽然都是“线程安全”著称的集合类，但是ConcurrentHashMap并不能保证写的同步性，因为ConcurrentHashMap写的时候加的是乐观锁。

1. getArray方法获取的是当前读线程可以读到的数组，即老数组
2. 获取老数组中当前位置的元素
3. 创建新数组newElements，把老数组的值复制过去，新的元素也加进去
4. 把新数组设置为老数组，设置完之后，读线程读到的就是新的数组了

最后释放锁。

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

add方法的逻辑和set基本一样。

get

public E get(int index) {
        return get(getArray(), index);
}

get方法是不加锁的，毕竟读并不会让list的内容产生任何的变化

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

remove同样是 先拿到当前元素，如果元素不是数组的首个，那么分段复制老数组到新数组上。

移除元素也需要获取lock。删除和添加是不能由不同的线程同时进行的。

iterator

    public Iterator iterator() {
        return new COWIterator(getArray(), 0);
    }
    static final class COWIterator implements ListIterator {
    /** 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;
    }
    public void remove() {
        throw new UnsupportedOperationException();
    }
    public void set(E e) {
        throw new 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;
    }
}

CopyOnWriteArrayList自己实现了一个迭代器COWIterator，主要是为了保留当前数组的快照，防止在遍历的过程中被其他线程给重新设置了。所以很显然，CopyOnWriteArrayList不能用正常的for循环来遍历

subList

public List subList(int fromIndex, int toIndex) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
        throw new IndexOutOfBoundsException();
        return new COWSubList(this, fromIndex, toIndex);
    } finally {
        lock.unlock();
    }
}
private static class COWSubList
        extends AbstractList
        implements RandomAccess
        {
    private final CopyOnWriteArrayList l;
    private final int offset;
    private int size;
    private Object[] expectedArray;    
    // only call this holding l's lock
    COWSubList(CopyOnWriteArrayList<E> list,
               int fromIndex, int toIndex) {
        l = list;
        expectedArray = l.getArray();
        offset = fromIndex;
        size = toIndex - fromIndex;
    }
    private void checkForComodification() {
        if (l.getArray() != expectedArray)
            throw new ConcurrentModificationException();
    }
   ...
}

CopyOnWriteArrayList提供了一个subList接口，返回指定位置的子list的引用。值得注意的几点：

1. sublist返回的类型是CopyOnWriteArrayList自定义的内部类COWSubList，所以拿到结果之后强转肯定会抛异常
2. subList返回的只是一个引用，可以理解为一个适配器，和clone接口还不太一样，并没有复制原有的数组，只是持有了原list的一个引用。因此，对subList的修改也会反映到原list上。同时，subList的get，set等操作时都会先调用checkForComodification方法检查原list是否有变化

lockOffset

// Support for resetting lock while deserializing
    private void resetLock() {
        UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
    }
    private static final sun.misc.Unsafe UNSAFE;
    private static final long lockOffset;
    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> k = CopyOnWriteArrayList.class;
            lockOffset = UNSAFE.objectFieldOffset
                (k.getDeclaredField("lock"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }

lockOffset的作用是在反序列化的时候，提供一个内存地址的偏移量用来重置类内部的ReentrantLock。但是Java又没有偏移量这个玩意儿，所以需要调用UNSAEF的方法，通过c语言来实现，大致可以理解为，通过这个lockOffset来代替类持有的锁的指针，反序列化的时候就可以让其指向序列化之前的锁的地址了，UNSAFE.putObjectVolatile这个方法就是干这个事儿的。static静态代码块中，类初始化的时候lockOffset被设置为类的lock属性的fieldOffset，随后在反序列化时，（例如类中的readObject方法）通过lockOffset手动设置lock的地址。

完
文章搬运自我的简书 https://www.jianshu.com/p/badabd1beb9e