Java集合 | CopyOnWriteArrayList源码分析(JDK 1.7)
一、基本结构
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
二、基本属性
// 加锁的方法，在增加、移除操作的时候都需要加锁
transient final ReentrantLock lock = new ReentrantLock();
// 底层的数组
private volatile transient Object[] array;
三、构造方法
// 无参构造函数
public CopyOnWriteArrayList() {
// 实例化一个 Object 类型的长度为 0 的数组，并赋值给 array
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);
// 将转变之后的数组赋给 array
setArray(elements);
}
// 有参构造函数，参数是数组
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
通用方法
// 获取 array 底层数组
final Object[] getArray() {
return array;
}
// 更新底层数组 array
final void setArray(Object[] a) {
array = a;
}
四、增加
CopyOnWriteArrayList 中的 add 方法
// 增加方法
public boolean add(E e) {
final ReentrantLock lock = this.lock;
// 获取执行 add 方法的那个对象的对象锁
lock.lock();
try {
// 获取底层数组，赋给 elements
Object[] elements = getArray();
int len = elements.length;
// 将底层数组 array 复制到新的数组 newElements
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 在新数组 newElements 添加元素
newElements[len] = e;
// 将新数组 newElements 赋给底层数组 array
setArray(newElements);
return true;
} finally {
// 释放当前对象的锁
lock.unlock();
}
}
在 CopyOnWriteArrayList 中增加元素的时候，需要对当前对象加锁，即在一个线程添加元素的时候，其他线程是不能同时进行增加操作的
在添加元素的时候，不是直接在底层数组 array 上添加的，而是先复制了一个新的数组，然后在这个新的数组上添加元素，最后在把新的数组赋值给底层数组
增加一个元素的图示如下
五、删除
CopyOnWriteArrayList 中的 remove() 方法，分为两种，一种是根据位置进行删除，还有一种是根据传入的元素进行删除
根据通过传入的位置进行删除
public E remove(int index) {
final ReentrantLock lock = this.lock;
// 获取执行 remove 方法的那个对象的对象锁
lock.lock();
try {
// 获取底层数组 array
Object[] elements = getArray();
int len = elements.length;
// 从 elements 数组中获取位置是 index 的值（即要被删除的元素）
E oldValue = get(elements, index);
// 获得从被删元素所在位置到数组的最后一位之间的元素个数
int numMoved = len - index - 1;
// 如果个数是 0，说明此时被删元素是数组的最后一位，直接复制最后一位之前的所有元素，将赋值的结果赋值给底层数组 array
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
// 如果被删元素不是数组的最后一位
else {
// 先实例化一个个数少 1 的新数组，用于存放删除指定元素之后的数组
Object[] newElements = new Object[len - 1];
// 首先将 elements 数组被删元素之前的所有元素复制到新数组(从新数组第0位开始接收)
System.arraycopy(elements, 0, newElements, 0, index);
// 然后将 elements 数组被删元素之后的所有元素复制到新数组(从新数组第index位开始接收)
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
// 将新数组 newElements 赋值给底层数组 array
setArray(newElements);
}
return oldValue;
} finally {
lock.unlock();
}
}
根据传入的对象进行删除
public boolean remove(Object o) {
final ReentrantLock lock = this.lock;
// 获取对象
lock.lock();
try {
// 将底层数组 array 赋给 elements
Object[] elements = getArray();
int len = elements.length;
// 如果数组长度大于 0
if (len != 0) {
// Copy while searching for element to remove
// This wins in the normal case of element being present
int newlen = len - 1;
// 实例化一个长度比 array 数组长度小 1 的新数组
Object[] newElements = new Object[newlen];
// 遍历新数组
for (int i = 0; i < newlen; ++i) {
// 如果传入对象和底层数组中当前位置的值相同(底层通过equals)判断
if (eq(o, elements[i])) {
// found one; copy remaining and exit
// 从被删元素的后一位开始遍历
for (int k = i + 1; k < len; ++k)
// 将被删除元素之后的所有元素赋给新数组
newElements[k-1] = elements[k];
// 将新数组赋给底层数组 array
setArray(newElements);
return true;
} else
// 如果传入对象和底层数组中当前位置的值不同，则直接将底层数组当前位置的元素赋值给新数组
newElements[i] = elements[i];
}
// special handling for last cell
// 如果底层数组只有1个元素
if (eq(o, elements[newlen])) {
// 直接将这一个元素赋值给底层数组 array
setArray(newElements);
return true;
}
}
return false;
} finally {
lock.unlock();
}
}
通用方法
// 获取数组中的某个位置的值
private E get(Object[] a, int index) {
// 获取数组中 index 位置的值
return (E) a[index];
}
private static boolean eq(Object o1, Object o2) {
// CopyOnWriteArrayList 中并没有重写 equals 方法
return (o1 == null ? o2 == null : o1.equals(o2));
}
删除方法共有2种，一种是根据位置进行删除，另一种是根据元素进行删除
对于根据位置进行删除的情况，步骤如下：
-
将底层数组复制给新数组 elements
-
根据删除元素的位置进行区分
2.1 如果删除原数组中的最后一个元素，直接将最后一个元素之前的所有元素复制到一个临时数组中，然后将这个临时的数组赋给底层数组 array
2.2 如果不是删除原数组中的最后一个元素，先创建一个长度比原来小 1 的新数组 newElements。首先将原数组被删元素之前的所有元素复制到新数组 newElements，在将原数组被删元素之后的所有元素复制到新数组 newElements。最后再把新数组 newElements 赋给底层数组 array
对于根据元素进行删除的情况，步骤如下：
-
将底层数组复制给新数组 elements
-
实例化一个数组长度比原来小 1 的新数组 newElements
-
遍历 newElements 数组
3.1 如果要删除的值和 elements 数组当前位置的值相同，则循环遍历将 elements 数组中除了被删元素之外的所有元素按原来的次序放入 newElements 中。放完之后，将放完的 newElements 赋给底层数组 array，然后直接退出
3.2 如果要删除的值和 elements 数组当前位置的值不同，则直接将 elements 数组中当前位置的元素赋给 newElements 中的当前位置
-
如果原数组长度是 1，且要删除的元素和这唯一的一个元素相同，则直接将空的数组赋给底层数组 array（将唯一一个元素删除自然就变成空数组了）
和 add 方法一样，执行 remove 方法之前也是需要获取对象锁的，也是先复制一份和底层数组 array 一样的数组，然后对这个新的数组进行删除操作，最后在将新的数组赋值给底层数组 array
六、其他方法
CopyOnWriteArrayList 的 get 方法
public E get(int index) {
// 传入底层的数组 array 和数组中的位置
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}
读取的方法是不用加锁的
七、遍历
// 集合遍历的方法
public Iterator<E> iterator() {
// 传入底层数组，和开始遍历的位置(从0开始)
return new COWIterator<E>(getArray(), 0);
}
内部类 COWIterator
private static class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array */
// 存放底层数组
private final Object[] snapshot;
/** Index of element to be returned by subsequent call to next. */
// 当前遍历在 snapshot 数组中的位置
private int cursor;
// 实例化迭代器的时候调用该构造函数
private COWIterator(Object[] elements, int initialCursor) {
// 传入初始遍历的位置，赋值给 cursor
cursor = initialCursor;
// 将底层数组赋值给新数组 snapshot
snapshot = elements;
}
public boolean hasNext() {
return cursor < snapshot.length;
}
public boolean hasPrevious() {
return cursor > 0;
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
// 从新的 snapshot 数组中获取 cursor 位置的值
return (E) snapshot[cursor++];
}
@SuppressWarnings("unchecked")
public E previous() {
if (! hasPrevious())
throw new NoSuchElementException();
return (E) snapshot[--cursor];
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; <tt>remove</tt>
* is not supported by this iterator.
*/
// 不支持直接在迭代器中使用 remove 方法
public void remove() {
throw new UnsupportedOperationException();
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; <tt>set</tt>
* is not supported by this iterator.
*/
public void set(E e) {
throw new UnsupportedOperationException();
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; <tt>add</tt>
* is not supported by this iterator.
*/
public void add(E e) {
throw new UnsupportedOperationException();
}
}
可以看到，CopyOnWriteArrayList 下的 Iterator 方法，并不是对底层数组 array 进行直接遍历的，而是先将底层数组复制到新数组 snapshot，然后对这个新的数组遍历取值
此时如果在遍历的时候，执行 CopyOnWrieArrayList 的 add 或者 remove 方法，并不会影响遍历，在使用迭代器进行遍历的时候，都是对迭代器在的 snapshot 这个数组执行的，而执行集合的 add 或者 remove 方法，只是对底层的数组 array 进行操作，发生改变的也只是 array 这个数组，并没有影响到 Iterator 中的 snapshot 这个数组
正因为这个机制，会出现这么一种情况，一边使用 Iterator 遍历 CopyOnWriteArrayList，一边使用集合的 remove 方法删除遍历出来的元素，当遍历结束的时候，CopyOnWriteArrayList 中已经没有元素了，而迭代器中仍然存有遍历之前底层数组中的所有元素
因为 CopyOnWriteArrayList 的迭代器不是对底层数组进行操作，所有也不会出现 ArrayList 和 HashMap 这种在使用迭代器的过程中如果集合中增加或者删除元素而发生的 ConcurrentModificationException 异常
同时要注意的是，CopyOnWriteArrayList 迭代器下的 remove、set 和 add 方法都是不能使用的，都会抛出 UnsupportedOperationException 异常
八、关于读和写
设想这么一个场景，如果有两个线程，一个线程执行读，另一个线程执行写，这里需要分以下几种情况：
1.使用Iterator进行读
这种情况我们上面已经研究过了，如果一个线程在完成了 Iterator 的初始化之后，其他线程才开始对 CopyOnWriteArrayList 集合进行写，即使写操作已经完成了，但是执行读操作的那个线程读到的依然是旧的数组
2.使用get方式进行读
使用 get 方法需要分这么三种情况：
- 如果一个线程写操作（在复制的数组中放了新的元素）未完成，另一个线程读到的依然是旧的数组的元素
- 如果一个线程写操作完成，但是没有赋给底层数组，另一个线程读到的依然是旧的数组的元素
- 如果一个线程写操作完成，同时也赋给了底层数组，另一个线程读到的则是新数组的元素
需要强调的是，读操作是不加锁的
九、缺点
这里我直接引用别人写的，写的还是挺清楚的
https://blog.****.net/linsongbin1/article/details/54581787
十、参考
https://www.cnblogs.com/dolphin0520/p/3938914.html
https://blog.****.net/linsongbin1/article/details/54581787
https://mp.weixin.qq.com/s?__biz=MzIxNTQ3NDMzMw==&mid=2247483989&idx=1&sn=6610ee7d7938a620452284eec215d213&scene=19#wechat_redirect