CopyOnWriteArrayList源码分析

目录

CopyOnWriteArrayList

构造方法

add()方法

remove()方法

get()方法

retainAll()方法

总结： 

---

CopyOnWriteArrayList

Copy-On-Write简称COW，是一种用于集合的并发访问的优化策略。基本思想是：当我们往一个集合容器中写入元素时（添加、修改、删除），并不会直接在集合容器中写入，而是先将当前集合容器进行Copy，复制出一个新的容器，然后新的容器里写入元素，写入操作完成之后，再将原容器的引用指向新的容器。

这样做的好处：实现对CopyOnWrite集合容器写入操作时的线程安全，但同时并不影响进行并发的读取操作。所以CopyOnWrite容器也是一种读写分离的思想。

构造方法

public class CopyOnWriteArrayList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
 
    final transient ReentrantLock lock = new ReentrantLock();
 
	// 用于保存数据的数组 volatile ：保证可见性
    private transient volatile Object[] array;
 
    // 得到数组
    final Object[] getArray() {
        return array;
    }
 
    final void setArray(Object[] a) {
        array = a;
    }
 
	// 无参构造方法：创建一个新数组，初始化长度为0
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }
 
    // 有参构造方法
    public CopyOnWriteArrayList(Collection 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)
            // 判断是否为Object[]
            if (elements.getClass() != Object[].class)
                // 复制
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        setArray(elements);
    }

add()方法

向容器中添加元素时，需要竞争锁，同一时刻最多只有一个线程可以操作。写入数据时不应该影响其他线程的读取，因此不会直接在array数组上操作，而是拷贝一个新的数组，元素设置完成后再覆盖旧数组。

public boolean add(E e) {
    // 获取锁
    final ReentrantLock lock = this.lock;
    // 手动上锁
    lock.lock();
    try {
        Object[] elements = getArray(); // 获取当前数组
        int len = elements.length; // 获取当前数组长度
 
		// 创建新数字，长度为len + 1
		// 将旧数组elements复制到新数组中
		// 返回新数组
        Object[] newElements = Arrays.copyOf(elements, len + 1); 
        newElements[len] = e; // 将元素e添加至数组末尾
        setArray(newElements); // 覆盖旧数组
        return true;
    } finally {
	// 手动解锁
    lock.unlock();
    }
}
 
public void add(int index, E element) {
	// 获取锁
    final ReentrantLock lock = this.lock;
	// 手动上锁
    lock.lock();
    try {
        Object[] elements = getArray(); // 获取当前数组
        int len = elements.length; // 获取当前数组长度
 
		// 如果下标"非法"，则抛出IndexOutOfBoundsException异常
        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();
        }
    }
 
// 一次性添加多个元素
public boolean addAll(int index, Collection c) {
    Object[] cs = c.toArray(); // 将传入的对象转换为Object类型的数组
	// 获取锁
    final ReentrantLock lock = this.lock;
	// 手动加锁
    lock.lock();
    try {
        Object[] elements = getArray(); // 获取当前数组
        int len = elements.length; // 获取当前数组长度
 
	  	// 如果下标"非法"，则抛出IndexOutOfBoundsException异常
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);
 
         if (cs.length == 0)
             return false;
            int numMoved = len - index;
            Object[] newElements;
            if (numMoved == 0)
				// 如果添加的元素位置为末尾
                newElements = Arrays.copyOf(elements, len + cs.length);
            else {
                newElements = new Object[len + cs.length];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index,
                                 newElements, index + cs.length,
                                 numMoved);
            }
			// 将目标数组复制到数组中
            System.arraycopy(cs, 0, newElements, index, cs.length);
            setArray(newElements);
            return true;
        } finally {
			// 手动解锁
            lock.unlock();
        }
    }

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)
	    	// 如果删除的是最后一个元素，则复制前len-1个元素
            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();
        }
    }

get()方法

根据指定下标，到原数组中读取元素。读取过程中不加锁，允许多个线程并发读取。但是如果读取的时候，有其它线程向集合中添加新元素，此时仍然读取到的是旧数据。因为添加操作没有对原数组加锁。

public E get(int index) {
    // 根据指定下标，从原数组中读取元素
    return get(getArray(), index);
}
 
private E get(Object[] a, int index) {
    return (E) a[index];
}

retainAll()方法

对于当前集合中的元素进行遍历，判断每个元素是否存在于参数集合中，若不存在则从当前集合中移除该元素，最终保留的就是两个集合共有的元素。

 
public boolean retainAll(Collection c) {
    if (c == null) throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray(); // 获取当前元素
            int len = elements.length; // 获取当前元素长度
            if (len != 0) {
                // temp array holds those elements we know we want to keep
                int newlen = 0;
                Object[] temp = new Object[len]; // 创建长度为len的数组
				// 遍历数组元素
                for (int i = 0; i < len; ++i) {
                    Object element = elements[i];
					// 判断当前元素在c数组中是否存在
                    if (c.contains(element))
						// 如果存在，则存入新数组中
                        temp[newlen++] = element;
                }
                if (newlen != len) {
                    setArray(Arrays.copyOf(temp, newlen));
                    return true;
                }
            }
            return false;
        } finally {
            // 手动解锁    
            lock.unlock();
        }
    }

总结： 

CopyOnWriteArrayList具有以下特性：

1. 在保证并发读取的前提下，确保了写入时的线程安全；
2. 由于每次写入操作时，进行了Copy复制原数组，所以无需扩容；
3. 适合读多写少的应用场景。由于add()、set() 、 remove()等修改操作需要复制整个数组，所以会有内存开销大的问题。
4. CopyOnWriteArrayList由于只在写入时加锁，所以只能保证数据的最终一致性，不能保证数据的实时一致性。