关键词:
CopyOnWriteArrayList 是一种写时复制的 ArrayList,在写操作时加锁,拷贝原数组成员,在拷贝的数组上进行修改,并重置数组。
该类对于读写可以并发执行,如果写线程还未重置数组,读到的是旧数据;如果已经重置,读到的是新数据。
1 基本属性和方法
写时使用 ReentrantLock 加锁。内部数组 array 存储数据,用 volatile 修饰,保证可见性,可以直接获取相应位置的对象。
getArray 返回数组本身,toArray 返回复制的数组。
//用于写时加锁
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
// getArray是返回数组array本身
final Object[] getArray() {
return array;
}
final void setArray(Object[] a) {
array = a;
}
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
//两个toArray返回的均是复制的数组
public Object[] toArray() {
Object[] elements = getArray();
return Arrays.copyOf(elements, elements.length);
}
public <T> T[] toArray(T a[]) {
Object[] elements = getArray();
int len = elements.length;
if (a.length < len)
return (T[]) Arrays.copyOf(elements, len, a.getClass());
else {
System.arraycopy(elements, 0, a, 0, len);
if (a.length > len)
a[len] = null;
return a;
}
}
2 读
在上节讲到的 array 使用 volatile 修饰,可以在相应索引处直接获取对象。
private E get(Object[] a, int index) {
return (E) a[index];
}
public E get(int index) {
return get(getArray(), index);
}
3 写
这里的写包括添加,删除,修改等操作,其步骤如下:在整个过程中加锁,首先获取原数组的一个拷贝,在拷贝上做一些修改,然后用修改后的数组替代原数组。
由于所有写操作都加了锁,至多允许一个写执行。在写的时候,存在两个数组,一个是数组 array,一个是拷贝的数组。在写的最后setArray
未完成时,读线程读到的是旧数组 array。不能保证数据的实时一致性,只能保证最终一致性。
3.1 add
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//拷贝长度大于elements,在后面多余的是null
Object[] newElements = Arrays.copyOf(elements, len + 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;
//注意到增加操作后的数组大小为len+1,有效索引为0-len
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];
//从0开始index个,即elements的0-(index-1)拷贝到newElements
System.arraycopy(elements, 0, newElements, 0, index);
//从index开始numMoved个,即elements的index-(len-1)拷贝到newElements的(index+1)-len
//此时newElements[index]正好空着
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements);
} finally {
lock.unlock();
}
}
3.2 remove
remove 有三种重载,public 的有两种。直接给索引的删除比较容易,和前面的 add 比较相似;给对象删除的方法,会先查找索引再执行删除,由于未加锁,删除时数组可能已经变化,可能需要再次查找索引。
在if (current[i] != snapshot[i] && eq(o, current[i]))
中,如果第一个条件不满足,则第二个条件一定不满足,这是因为在第二个remove
方法中先使用 indexOf
方法来获得相应的索引,则snapshot
在[0,index-1]之前的项一定不能equals
对象o
。如果第一个条件不满足,即current[i]==snapshot[i]
,那么这些项一定无法equals
对象o
。
这种写法概括为if(a&&b)
,其中 a 不满足,则 b 一定不满足,即 a 是必要,b是充分。其实可以省略 a 写为 if(b)
,之所以在 b 前面加上 a 的判断,通常是对 a 的判断较为容易,对 b 的判断较复杂,利用 &&
的短路性质尽量能够不去判断 b。
个人感觉第二种remove
的写法不好,最好是加锁并删除,避免里面的多次查找索引。
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();
}
}
public boolean remove(Object o) {
//获取当前数组的一个快照
Object[] snapshot = getArray();
//indexOf未加锁
int index = indexOf(o, snapshot, 0, snapshot.length);
//如果索引无效,返回false,否则执行下面的remove
return (index < 0) ? false : remove(o, snapshot, index);
}
//在执行到该方法的时候,数组可能已经发生了变化,用快照找到的索引可能失效,需要重新查找
private boolean remove(Object o, Object[] snapshot, int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] current = getArray();
int len = current.length;
//如果数组已经发生了变化,会判断索引是否失效
//这里findIndex是一个标签
//用于控制下面的代码块,break 会退出所在的代码块
if (snapshot != current) findIndex: {
int prefix = Math.min(index, len);
for (int i = 0; i < prefix; i++) {
//该判断为if(a&&b),其中a不满足,则b一定不满足。
//写a是利用&&的短路性质,尽量早结束不判断b
if (current[i] != snapshot[i] && eq(o, current[i])) {
index = i;
break findIndex;
}
}
if (index >= len)
return false;
if (current[index] == o)
break findIndex;
//到这里说明index失效,从index向后进行查找
index = indexOf(o, current, index, len);
if (index < 0)
return false;
}//findIndex代码块结束的位置
Object[] newElements = new Object[len - 1];
System.arraycopy(current, 0, newElements, 0, index);
System.arraycopy(current, index + 1,
newElements, index,
len - index - 1);
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
private static int indexOf(Object o, Object[] elements,
int index, int fence) {
if (o == null) {
for (int i = index; i < fence; i++)
if (elements[i] == null)
return i;
} else {
for (int i = index; i < fence; i++)
if (o.equals(elements[i]))
return i;
}
return -1;
}
3.3 set/clear
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
E oldValue = get(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 oldValue;
} finally {
lock.unlock();
}
}
public void clear() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
setArray(new Object[0]);
} finally {
lock.unlock();
}
}
4 迭代器
调用 iterator
方法获取迭代器,将当前数组作为一个快照。在迭代器执行迭代的时候,对该快照数组进行迭代,迭代器只允许遍历,不允许修改。
ArrayList
允许迭代器执行修改,在生成迭代器之后的迭代过程中,只能通过迭代器进行修改,如果不通过迭代器修改,迭代器在迭代时因为 modCount != expectedModCount
而抛出异常 ConcurrentModificationException
。这称为快速失败。
CopyOnWriteArrayList
不允许迭代器执行修改,在迭代器生成的时候数组就已经确定下来了,迭代的过程中其他的修改都不会影响迭代器。这称为安全失败。
//CopyOnWriteArrayList中获取迭代器的方法,获取当前数组
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final 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. */
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
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();
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;
}
//不支持
public void remove() {
throw new UnsupportedOperationException();
}
//不支持
public void set(E e) {
throw new UnsupportedOperationException();
}
//不支持
public void add(E e) {
throw new UnsupportedOperationException();
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
Object[] elements = snapshot;
final int size = elements.length;
for (int i = cursor; i < size; i++) {
@SuppressWarnings("unchecked") E e = (E) elements[i];
action.accept(e);
}
cursor = size;
}
}
5 copyOnWriteArraySet
通过copyOnWriteArrayList
实现相应操作,为了确保不重复,该类的 add
调用了copyOnWriteArrayList
的 addIfAbsent
。
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
implements java.io.Serializable {
private static final long serialVersionUID = 5457747651344034263L;
private final CopyOnWriteArrayList<E> al;
/**
* Creates an empty set.
*/
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
public boolean add(E e) {
return al.addIfAbsent(e);
}
...
}
//copyOnWriteArrayList的方法
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
//和remove的逻辑类似,不再详述
private boolean addIfAbsent(E e, Object[] snapshot) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] current = getArray();
int len = current.length;
if (snapshot != current) {
// Optimize for lost race to another addXXX operation
int common = Math.min(snapshot.length, len);
for (int i = 0; i < common; i++)
if (current[i] != snapshot[i] && eq(e, current[i]))
return false;
if (indexOf(e, current, common, len) >= 0)
return false;
}
Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
copyonwritearraylist源码解析(基于jdk8)
...和方法2读3写3.1add3.2remove3.3set/clear4迭代器5copyOnWriteArraySetCopyOnWriteArrayList是一种写时复制的ArrayList,在写操作时加锁,拷贝原数组成员,在拷贝的数组上进行修改,并重置数组。该类对于读写可以并发执行,如果写线程还未重置... 查看详情
javareview-并发编程_并发list_copyonwritearraylist源码剖析(代码片段)
...取指定位置元素修改指定元素删除元素弱一致性的迭代器CopyOnWriteArrayList是如何实现弱一致性的小结概述并发包中的并发List只有CopyOnWriteArrayList。CopyOnWriteArrayList是一个线程安全的ArrayList,对其进行的修改操作都是在底层的一... 查看详情
copyonwritearraylist学习笔记(代码片段)
前言并发包中的并发List只有CopyOnWriteArrayList。CopyOnArrayList是一个线程安全的ArrayList,对其进行修改的操作都是在底层的一个复制的数组上进行的,也就是使用了写时复制策略。CopyOnWriteArrayList源码解析初始化publicCopyOnWriteA... 查看详情
copyonwritearraylist实现解析(代码片段)
一,内部核心变量定义/**Thelockprotectingallmutators*/finaltransientReentrantLocklock=newReentrantLock();/**Thearray,accessedonlyviagetArray/setArray.*/privatetransientvolatileObject[]array;数据存放在arry内 查看详情
copyonwritearraylist实现原理及源码分析
CopyOnWriteArrayList是Java并发包中提供的一个并发容器,它是个线程安全且读操作无锁的ArrayList,写操作则通过创建底层数组的新副本来实现,是一种读写分离的并发策略,我们也可以称这种容器为"写时复制器",Java并发包中类... 查看详情
高并发容器copyonwritearraylist原理解析(代码片段)
CopyOnWriteArrayList实现arraylist多线程数据安全的方式jdk提供的Collections.SynchronizedList()所有方法进行添加synchronized块publicvoidadd(intindex,Eelement)synchronized(mutex)list.add(index,element);使用reentrantLock自己对add时& 查看详情
copyonwritearraylist源码详解(代码片段)
CopyOnWriteArrayList源码详解最近在一个代码优化中使用到CopyOnWriteArrayList,想起这个java容器知道使用特性是读写分离,在每次写入时都复制一个新的list进行操作,但是没有具体的看过其源码细节,于是写一篇文章来... 查看详情
j.u.c并发框架源码阅读(十五)copyonwritearraylist
基于版本jdk1.7.0_80java.util.concurrent.CopyOnWriteArrayList 代码如下/**Copyright(c)2003,2011,Oracleand/oritsaffiliates.Allrightsreserved.*ORACLEPROPRIETARY/CONFIDENTIAL.Useissubjecttolicenseterms.****** 查看详情
死磕java集合之copyonwritearraylist源码分析(代码片段)
...看更多源码系列文章,与彤哥一起畅游源码的海洋。简介CopyOnWriteArrayList是ArrayList的线程安全版本,内部也是通过数组实现,每次对数组的修改都完全拷贝一份新的数组来修改,修改完了再替换掉老数组,这样保证了只阻塞写操作... 查看详情
死磕java集合之copyonwritearraylist源码分析(代码片段)
...看更多源码系列文章,与彤哥一起畅游源码的海洋。简介CopyOnWriteArrayList是ArrayList的线程安全版本,内部也是通过数组实现,每次对数组的修改都完全拷贝一份新的数组来修改,修改完了再替换掉老数组,这样保证了只阻塞写操作... 查看详情
copyonwritearraylist源码---jdk1.8
CopyOnWriteArrayList:通过copy一份以前元素的快照,是一种读写分离的并发策略,我们也可以称这种容器为"写时复制器"。该集合适合读多写少的场景(读没有加锁,其他更新操作均有加锁)。 /**Thelockprotectingallmutators*/finaltransien... 查看详情
list源码解析之arraylist源码分析
...个线程安全的ArrayList类,也可以使用concurrent并发包下的CopyOnWriteArrayList类。ArrayList实现了 查看详情
copyonwritearraylist使用入门及源码详解(代码片段)
CopyOnWriteArrayList官方定义CopyOnWriteArrayList是ArrayList的线程安全变体,其中通过创建底层数组的新副本来实现所有可变操作(添加,设置等)。这通常成本太高,但是当遍历操作大大超过突变时,它可能比替代方法更有效,并且当... 查看详情
copyonwritearraylist使用入门及源码详解(代码片段)
CopyOnWriteArrayList官方定义CopyOnWriteArrayList是ArrayList的线程安全变体,其中通过创建底层数组的新副本来实现所有可变操作(添加,设置等)。这通常成本太高,但是当遍历操作大大超过突变时,它可能比替代方法更有效,并且当... 查看详情
copyonwritearraylist源码解读(代码片段)
一、CopyOnWriteArrayList源码解读在JUC中,对于ArrayList的线程安全用法,比较推崇于使用CopyOnWriteArrayList,那CopyOnWriteArrayList是怎么解决线程安全问题的呢,本文带领大家一起解读下CopyOnWriteArrayList的源码,主要对几... 查看详情
源码阅读(29):java中线程安全的list结构——copyonwritearraylist(代码片段)
...;接上文《源码阅读(28):Java中线程安全的List结构——CopyOnWriteArrayList(1)》)4、CopyOnWriteArrayList的主要方法当完成CopyOnWriteArrayList集合的初始化过程的介绍后,本文再列举几个该集合典型的方法,以便帮助... 查看详情
javareview-并发编程_并发list_copyonwritearraylist源码剖析
文章目录概述概述并发包中的并发List只有CopyOnWriteArrayList。CopyOnWriteArrayList是一个线程安全的ArrayList,对其进行的修改操作都是在底层的一个复制的数组(快照)上进行的,也就是使用了写时复制策略。 查看详情
jdk1.8copyonwritearraylist源码学习
ArrayList底层:Object数组,非线程安全默认容量:10,其实是0,第一次add时,才会主动去扩容每一扩容,变为原来容量的1.5倍。10->15->22 /**/privatevoidgrow(intminCapacity)/**//*254*/intoldCapacity=elementData.length;/*255*/intnewCapacity=oldC 查看详情