[数据结构与算法]CopyOnWriteArrayList

CopyOnWrite指在“写”的时候，不是直接“写”源数据，而是把数据拷贝一份进行修改，再通过悲观 锁或者乐观锁的方式写回。

拷贝一份修改是为了在“读”的时候不加锁

CopyOnWriteArrayList

CopyOnWriteArrayList的核心数据结构是一个数组 array

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess,
Cloneable, java.io.Serializable {
	// ...
    private volatile transient Object[] array;
}

它的几个读方法都没有加锁

final Object[] getArray() {
        return array;
}
//
public E get(int index) {
    return elementAt(getArray(), index);
}
public boolean isEmpty() {
    return size() == 0;
}
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
public int indexOf(Object o) {
    Object[] es = getArray();
    return indexOfRange(o, es, 0, es.length);
}
private static int indexOfRange(Object o, Object[] es, int from, int to){
    if (o == null) {
        for (int i = from; i < to; i++)
            if (es[i] == null)
                return i;
    } else {
        for (int i = from; i < to; i++)
            if (o.equals(es[i]))
                return i;
	}
	return -1; 
}

写方法加了锁

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    //获得锁
    lock.lock();
    try {
    	//获得array数组
        Object[] elements = getArray();
        //获得数组长度
        int len = elements.length;
        //拷贝之前的数组，并把新数组的长度设置为旧数组的长度+1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //把新加入的元素放在最后
        newElements[len] = e;
        //将array变量指向新数组
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

其他写方法和add类似都是加的锁

CopyOnWriteArraySet

CopyOnWriteArraySet 就是用 Array 实现的一个Set，保证所有元素都不重复。其内部是封装的一个CopyOnWriteArrayList。

public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements
java.io.Serializable {
	// 封装的CopyOnWriteArrayList
	private final CopyOnWriteArrayList<E> al;
	
	public CopyOnWriteArraySet() {
	        al = new CopyOnWriteArrayList<E>();
	}
	public boolean add(E e) {
		return al.addIfAbsent(e); // 不重复的加进去
	} 

	//CopyOnWriteArrayList中的方法
    public boolean addIfAbsent(E e) {
       Object[] snapshot = getArray();
       //要添加的元素e在CopyOnWriteArrayList是否存在，不存在的话就添加
       return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
           addIfAbsent(e, snapshot);
    }

	
	
}