线程安全的ArrayList——CopyOnWriteArrayList

admin管理员组

文章数量:1641793

CopyOnWriteArrayList是一个线程安全的ArrayList，对其进行的修改操作都是在底层的一个复制的数组（快照）上进行的，也就是使用了写时复制策略。同时因为获取—修改—写入三步操作并不是原子性的，所以在增删改的过程中都使用了独占锁，来保证在某个时间只有一个线程能对list数组进行修改。

类图

每个CopyOnWriteArrayList对象里面有一个array数组对象用来存放具体元素

ReentrantLock独占锁对象用来保证同时只有一个线程对array进行修改。

ReentrantLock独占锁对象用来保证同时只有一个线程对array进行修改。 何时初始化list？

初始化list

1、无参构造函数

代码在内部创建了一个大小为0的Object数组作为array的初始值。

2、有参构造函数

如何保证线程安全？

添加元素——add（E e）

CopyOnWriteArrayList中用来添加元素的函数有

add（E e）

add（int index, Eelement）

addIfAbsent（E e）

addAllAbsent（Collection<? extends E>c）

调用add方法的线程会首先执行代码（1）去获取独占锁，如果多个线程都调用add方法则只有一个线程会获取到该锁，其他线程会被阻塞挂起直到锁被释放。所以一个线程获取到锁后，就保证了在该线程添加元素的过程中其他线程不会对array进行修改。线程获取锁后执行代码（2）获取array，然后执行代码（3）复制array到一个新数组（从这里可以知道新数组的大小是原来数组大小增加1，所以CopyOnWriteArrayList是无界list），并把新增的元素添加到新数组。然后执行代码（4）使用新数组替换原数组，并在返回前释放锁。由于加了锁，所以整个add过程是个原子性操作。需要注意的是，在添加元素时，首先复制了一个快照，然后在快照上进行添加，而不是直接在原来数组上进行。

删除元素——E remove（int index）

E remove（int index）

boolean remove（Object o）

boolean remove（Object o, Object[] snapshot, int index）

（1）获取独占锁以保证删除数据期间其他线程不能对array进行修改。

（2）然后获取数组中要被删除的元素，并把剩余的元素复制到新数组。

（3）之后使用新数组替换原来的数组。

（4）最后在返回前释放锁。

修改元素——E set（int index, E element）

修改list中指定元素的值，如果指定位置的元素不存在则抛出IndexOutOfBoundsException异常。

（1）首先获取了独占锁，从而阻止其他线程对array数组进行修改，

（2）然后获取当前数组，并调用get方法获取指定位置的元素

（3）如果指定位置的元素值与新值不一致则创建新数组并复制元素，然后在新数组上修改指定位置的元素值并设置新数组到array。

（4）如果指定位置的元素值与新值一样，则为了保证volatile语义，还是需要重新设置array，虽然array的内容并没有改变。

查找元素——E get（int index）

获取下标为index的元素，如果元素不存在则抛出IndexOutOfBoundsException异常。

当线程x调用get方法获取指定位置的元素时，分两步走，首先获取array数组（这里命名为步骤A），然后通过下标访问指定位置的元素（这里命名为步骤B），这是两步操作，但是在整个过程中并没有进行加锁同步。

情景问题——线程x读同时线程y删

数组{1,2,3}，线程x读元素1，线程y删除元素1。

remove操作首先会获取独占锁，然后进行写时复制操作，也就是复制一份当前array数组，然后在复制的数组里面删除线程x通过get方法要访问的元素1，之后让array指向复制的数组。而这时候array之前指向的数组的引用计数为1而不是0，因为线程x还在使用它，这时线程x开始执行步骤B，步骤B操作的数组是线程y删除元素之前的数组，所以，虽然线程y已经删除了index处的元素，但是线程x的步骤B还是会返回index处的元素，这其实就是写时复制策略产生的弱一致性问题。

弱一致性： 不能保证任何一次读都能读到最近一次写入的数据，但能保证最终可以读到写入的数据，所以像concurrentHashMap就是弱一致性的一种实现。

如何保证使用迭代器遍历list时的数据一致性？

如何使用迭代器？

迭代器的弱一致性

CopyOnWriteArrayList中迭代器的弱一致性是怎么回事，所谓弱一致性是指返回迭代器后，其他线程对list的增删改对迭代器是不可见的。

当调用iterator（）方法获取迭代器时实际上会返回一个COWIterator对象，COWIterator对象的snapshot变量保存了当前list的内容，cursor是遍历list时数据的下标。为什么说snapshot是list的快照呢？明明是指针传递的引用啊，而不是副本。如果在该线程使用返回的迭代器遍历元素的过程中，其他线程没有对list进行增删改，那么snapshot本身就是list的array，因为它们是引用关系。但是如果在遍历期间其他线程对该list进行了增删改，那么snapshot就是快照了，因为增删改后list里面的数组被新数组替换了，这时候老数组被snapshot引用。这也说明获取迭代器后，使用该迭代器元素时，其他线程对该list进行的增删改不可见，因为它们操作的是两个不同的数组，这就是弱一致性。

本文标签： 线程ArrayListCopyOnWriteArrayList