java并发数据结构之CopyOnWriteArrayList

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

###构造函数

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

/** The lock protecting all mutators */     final transient ReentrantLock lock = new ReentrantLock();      /** The array, accessed only via getArray/setArray. */     private transient volatile Object[] array;       /**      * Creates an empty list.      */     public CopyOnWriteArrayList() {         setArray(new Object[0]);     }

写操作

add实现

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

    /**      * 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);//copy一个副本对象             newElements[len] = e;//赋值             setArray(newElements);//把对象写回去             return true;         } finally {             lock.unlock();//释放锁         }     }      /**      * Inserts the specified element at the specified position in this      * list. Shifts the element currently at that position (if any) and      * any subsequent elements to the right (adds one to their indices).      *      * @throws IndexOutOfBoundsException {@inheritDoc}      */     public void add(int index, E element) {         final ReentrantLock lock = this.lock;         lock.lock();         try {             Object[] elements = getArray();//获取自身数组对象             int len = elements.length;             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];                 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的实现中我们可以看到在实际执行操作之前,会对对象的线程安全进行再次检查,另外在执行定位下标操作时基于原有下标进行分段定位的优化,一定概率上会降低循环复杂度

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();         int index = indexOf(o, snapshot, 0, snapshot.length);//遍历数组定位元素下标         return (index < 0) ? false : remove(o, snapshot, index);     }      /**      * A version of remove(Object) using the strong hint that given      * recent snapshot contains o at the given 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;             //以下这段代码保证数据线程安全,再次对数组是否发生改变进行判断,如果发生改变进行分段轮询,提高效率             if (snapshot != current) findIndex: {//这里判断数组是否已经被修改,如果有修改就重新定位下标                 int prefix = Math.min(index, len);//取最小值                 for (int i = 0; i < prefix; i++) {//提高效率先按最小循环次数遍历                     if (current[i] != snapshot[i] && eq(o, current[i])) {                         index = i;                         break findIndex;                     }                 }                 if (index >= len)//下标超过当前数组长度返回false                     return false;                 if (current[index] == o)//下标未改变,直接返回                     break findIndex;                 index = indexOf(o, current, index, len);//遍历剩余部分                 if (index < 0)                     return false;             }             Object[] newElements = new Object[len - 1];//创建一个长度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();         }     }

读操作

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

/**      * {@inheritDoc}      *      * @throws IndexOutOfBoundsException {@inheritDoc}      */     public E get(int index) {         return get(getArray(), index);     }      @SuppressWarnings("unchecked")     private E get(Object[] a, int index) {         return (E) a[index];     }

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

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

 

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

java并发数据结构之CopyOnWriteArrayList

发表评论

相关文章