CopyOnWriteArrayList源代码阅读器

java.util.concurrent在相应的并发集合的包中定义的通用集合类,为了有效地处理并发场景。间CopyOnWriteArrayList它是合适ArrayList。顾名思义CopyOnWrite,当写副本,在这里写下包含集合改变操作,将创建一个副本。

CopyOnWriteArrayList的实现

类的定义

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
能够看到没有继承不论什么子类,实现接口和ArrayList类似。

关键属性

/** The lock protecting all mutators */
transient final ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private volatile transient Object[] array;
相同是採用数组方式实现,多了一个volatile声明,用于保证线程可见性。没有size声明表示实际包括元素的大小。多了一个ReentrantLock对象声明。

常见方法

构造方法

public CopyOnWriteArrayList() {
    setArray(new Object[0]); //默认创建一个空数组
}
public CopyOnWriteArrayList(Collection<? extends E> c) {
	Object[] 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);
}
size方法,直接返回数组大小,说明array数组仅仅包括实际大小的空间

public int size() {
        return getArray().length;
}
get方法,和ArrayList中类似,只是没有index的范围推断

public E get(int index) {
        return (E)(getArray()[index]);
}
add方法,能够看到不管是在尾部还是指定位置加入。都有锁定和解锁操作。在设置值之前都先将原先数组拷贝一份并扩容至size+1大小。

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);//拷贝array属性,并扩展为length+1大小
	    newElements[len] = 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;
	    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];
			//elements[0,index) ---> newElements[0,index)
			System.arraycopy(elements, 0, newElements, 0, index);
			//elements[index,len) --> newElements[index+1,len+1)
			System.arraycopy(elements, index, newElements, index + 1,
					 numMoved);
	    }
	    newElements[index] = element;
	    setArray(newElements);
	} finally {
	    lock.unlock();
	}
}
set方法,ArrayList中set方法直接改变数组中相应的引用,这里须要拷贝数组然后再设置。

(else那个分支没看懂,为什么值没有改变还须要设置来保证volatile写语义)

public E set(int index, E element) {
	final ReentrantLock lock = this.lock;
	lock.lock();
	try {
	    Object[] elements = getArray();
	    Object oldValue = 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 (E)oldValue;
	} finally {
	    lock.unlock();
	}
}
remove(int)方法,和指定位置加入类似,须要拷贝[0,index)和[index+1,len)之间的元素

public E remove(int index) {
	final ReentrantLock lock = this.lock;
	lock.lock();
	try {
	    Object[] elements = getArray();
	    int len = elements.length;
	    Object oldValue = elements[index];
	    int numMoved = len - index - 1;nt
	    if (numMoved == 0) //删除最后一个元素
			setArray(Arrays.copyOf(elements, len - 1));
	    else {
			Object[] newElements = new Object[len - 1];
			//elements[0,index) --> newElements[0,index)
			System.arraycopy(elements, 0, newElements, 0, index);
			//elements[index+1,len) --> newElements[index,len-1)
			System.arraycopy(elements, index + 1, newElements, index,
					 numMoved);
			setArray(newElements);
	    }
	    return (E)oldValue;
	} finally {
	    lock.unlock();
	}
}
remove(Object)方法,分配一个len-1大小的新数组。遍历原来数组,假设找到则将原来数组以后的元素复制到新数组中并将list设置为新数组,否则直接给新数组赋值上原来数组。

public boolean remove(Object o) {
	final ReentrantLock lock = this.lock;
	lock.lock();
	try {
	    Object[] elements = getArray();
	    int len = elements.length;
	    if (len != 0) {
		// Copy while searching for element to remove
		// This wins in the normal case of element being present
		int newlen = len - 1;
		Object[] newElements = new Object[newlen];

		for (int i = 0; i < newlen; ++i) {
		    if (eq(o, elements[i])) {
			// found one;  copy remaining and exit
			for (int k = i + 1; k < len; ++k)
			    newElements[k-1] = elements[k];
			setArray(newElements);
			return true;
		    } else
			newElements[i] = elements[i];
		}

		// special handling for last cell
		if (eq(o, elements[newlen])) {
		    setArray(newElements);
		    return true;
		}
	    }
	    return false;
	} finally {
	    lock.unlock();
	}
 }

迭代器的实现

ArrayList中迭代器支持fast fail,一旦检測到遍历过程中发送了改动则会抛出ConcurrentModificationException;CopyOnWriteArrayList的迭代器因为改动的时候都会又一次copy一份数组,因此不存在并发改动问题。也不会抛出ConcurrentModificationException。

相同支持单向和双向迭代器,其iterator和listIterator方法都是通过内部类COWIterator创建。仅仅是前者返回接口限定为单向迭代Iterator<E>。

COWIterator定义

/** Snapshot of the array **/
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;
}
iterator和listIterator中会传递当前数组的引用和cursor(无參方法为0,有參数方法为相应值)

常见方法

public boolean hasNext() {
    return cursor < snapshot.length;
}
public boolean hasPrevious() {
    return cursor > 0;
}
public E next() {
	if (! hasNext())
        throw new NoSuchElementException();
	return (E) snapshot[cursor++];
}
public E previous() {
	if (! hasPrevious())
        throw new NoSuchElementException();
	return (E) snapshot[--cursor];
}
另外其它add、remove和set改动容器的方法都没有实现,直接throw new UnsupportedOperationException();

总结

1. CopyOnWriteArrayList的迭代器保留一个运行底层基础数组的引用,这个数组当前位于迭代器的起始位置,因为基础数组不会被改动(改动都是复制一个新的数组),因此对其同步仅仅须要保证数组内容的可见性。多个线程能够同一时候对这个容器进行迭代。而不会彼此干扰或者与改动容器的线程互相干扰。

不会抛出CocurrentModificationException。而且返回元素与创建迭代器创建时的元素全然一致。不必考虑之后改动操作带来影响。

2. 每次改动容器都会复制底层数组,这须要一定开销,特别是容器规模较大。仅当迭代操作远远多于改动操作时,才应该使用CopyOnWriteArrayList。




版权声明:本文博主原创文章。博客,未经同意不得转载。

原文地址:https://www.cnblogs.com/zfyouxi/p/4869121.html