CopyOnWriteArrayList源码分析

一、CopyOnWriteArrayList

1、概述

Copy-On-Write简称COW，是一种用于集合的并发访问的优化策略。对它的理解:它是一个线程安全的集合实现类，它的写入操作(比如add,get,remove方法)内部都有ReentrantLock，加锁后保证了线程安全。当我们往一个集合容器中写入元素时（添加、修改、删除），并不会直接在集合容器中写入，而是先将当前集合容器进行Copy，复制出一个新的容器，然后新的容器里写入元素，写入操作完成之后，再将原容器的引用指向新的容器。

2、优点:

实现对CopyOnWrite集合容器写入操作时的线程安全，但同时并不影响进行并发的读取操作。所以CopyOnWrite容器也是一种读写分离的思想。从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发集合容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。

CopyOnWriteArrayList相当于线程安全的ArrayList，内部存储结构采用Object[]数组，线程安全使用ReentrantLock实现，允许多个线程并发读取，但只能有一个线程写入。

3、CopyOnWriteArrayList内部源码分析

构造方法
 

public class CopyOnWriteArrayList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
	
	
    final transient ReentrantLock lock = new ReentrantLock();
 
    private transient volatile Object[] array;
 
    final Object[] getArray() {
        return array;
    }
    //返回新数组为传进去的数组
    final void setArray(Object[] a) {
        array = a;
    }
 
    //无参构造,默认数组长度为0
    public CopyOnWriteArrayList() {
		//调用setArray()方法
        setArray(new Object[0]);
    }
 
	//有参构造:参数为Collection类型的集合
    public CopyOnWriteArrayList(Collection c) {
		//定义一个数组
        Object[] elements;
		//如果这个集合的class对象和CopyOnWriteArrayList的class对象相同
        if (c.getClass() == CopyOnWriteArrayList.class)
            //存入数组
            elements = ((CopyOnWriteArrayList)c).getArray();
        else {
			//如果不同，将集合转换为数组
            elements = c.toArray();
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
			//如果这个数组的class对象和数组的class对象不同
			//复制原数组到新的数组
            if (elements.getClass() != Object[].class)
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
		//把原数组的引用指向一个新的数组
        setArray(elements);
    }

 set():

public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
			//获取集合中的数组
            Object[] elements = getArray();
			//根据下标获得原来数组的值
            E oldValue = get(elements, index);
			//如果原本的值不等于要set的值
            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();
        }
    }

add(E e) :末尾添加

public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
			//获取原来的数组
            Object[] elements = getArray();
			//获取原来数组的长度
            int len = elements.length;
			//创建一个新数组按照原数组长度+1复制
            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;
			//数组长度-下标-1=0说明在数组最末尾添加
            int numMoved = len - index-1;
			//如果要在数组的最末尾的添加
            if (numMoved == 0)
                //复制原来数组，长度+1
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                //不是末尾添加，创建一个原数组长度+1的新数组
                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();
        }
    }

removeRange(int fromIndex, int toIndex)：删除指定范围的元素

void removeRange(int fromIndex, int toIndex) {
		final ReentrantLock lock = this.lock;
		lock.lock();
		try {
            //获取原数组
			Object[] elements = getArray();
            //获取原数组长度
			int len = elements.length;
 
            //判断是否下标越界
			if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
				throw new IndexOutOfBoundsException();
 
			// 计算新数组长度
			int newlen = len - (toIndex - fromIndex);
            //等于0说明删除到数组最末尾
			int numMoved = len - toIndex;
			if (numMoved == 0)
				//直接复制新数组开始下标之前的元素
				setArray(Arrays.copyOf(elements, newlen));
			else {
				// 新建一个数组，长度为newlen的
				Object[] newElements = new Object[newlen];
                //复制到新数组开始下标前
				System.arraycopy(elements, 0, newElements, 0, fromIndex);
                //复制结束下标之后的元素
				System.arraycopy(elements, toIndex, newElements, fromIndex, numMoved);
                //存入新数组
				setArray(newElements);
			}
		} finally {
			lock.unlock();
		}
	}

retainAll(Collection c)：修改当前集合为传入集合与当前集合的交集

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];
			
                for (int i = 0; i < len; ++i) {
			//取出原数组所有元素
                    Object element = elements[i];
			//判断传入集合中是否含这个元素
                    if (c.contains(element))
				//如果有，加入新数组
                        temp[newlen++] = element;
                }
			//判断新数组长度是否与原数组长度相同
                if (newlen != len) {
			//如果不相同，复制新数组，存入新定义的数组
                    setArray(Arrays.copyOf(temp, newlen));
			//返回true
                    return true;
                }
            }
		//返回false
            return false;
        } finally {
		//释放锁
            lock.unlock();
        }
    }

clear():清空集合中的元素

  public void clear() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            //新数组长度为0
            setArray(new Object[0]);
        } finally {
            lock.unlock();
        }
    }

addAll():在原来集合的指定下标位置添加新集合

 public boolean addAll(int index, Collection c) {
		// 指定集合转化成数组
        Object[] cs = c.toArray();
		// 加锁
        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);
            // 判断新集合是否为空
			if (cs.length == 0)
                return false;
            int numMoved = len - index;
            Object[] newElements;
            //如果numMoved等于0，则代表在原集合末尾添加
            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();
        }
}