java并发数据结构之CopyOnWriteArrayList

CopyOnWriteArrayList是一个线程安全的List实现，其在对对象进行读操作时，由于对象没有发生改变，因此不需要加锁，反之在对象进行增删等修改操作时，它会先复制一个对象副本，然后对副本进行修改，最后将修改后的副本对象写回，从而保证操作的线程安全,下面我们看一下具体的代码实现。

###构造函数

通过CopyOnWriteArrayList链表的构造，可以看出主要是依赖ReentrantLock与数组实现线程安全的链表

/**Thelockprotectingallmutators*/
finaltransientReentrantLocklock=newReentrantLock();
/**Thearray,accessedonlyviagetArray/setArray.*/
privatetransientvolatileObject[]array;
/**
*Createsanemptylist.
*/
publicCopyOnWriteArrayList(){
setArray(newObject[0]);
}

写操作

add实现

add是一个标准的使用ReentrantLock加锁保证线程安全操作的实现

/**
*Appendsthespecifiedelementtotheendofthislist.
*
*@parameelementtobeappendedtothislist
*@return{@codetrue}(asspecifiedby{@linkCollection#add})
*/
publicbooleanadd(Ee){
finalReentrantLocklock=this.lock;
lock.lock();//加锁
try{
Object[]elements=getArray();//获取自身数组对象
intlen=elements.length;
Object[]newElements=Arrays.copyOf(elements,len+1);//copy一个副本对象
newElements[len]=e;//赋值
setArray(newElements);//把对象写回去
returntrue;
}finally{
lock.unlock();//释放锁
}
}
/**
*Insertsthespecifiedelementatthespecifiedpositioninthis
*list.Shiftstheelementcurrentlyatthatposition(ifany)and
*anysubsequentelementstotheright(addsonetotheirindices).
*
*@throwsIndexOutOfBoundsException{@inheritDoc}
*/
publicvoidadd(intindex,Eelement){
finalReentrantLocklock=this.lock;
lock.lock();
try{
Object[]elements=getArray();//获取自身数组对象
intlen=elements.length;
if(index>len||index<0)//判断是否越界
thrownewIndexOutOfBoundsException("Index:"+index+
",Size:"+len);
Object[]newElements;
intnumMoved=len-index;//计算需要移动的数组长度
if(numMoved==0)
newElements=Arrays.copyOf(elements,len+1);
else{
newElements=newObject[len+1];
System.arraycopy(elements,0,newElements,0,index);
System.arraycopy(elements,index,newElements,index+1,
numMoved);
}
newElements[index]=element;//赋值
setArray(newElements);//把对象写回去
}finally{
lock.unlock();//释放锁
}
}

remove实现

在remove的实现中我们可以看到在实际执行操作之前，会对对象的线程安全进行再次检查，另外在执行定位下标操作时基于原有下标进行分段定位的优化，一定概率上会降低循环复杂度

publicEremove(intindex){
finalReentrantLocklock=this.lock;
lock.lock();//加锁
try{
Object[]elements=getArray();//获取自身数组对象
intlen=elements.length;
EoldValue=get(elements,index);//根据下标取值
intnumMoved=len-index-1;//计算需要移动的数组长度
if(numMoved==0)
setArray(Arrays.copyOf(elements,len-1));
else{
Object[]newElements=newObject[len-1];//声明一个新数组
System.arraycopy(elements,0,newElements,0,index);
System.arraycopy(elements,index+1,newElements,index,
numMoved);
setArray(newElements);
}
returnoldValue;
}finally{
lock.unlock();
}
}
publicbooleanremove(Objecto){
Object[]snapshot=getArray();
intindex=indexOf(o,snapshot,0,snapshot.length);//遍历数组定位元素下标
return(index<0)?false:remove(o,snapshot,index);
}
/**
*Aversionofremove(Object)usingthestronghintthatgiven
*recentsnapshotcontainsoatthegivenindex.
*/
privatebooleanremove(Objecto,Object[]snapshot,intindex){
finalReentrantLocklock=this.lock;
lock.lock();//加锁
try{
Object[]current=getArray();
intlen=current.length;
//以下这段代码保证数据线程安全，再次对数组是否发生改变进行判断，如果发生改变进行分段轮询，提高效率
if(snapshot!=current)findIndex:{//这里判断数组是否已经被修改，如果有修改就重新定位下标
intprefix=Math.min(index,len);//取最小值
for(inti=0;i<prefix;i++){//提高效率先按最小循环次数遍历
if(current[i]!=snapshot[i]&&eq(o,current[i])){
index=i;
breakfindIndex;
}
}
if(index>=len)//下标超过当前数组长度返回false
returnfalse;
if(current[index]==o)//下标未改变，直接返回
breakfindIndex;
index=indexOf(o,current,index,len);//遍历剩余部分
if(index<0)
returnfalse;
}
Object[]newElements=newObject[len-1];//创建一个长度len-1的数组，执行复制操作
System.arraycopy(current,0,newElements,0,index);
System.arraycopy(current,index+1,
newElements,index,
len-index-1);
setArray(newElements);//覆盖原数组
returntrue;
}finally{
lock.unlock();
}
}

读操作

读操作非常简单，无需加锁

/**
*{@inheritDoc}
*
*@throwsIndexOutOfBoundsException{@inheritDoc}
*/
publicEget(intindex){
returnget(getArray(),index);
}
@SuppressWarnings("unchecked")
privateEget(Object[]a,intindex){
return(E)a[index];
}

通过对源码的分析，可以看到CopyOnWriteArrayList只在需要保证线程安全的写操作上加锁，核心思想就是减少锁竞争，从而提高并发时的读取性能，适用于写少读多的应用场景。

以上就是对CopyOnWriteArrayList内部核心源码的基本走读与解析，其线程安全的实现模式很有代表意义，十分值得初学者参考与学习，希望对大家能有所帮助，其中如有不足与不正确的地方还望指正与海涵，十分感谢。

关注微信公众号，查看更多技术文章。