1、初探CopyOnWriteArrayList

第一眼看到这个类的时候,英文好的可能已经发现了,这个类翻译过来:使用写时复制策略的ArrayList。这个类出现其实是为了解决并发情况下,ArrayList线程不安全的问题。也可以这么说,CopyOnWriteArrayList是一个线程安全的ArrayList,因为他和ArrayList存储原理差不多,且都实现了List接口。他的基本原理也很简单,对CopyOnWriteArrayList进行的修改操作,是在底层的一个复制的数组上进行的。我们来看看CopyOnWriteArrayList的类图,让我们更加深入了解吧。

 

从这个类图我们可以看出,CopyOnWriteArrayList内部维护了两个变量,一个是lock,是ReentrantLock独占锁的对象,这个lock是用来保证同时只有一个线程操作我们的array数组。这里我们只关注他是一个独占锁就可以了。另一个是array,它是一个Object数组,用来存放具体的数组的,且用了volatile修饰,保证了这个数组内存可见性。

那如果让我们自己做一个写时复制的线程安全的ArrayList,那么该怎样做呢?我们要考虑写什么呢?

  • 什么时候初始化array,初始化array元素个数是多少,array是有限大小的吗?
  • 如何保证线程安全,比如多个线程进行读写的时候如何保证保证线程安全?
  • 如何保证使用迭代器时,数据的一致性

下面我们来看看,他的源码是如何写的吧

2、CopyOnWriteArrayList源码探究

2.1初始化

探究源码的第一步,也是较为简单的一步,就是看看这个类如何初始化的。简而言之就是直接看他的构造器。代码如下,我自己做了很多注释,应该能够一下子就看懂的:

//无参构造器其实就是设置array的值
//给array一个长度为0的Object数组
public CopyOnWriteArrayList() {
   
     
     setArray(new Object[0]);
}

//传入的是一个集合
public CopyOnWriteArrayList(Collection<? extends E> c) {
   
     
    Object[] elements;
    //如果传入的这个集合是CopyOnWriteArrayList类型的
    if (c.getClass() == CopyOnWriteArrayList.class)
        //直接使用本类的getArray方法,转化成为数组
        //传入elements
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
   
     
        //直接使用集合的toArray方法
        elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] 
        // 集合的toArray方法返回的可能不是Object数组,所以这里要转换一下
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    //将转换好的数组,传入array
    setArray(elements);
}

//传入一个数组,而我们要做的就是把这个数组复制一遍
//然后副本传入array
public CopyOnWriteArrayList(E[] toCopyIn) {
   
     
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

其实上面的构造器,都是为了将传入的内容变成Object数组,然后设置到array里面。

2.2添加元素

要想知道他是怎么添加元素的,我们先来看看他有哪些方法可以添加元素。

public boolean add(E e) ;
public void add(int index, E element) ;
public boolean addIfAbsent(E e) ;
private boolean addIfAbsent(E e, Object[] snapshot) ;
public int addAllAbsent(Collection<? extends E> c) ;

看上去好像有很多可以添加元素的方法,但其实它的原理大同小异,这里我着重讲解一下第一个方法,add(E e)。知道了这个方法,其他的方法就会一通百通。好了,我们来看一下他的源码(注释应该很到位了):

public boolean add(E e) {
   
     
    //首先获取独占锁,保证只有一个线程执行接下来的代码
    final ReentrantLock lock = this.lock;
    //加锁
    lock.lock();
    try {
   
     
        //获取当前的array,
        Object[] elements = getArray();
        int len = elements.length;
        //复制原来的数组到新的数组,并且新数组的长度比原来的大1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //把要添加的元素,加入到新数组的末尾
        newElements[len] = e;
        //然后把新的数组设置到array里面
        setArray(newElements);
        return true;
    } finally {
   
     
        //释放锁
        lock.unlock();
    }
}

其实上面讲述的方法,就把array数组拷贝下来,然后扩容之后,把新的元素赋值给新数组的最后一个元素,然后把新数组设置到array。这整个过程还要保证只有一个线程执行。所以使用了独占锁ReentrantLock。

2.3获取指定位置元素

这里获取指定的元素方法,代码相对比较简单,但是会有一个问题。那么我们下面看看源码吧

private E get(Object[] a, int index) {
   
     
    return (E) a[index];
}

final Object[] getArray() {
   
     
    return array;
}

public E get(int index) {
   
     
    return get(getArray(), index);
}

上面的代码可以说是非常简单了,但是会有问题。假如一个线程调用get方法获得元素的时候,这里就会有两个步骤,第一步首先获得array数组,第二步获得通过下标访问数组。就是这两步操作,但是在整个过程中没有相应的加锁同步。大家应该都想到了吧,当第一步执行完了以后,另外一个线程如果修改了这个数据,又或者直接删除了呢?那么当前执行的线程拿到的可能就是脏数据,而且是根本不期望的数据。这其实就是写时复制策略产生的弱一致性问题。

2.4修改指定元素

这里修改使用的是set方法,输入元素下标和元素的值,就可以修改。如果输入的下标不存在,就会产生一个IndexOutOfBoundsException异常。

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

这里着重说一下,为什么新的值和老的值相等的时候,还是要设置一下array数组。这里跟volatile的内存意义有关了,详情可以去看一下我的第七篇博客。

2.5删除元素

话不多说,删除元素也有很多方法,原理都一样,这里介绍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];
            //这里分了两次复制
            //第一次复制下标为0后的index个元素到新数组
            System.arraycopy(elements, 0, newElements, 0, index);
            //第二次复制下标为index后numMoved个元素到新数组
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            //然后设置新的array
            setArray(newElements);
        }
        //返回老的值
        return oldValue;
    } finally {
   
     
        //释放锁
        lock.unlock();
    }
}

