CopyOnWriteArrayList源码分析

提到CopyOnWriteArrayList，就不得不另外带上CopyOnWriteArraySet。

声明：源码是基于JDK1.8的。

基本思想是一旦对容器有修改，那么就“复制”一份新的集合，在新的集合上修改，然后将新集合复制给旧的引用。当然了这部分少不了要加锁。显然对于CopyOnWriteArrayList/CopyOnWriteArraySet来说最大的好处就是“读”操作不需要锁了。

CopyOnWriteArrayList是ArrayList 的一个线程安全的变体，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。 这一般需要很大的开销，但是当遍历操作的数量大大超过可变操作的数量时，这种方法可能比其他替代方法更 有效。在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时，它也很有用。“快照”风格的迭代器方法在创建迭代器时使用了对数组状态的引用。此数组在迭代器的生存期内不会更改，因此不可能发生冲突，并且迭代器保证不会抛出 ConcurrentModificationException。创建迭代器以后，迭代器就不会反映列表的添加、移除或者更改。在迭代器上进行的元素更改操作（remove、set 和 add）不受支持。这些方法将抛出 UnsupportedOperationException。

下面上源码

继承结构

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

属性

    /** The lock protecting all mutators */
    //私有变量 lock锁
    final transient ReentrantLock lock = new ReentrantLock();
    
    //多线程可见的object数组array
    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;

底层还是基于数组来实现的，只是此时的数组采用volatile来修饰，来保证内存的一致性，即一个线程对array的修改对另一个线程可见，但不是立即可见。

构造函数

    //创建一个空的Object数组
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }
    
    //set方法
    final void setArray(Object[] a) {
        array = a;
    }

    //
    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);
    }
    
    //创建一个指定类集合的拷贝
    public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

方法

get方法

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

利用的数组的不可变性，get方法的操作数组都是某一时刻array的镜像。这样在高并发的情况下get方法和其它线程对该List的访问(无论是读操作还是写操作)都不会产生冲突。

contains/indexOf

    public boolean contains(Object o) {
        Object[] elements = getArray();
        return indexOf(o, elements, 0, elements.length) >= 0;
    }
    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)
                    return i;
        } else {
            for (int i = index; i < fence; i++)
                if (o.equals(elements[i]))
                    return i;
        }
        return -1;
    }

可见也没有加锁，这些都是读的操作。可变操作如add/set/remove，这些都会导致数组内的元素发生变化。可变操作都是采用的如下的思想：

1. 加锁
2. 将原来的数组copy一份到新数组中，然后修改
3. 将旧的引用array指向新数组。
4. 释放锁

那我们接着看源码。

add(E e)

    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(int index, E element) 

    public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            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 {
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            newElements[index] = element;
            setArray(newElements);
        } finally {
            lock.unlock();
        }
    }

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

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;
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

addIfAbsent(E e) 

    public boolean addIfAbsent(E e) {
        Object[] snapshot = getArray();
        return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
            addIfAbsent(e, snapshot);
    }

    /**
     * A version of addIfAbsent using the strong hint that given
     * recent snapshot does not contain e.
     */
    private boolean addIfAbsent(E e, Object[] snapshot) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] current = getArray();
            int len = current.length;
            if (snapshot != current) {
                // Optimize for lost race to another addXXX operation
                int common = Math.min(snapshot.length, len);
                for (int i = 0; i < common; i++)
                    if (current[i] != snapshot[i] && eq(e, current[i]))
                        return false;
                if (indexOf(e, current, common, len) >= 0)
                        return false;
            }
            Object[] newElements = Arrays.copyOf(current, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

 下面看看CopyOnWriteArraySet类

CopyOnWriteArraySet类

因为，CopyOnWriteArraySet里面有一个CopyOnWriteArrayList的引用，即CopyOnWriteArraySet类里面的内部实现全部是委托给CopyOnWriteArrayList来实现的，只是额外的封装了下。

继承结构

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable

属性

private static final long serialVersionUID = 5457747651344034263L;

private final CopyOnWriteArrayList<E> al;

构造方法

    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }

    public CopyOnWriteArraySet(Collection<? extends E> c) {
        if (c.getClass() == CopyOnWriteArraySet.class) {
            @SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =
                (CopyOnWriteArraySet<E>)c;
            al = new CopyOnWriteArrayList<E>(cc.al);
        }
        else {
            al = new CopyOnWriteArrayList<E>();
            al.addAllAbsent(c);
        }
    }

其他方法都是通过CopyOnWriteArrayList实现的。比如下面的代码：

    public boolean add(E e) {
        return al.addIfAbsent(e);
    }
    public boolean remove(Object o) {
        return al.remove(o);
    }
    

因为是set，所有没有什么indexOf，set，get方法等。由上面的源码可见，确实是通过引用实现的。所以实现思路也就清晰可见了。