源码剖析之CopyOnWriteArrayList

CopyOnWriteArrayList：jdk1.5新增的线程安全的ArrayList实现。
使用场景：读取频繁，写较少。
理由：底层的安全性 本质上是依赖于线程读取的数据副本来实现的。因此每次写都是要复制底层数组数据的，如果写频繁势必会造成大量的性能消耗。

如果写非常频繁，那么可以根据实际情况选择：vector 或者Collections.synchronizedList获取同步保证。
1、底层的支持数据接口是数组，volatile 限制了array对象的可见性。
private volatile transient Object[] array;

2、查询类函数的线程安全保证。由于查询，本质上是是不会变动list的底层数据结构的，也就可以认为查询类的操作，不需要加锁，但是这样不能保证其他的写操作不会变动底层数组。因此不需要加锁的另外一个前提是：获取到的底层数组是不可变的。如果数组可变，比如删除一个对象或者清空就可以导致IndexOutOffException，这样多个线程都共享了底层的array数据，自然不是线程安全的。

特别代码：

/**
getArray()返回的引用是事实上不可变的，如果没有这个保证，那么这个操作不可能是线程安全
*/
public int size() {
        return getArray().length;
}

/**
有和size方法同样的先决条件
*/
public boolean contains(Object o) {
        Object[] elements = getArray();
        return indexOf(o, elements, 0, elements.length) >= 0;
}

//同上
public int indexOf(Object o) {
        Object[] elements = getArray();
        return indexOf(o, elements, 0, elements.length);
}

3、底层数据返回类的线程安全保证。典型的的是toArray方法，由于toArray方法返回的数组时原始数组的copy，所以是安全的线程发布。也即当前对象的toArray 方法在任何线程中返回的对象都是线程内封闭，自然是安全的。此方法的另外一个先决条件：返回的elements是事实不可变的。

public Object[] toArray() {
        Object[] elements = getArray();
	return Arrays.copyOf(elements, elements.length);
}

4、修改底层数组的操作。

/**
 变更底层数组的操作
*/
public E set(int index, E element) {
	final ReentrantLock lock = this.lock;
	/*并发写操作此处阻止了，必须等此操作完成，请他并发写操作才能继续！！！ 
当然读操作可以继续喽，读的底层数组的有两种可能性：1、此次写之前的数组；2、此次写之后的数组。*/
	lock.lock();
	try {
		 //指向底层的引用
	    Object[] elements = getArray();
	    Object oldValue = elements[index];

	    if (oldValue != element) {
		int len = elements.length;
		//此处相当于从原始的数据copy进新的数组
		Object[] newElements = Arrays.copyOf(elements, len);
		//在新的数组赋值，老的数组没有变啊！！，所有老的数组是没有改变的。
		newElements[index] = element;
		//把原始的引用指向新的数组地址（注意：此处的原来的数组没有改变，从而给getArray()返回的底层数组是：事实不变的）
		setArray(newElements);
		 /*如果此时 有线程读取底层的数组，那么获取的将是新生成的数组，不过这没有关系
（事实上我们可以参考ArrayList 的所有的方法加synchronized的效果， 来体会此处的逻辑）*/
	    } else {
	  //此处我没有看懂为什么要再次设置下？ 我认为没有必要，请大侠指点下！！！
		// Not quite a no-op; ensures volatile write semantics
		setArray(elements);
	    }
	    return (E)oldValue;
	} finally {
	    lock.unlock();
	}
}



/**
删除一个元素的线程安全保证
*/
public E remove(int index) {
	final ReentrantLock lock = this.lock;
	lock.lock();
	try {
		 //此处获取的引用指向的底层数组是不会变动的！！！ 因为：前面的lock.lock()
	    Object[] elements = getArray();
	    int len = elements.length;
	    Object oldValue = elements[index];
	    int numMoved = len - index - 1;
	    if (numMoved == 0)
	    //如果删除的是最后一个记录，赋那么直接复制前 n-1 的数组数据。setArray（Arrays.copyOf ... ）
 此操作保证了原来的数组没有变，其他线程的非更改底层数据的操作获取到的array都是不变的！！
		  setArray(Arrays.copyOf(elements, len - 1));
	    else {
		Object[] newElements = new Object[len - 1];
		//复制老数组的数据到 newElements 里
		System.arraycopy(elements, 0, newElements, 0, index);
		System.arraycopy(elements, index + 1, newElements, index,
				 numMoved);
				 //更改当前对象的底层数组，底层数组由于volatile 修饰，保证了内存的可见性！！！
		setArray(newElements);
	    }
	    return (E)oldValue;
	} finally {
	    lock.unlock();
	}
}


//结合以上分析，很容易分析出此操作的线程安全性！
public boolean addIfAbsent(E e) {
	final ReentrantLock lock = this.lock;
	lock.lock();
	try {
	    // Copy while checking if already present.
	    // This wins in the most common case where it is not present
	    Object[] elements = getArray();
	    int len = elements.length;
	    Object[] newElements = new Object[len + 1];
	    for (int i = 0; i < len; ++i) {
		if (eq(e, elements[i]))
		    return false; // exit, throwing away copy
		else
		    newElements[i] = elements[i];
	    }
	    newElements[len] = e;
	    setArray(newElements);
	    return true;
	} finally {
	    lock.unlock();
	}
    }

5、迭代器 的安全性分析。

public ListIterator<E> listIterator() {
        //对快照的的迭代
        return new COWIterator<E>(getArray(), 0);
    }

private static class COWIterator<E> implements ListIterator<E> {
        /** Snapshot of the array 
        final 修饰的，保证了迭代的底层数据不会动！
        **/
        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;
        }
  .... 
}

总结：CopyOnWriteArrayList 的安全性保证：
1、写线程的操作加锁（保证多个写线程不会有操作被覆盖）
2、写线程操作的底层数组复制（保证线程读取操作不会在其他线程写操作前后发生线程不安全的操作）
3、获取底层数组时的 底层数组的复制（保证返回的底层数据不在多个线程中共享，含义与2一致）。
4、volatile修饰 保证底层数组的线程可见性。（保证线程操作happened before的逻辑）

以上是我的理解，有理解错误点，请指出！