如上代码其实和新增元素的代码类似,首先获取独占锁以保证删除数据期间其他线程不能对array做修改,然后复制元素到新的数组,返回老的值,最后释放锁。

2.6使用迭代器(弱一致性)

在讲述迭代器的弱一致性之前,我们先来看看这个迭代器如何使用。我们先来举个例子,看看这个迭代器如何使用:

public class COWListDemo {
   
     
    public static void main(String[] args) {
   
     
        //创建CopyOnWriteArrayList对象
        CopyOnWriteArrayList<String> arrayList = new CopyOnWriteArrayList<>();
        //添加元素
        arrayList.add("张三");
        arrayList.add("李四");
        //通过CopyOnWriteArrayList对象,获得迭代器
        Iterator<String> itr = arrayList.iterator();
        //判断迭代器有没有下一个元素
        while(itr.hasNext()){
   
     
            //输出下一个元素
            //并且迭代器里面的指针会指向下一个元素
            System.out.println(itr.next());
        }
    }
}

上面这个例子简单的使用了一下迭代器,下面我们来说一下什么叫迭代器的弱一致性。弱一致性:当我们获得了这个list的迭代器后,其他线程对list进行修改,是不会影响的。也就是说我们获得了的迭代器,其实是那一瞬间的迭代器,不会它里面的元素是不会因为其他线程的修改而改变。

我们来看看源码就知道了:

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

    public E next() {
   
     
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }
}

如上代码,当调用iterator()方法获取迭代器,实际上会返回一个COWIterator对象,COWIterator对象其中的snapshot,保存了当前list的内容,cursor是迭代器遍历的下标。这里我们称snapshot其实是array的一个快照。

那么为什么说snapshot其实是array的一个快照呢?很多人没有想明白,明明是把array的引用传递给了snapshot,两个变量其实用的是同一个数组啊,如果其他线程修改了array,那么迭代器里面的内容也会随之改变。但是大家都忘记了一点,就是对array进行增删改查操作时,我们都是用一个新的数组的引用,直接覆盖老的,也就是说,修改了以后,迭代器里面的snapshot仍然引用的上一个array。这也就说明了,使用迭代器元素时,其他线程对改list进行增删改查不可见,因为他们已经操作的是两个数组了,这其实就是弱一致性。

如果你还不明白我这里有一个例子,看完你就会恍然大悟了:

public class COWIList {
   
     
    //初始化list,且要保证内存可见性
    private static volatile CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
   
    public static void main(String[] args) throws InterruptedException {
   
     
        //添加元素
        list.add("one");
        list.add("two");
        list.add("three");
        list.add("five");
        list.add("six");
        list.add("seven");

        Thread threadOne = new Thread(new Runnable() {
   
     
            @Override
            public void run() {
   
     
                //修改元素
                list.set(1,"strange");
                //删除元素
                list.remove(2);
                list.remove(3);
            }
        });

        //先获得迭代器
        Iterator<String> it = list.iterator();

        //然后启动线程
        threadOne.start();

        //等待子线程完成
        threadOne.join();

        //使用迭代器遍历元素
        while(it.hasNext()){
   
     
            System.out.println(it.next());
        }
    }
}

得到的结果如下:
 

3、总结

CopyOnWriteArrayList使用写时复制的策略来保证list的一致性,但是获取-修改-写入三步却不是原子性的,所以在增删改的过程中都使用了独占锁,来保证某个时间只有一个线程对其进行修改。另外CopyOnWriteArrayList还提供了弱一致性的迭代器,其他线程的修改对迭代器是不可见的,迭代器内部维护的snapshot,其实是array的快照。

好了,CopyOnWriteArrayList就分析到这里,喜欢的话就给我这个网络乞丐点个赞吧!!