`
kingj
  • 浏览: 429143 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

java CopyOnWriteArrayList的原理

 
阅读更多

     通常情况下我们的高并发都发生在“多读少写”的情况,因此如果能够实现一种更优秀的算法这对生产环境还是很有好处的。ReadWriteLock当然是一种实现。CopyOnWriteArrayList/CopyOnWriteArraySet确实另外一种思路。

CopyOnWriteArrayList/CopyOnWriteArraySet 的基本思想是一旦对容器有修改,那么就“复制”一份新的集合,在新的集合上修改,然后将新集合复制给旧的引用。当然了这部分少不了要加锁。显然对于 CopyOnWriteArrayList/CopyOnWriteArraySet来说最大的好处就是“读”操作不需要锁了。

我们来看看源码。

/** The array, accessed only via getArray/setArray. */
private   volatile   transient Object[] array;
public E get( int index) {
   
return (E)(getArray()[index]);
}
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 ;
}
public Iterator < E > iterator() {
   
return   new COWIterator < E > (getArray(), 0 );
}
   
public   void clear() {
   
final ReentrantLock lock =   this .lock;
    lock.lock();
   
try {
        setArray(
new Object[ 0 ]);
    }
finally {
        lock.unlock();
    }
    }

对于上述代码,有几点说明:

  1. List仍然是基于数组的实现,因为只有数组是最快的。
  2. 为了保证无锁的读操作能够看到写操作的变化,因此数组array是volatile类型的。
  3. get/indexOf/iterator等操作都是无锁的,同时也可以看到所操作的都是某一时刻array的镜像(这得益于数组是不可变化的)
  4. add/set/remove/clear等元素变化的都是需要加锁的,这里使用的是ReentrantLock。

这里有一段有意思的代码片段。

    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();
    }
    }

final   void setArray(Object[] a) {
    array
= a;
}

对于set操作,如果元素有变化,修改后setArray(newElements);将新数组赋值还好理解。那么如果一个元素没有变化,也就是上述代码的else部分,为什么还需要进行一个无谓的setArray操作?毕竟setArray操作没有改变任何数据。

对于这个问题也是很有意思,有一封邮件讨论了此问题(123 )。
大 致的意思是,尽管没有改变任何数据,但是为了保持“volatile”的语义,任何一个读操作都应该是一个写操作的结果,也就是读操作看到的数据一定是某 个写操作的结果(尽管写操作没有改变数据本身)。所以这里即使不设置也没有问题,仅仅是为了一个语义上的补充(个人理解)。

这里还有一个 有意思的讨论,说什么addIfAbsent在元素没有变化的时候为什么没有setArray操作?这个要看怎么理解addIfAbsent的语义了。如 果说addIfAbsent语义是”写“或者”不写“操作,而把”不写“操作当作一次”读“操作的话,那么”读“操作就不需要保持volatile语义 了。

 

对于CopyOnWriteArraySet而言就简单多了,只是持有一个CopyOnWriteArrayList,仅仅在add/addAll的时候检测元素是否存在,如果存在就不加入集合中。

private   final CopyOnWriteArrayList < E > al;
/**
* Creates an empty set.
*/
public CopyOnWriteArraySet() {
    al
=   new CopyOnWriteArrayList < E > ();
}

public   boolean add(E e) {
   
return al.addIfAbsent(e);
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics