CopyOnWriteArrayList的原理及使用

78 阅读 0 评论 52 点赞

我是靠谱客的博主悲凉时光，最近开发中收集的这篇文章主要介绍CopyOnWriteArrayList的原理及使用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

程序语言中，容器是所有编程中的基础工具。这里当然也包括并发编程。

我们熟知的容器包括arraylist，map，set等。既然有了arraylist，那为何还要设计个copyonwriteArraylist。

原理

从字面意思，这个自注释的数据结构，Copy-On-Write容器即写时复制的容器。是为了并发操作避免发生同步问题而设计的。同城我们为了保证数据同步，会增加锁来保证。而CopyOnWriteArrayList是免锁容器的一种，即在可能发生同步问题的操作方法中，已经加入了同步锁机制，保证不会发生并发问题。

免锁容器的通用策略是：对容器的修改可以与读操作同时发生，只要读取者只能看到完成修改的结果即可。修改是在容器数据结构的某个部分的一个单独的副本（或整个数据副本）上执行的，并且这个副本在修改过程中是不可视的。当修改完成时，被修改的结构才会自动的与主数据结构进行交换，之后读者就能看到这个修改了。

通俗的讲就是：这个结构是读写分离的，随时可读，但是要写入操作时，则会创建一个数据副本，然后在这个副本上进行修改，所以此时多线程仍可以从原旧数据读取，读操作不会被阻塞。副本修改完成后，将原数据替换为这个副本。

有经验的开发者可能遇到过java.util.ConcurrentModificationException这个异常，在我们用容器的Iterator遍历读结构时，如果多线程同时又更改了这个容器数据，就会导致这个错误的发生。包括arraylist ，hashmap等都会发生，而由于CopyOnWriteArrayList的写时复制策略，其是不会抛出这个异常的，因此不需要编写特殊的代码去防止这种异常。

源码解读

在JDK中其源码类注释如下所示，提到了其线程安全的特点。且array变量即CopyOnWriteArrayList中存数据的变量，且可通过getArray和setArray获取、替换。

/**
* A thread-safe variant of {@link java.util.ArrayList} in which all mutative
* operations ({@code add}, {@code set}, and so on) are implemented by
* making a fresh copy of the underlying array.
*
* <p>This is ordinarily too costly, but may be <em>more</em> efficient
* than alternatives when traversal operations vastly outnumber
* mutations, and is useful when you cannot or don't want to
* synchronize traversals, yet need to preclude interference among
* concurrent threads.
The "snapshot" style iterator method uses a
* reference to the state of the array at the point that the iterator
* was created. This array never changes during the lifetime of the
* iterator, so interference is impossible and the iterator is
* guaranteed not to throw {@code ConcurrentModificationException}.
* The iterator will not reflect additions, removals, or changes to
* the list since the iterator was created.
Element-changing
* operations on iterators themselves ({@code remove}, {@code set}, and
* {@code add}) are not supported. These methods throw
* {@code UnsupportedOperationException}.
*
* <p>All elements are permitted, including {@code null}.
*
* <p>Memory consistency effects: As with other concurrent
* collections, actions in a thread prior to placing an object into a
* {@code CopyOnWriteArrayList}
* <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
* actions subsequent to the access or removal of that element from
* the {@code CopyOnWriteArrayList} in another thread.
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @since 1.5
* @author Doug Lea
* @param <E> the type of elements held in this collection
*/
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8673264195747942595L;
/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
/**
* Gets the array.
Non-private so as to also be accessible
* from CopyOnWriteArraySet class.
*/
final Object[] getArray() {
return array;
}
/**
* Sets the array.
*/
final void setArray(Object[] a) {
array = a;
}

然后我们看其对数据修改部分的源码，可以看出在add操作时，newElements 是拷贝的副本，最后的setArray即是将副本数据替换原数据的操作。且这中间操作是加锁的，即保证了只有一个线程可以更改数据，但是不影响读旧数据。

/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
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);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
Returns the element that was removed from the list.
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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();
}
}
/**
* Sets the array.
*/
final void setArray(Object[] a) {
array = a;
}

优缺点：
优点
1.不会发生java.util.ConcurrentModificationException异常，不用对此做特殊操作。
2.多线程保证读效率
缺点：
1.副本的内存占用问题，数据内存较大时且多次写可能频繁引起GC
2.不能保证实时性，由于写时复制，操作副本，读到的还是旧数据。
3.大量写操作性能差。
所有的数据结构都或多或少有一定的优缺点限制，没有万能的通用且现场安全的数据结构，所以我们要学习了解其特点，然后根据其特点和适用场景使用。而不是学习了一个新数据结构就感觉高大上，就要使用，而不顾其特点和使用场景。