java高并发下CopyOnWriteArrayList替代ArrayList
Zhongger 人气:0一、ArrayList线程不安全
在Java的集合框架中，想必大家对ArrayList肯定不陌生，单线程的情况下使用它去做一些CRUD的操作是非常方便的，先来看看这个例子：
public class ListTest {
public static void main(String[] args) {
List<String> arrayList = new ArrayList<>();
arrayList.add("a");
arrayList.add("b");
arrayList.add("c");
for (String s : arrayList) {
System.out.println(s);
}
}
}
其输出结果就是与元素被添加进ArrayList的顺序一样，即：
a
b
c
但是到了多线程的情况下，ArrayList还会像单线程一样执行结果符合我们的预期吗？我们再来看下这个例子：
public class ListTest {
public static void main(String[] args) {
List<String> arrayList = new ArrayList<>();
for (int i = 0; i < 30; i++) {
new Thread(()->{
arrayList.add(UUID.randomUUID().toString().substring(0,5));
//往list中添加一个长为5的随机字符串
System.out.println(arrayList);
//读取list
},"线程"+(i+1)).start();
}
}
}
由输出结果：
Exception in thread "线程10"
Exception in thread "线程1"
Exception in thread "线程14"
Exception in thread "线程3"
Exception in thread "线程5"
Exception in thread "线程2"
Exception in thread "线程6"
Exception in thread "线程21"
Exception in thread "线程23"
Exception in thread "线程28"
Exception in thread "线程29"
java.util.ConcurrentModificationException
我们发现，多线程的情况下，有多个线程对ArrayList添加元素，同时又会有多个元素对ArrayList进行元素的读取，这样使得程序抛出了ConcurrentModificationException并发修改异常，所以我们可以下定结论：ArrayList线程不安全！
二、解决ArrayList线程不安全的方案
1、使用Vector类
我们知道，Java集合中的Vector类是线程安全的，可以用Vector去解决上述的问题。
public class ListTest {
public static void main(String[] args) {
List<String> arrayList = new Vector<>();
for (int i = 0; i < 30; i++) {
new Thread(()->{
arrayList.add(UUID.randomUUID().toString().substring(0,5));
//往list中添加一个长为5的随机字符串
System.out.println(arrayList);
//读取list
},"线程"+(i+1)).start();
}
}
}
翻看Vector的源码可知，其add方法是使用了synchronized同步锁，同一时刻只允许一个线程对List进行修改。虽然Vector能够保证线程安全，但通过前面几期推文的学习，synchronized的方案一般不是最优选择，会对程序的性能有一定的影响。
2、使用Collections类
Collections类中的synchronizedList方法可以使一个线程不安全的List转为线程安全的。
public class ListTest {
public static void main(String[] args) {
List<String> arrayList = Collections.synchronizedList(new ArrayList<>());
for (int i = 0; i < 30; i++) {
new Thread(()->{
arrayList.add(UUID.randomUUID().toString().substring(0,5));
//往list中添加一个长为5的随机字符串
System.out.println(arrayList);
//读取list
},"线程"+(i+1)).start();
}
}
}
即使是不看synchronizedList的源码我们也可以通过它的名字猜到其底层也是使用synchronized来保证线程安全的，这也不是最优解。
3、使用CopyOnWriteArrayList类
CopyOnWriteArrayList类就是我们今天要主要探讨的重头。
public class ListTest {
public static void main(String[] args) {
List<String> arrayList = Collections.synchronizedList(new ArrayList<>());
for (int i = 0; i < 30; i++) {
new Thread(()->{
arrayList.add(UUID.randomUUID().toString().substring(0,5));
//往list中添加一个长为5的随机字符串
System.out.println(arrayList);
//读取list
},"线程"+(i+1)).start();
}
}
}
下面我们来聊聊CopyOnWriteArrayList是这么实现线程安全的。
三、CopyOnWriteArrayList
1、简介
java.util.concurrent包下的并发List只有CopyOnWriteArrayList。CopyOnWriteArrayList是一个线程安全的ArrrayList，对其进行的修改操作都是在底层的一个复制的数组上进行的，采用了写时复制，读写分离的思想。其类图结构如下：
通过类图可以清楚下面几点：
- 每个CopyOnWriteArrayList对象中有一个
array数组对象用来存放具体元素 - ReentrantLock独占锁对象用来保证同一时刻只有一个线程对array进行修改
如果要我们自己来实现一个写时复制的线程安全的List，要考虑哪些点呢？
下面我们带着以下的问题与思考，来学习下CopyOnWriteArrayList吧！
- 何时初试化list，初始化的list元素个数为多少，list的大小是是有限的吗？
- 如何保证线程安全，多个线程对list进行读写时是如何保证线程安全的？
- 如何确保使用迭代器变量list时的数据一致性？
2、主要方法源码分析
1、初始化
无参构造函数，其实是在内部创建了一个大小为0的Object数组作为array的初始值
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
有参构造函数有两个：
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
CopyOnWriteArrayList中的array数组元素是入参toCopyIn数组元素的拷贝。
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
if (c.getClass() == CopyOnWriteArrayList.class)
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
elements = c.toArray();
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
setArray(elements);
}
入参为集合时，将集合里的元素复制到CopyOnWriteArrayList中。
2、添加元素
CopyOnWriteArrayList中用来添加元素的方法有很多，原理均类似，故选取add(E e)方法来进行学习。
public boolean add(E e) {
//(1)
final ReentrantLock lock = this.lock;
lock.lock();
try {
//(2)
Object[] elements = getArray();
//(3)
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
//(4)
setArray(newElements);
return true;
} finally {
//(5)
lock.unlock();
}
}
上述代码中，独占锁的思想非常值得学习。
- 调用add方法的线程会首先执行代码(1)去获取独占锁，如果有多个线程都调用add方法时则只有一个线程会去获取到该锁，其他线程会被阻塞挂起直到锁被释放。
- 一个线程获取到锁后，就保证了该线程添加元素的过程中其他线程不会对array数组进行修改。
- 线程获取到所后执行代码(2)获取array，然后执行代码(3)复制array到一个新数组中，新数组的大小是array数组的大小+1，所以CopyOnWriteArrayList是无界的List，并把新的元素添加进新数组中。
- 代码(4)使用新数组替换原数组，并在返回前执行(5)释放锁。由于加了锁，所以整个add的过程是原子性操作。
小结一下就是，添加元素时，线程先获取独占锁，然后复制原数组到新数组，给新数组添加元素，再把添加完元素后的新数组复制回原数组，最后释放锁返回。这就是所谓的写时复制。
3、获取指定位置元素
使用 E get(int index)获取下班为index的元素，如果元素不存在则抛出IndexOutOfBoundsException异常。
public E get(int index) {
return get(getArray(), index);
}
final Object[] getArray() {
return array;
}
private E get(Object[] a, int index) {
return (E) a[index];
}
上述的代码中，当线程x调用get方法获取指定位置的元素时，需要分两步，首先获取array数组，然后通过下标访问指定位置的元素，这个过程是没有加锁同步的。假设这时候List的内容如图所示，里面有1、2、3的元素：
由于线程x调用get方法时是没有加锁的，这就可能导致线程x在获取完array数组之后、访问指定位置元素之前，另外一个线程y进行了remove操作，假设要删除元素1，remove操作首先或获取独占锁，然后进行写时复制，也就是复制一份当前array数组，然后在复制的数组里删除线程x要调用get方法访问的元素1，然后让array指向复制的数组。所以这个时候array之前指向的数组的引用计数为1而不为0，因为线程x还在使用它，这是线程x要访问指定位置的元素了，而它操作的数组就是线程B删除元素之前的数组。如下示意图：
虽然线程y删除了index处的元素，但是线程x还是能够读到index处的元素，这就是写时复制策略产生的弱一致性问题。
4、修改指定元素
使用E set(int index, E element)方法修改list中指定元素的值时，如果指定位置元素不存在则抛出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数组进行修改，然后获取当前数组，调用get方法获取指定位置的元素，若指定位置的元素值与新值不一致，则创建新数组并复制元素，然后在新数组上修改元素值，再将array指向新数组；如果指定位置的元素值与新值一直，则为了保证volatile语义，还是要重新设置array，虽然其值为改变。
5、删除元素
这里介绍E remove(int index)方法。
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();
}
}
如上代码其实和新增元素的代码类似，首先获取独占锁以保证删除数据期间其他线程不能对 array 进行修改，然后获取数组中要被删除的元素，并把剩余的元素复制到新数组，之后使用新数组替换原来的数组，最后在返回前释放锁。
6、弱一致性的迭代器
在讲解什么是迭代器的弱一致性前，先看看下面的例子：
public class ListTest {
public static void main(String[] args) {
List<String> arrayList =new CopyOnWriteArrayList<>();
arrayList.add("Hello");
arrayList.add("HuYa");
Iterator<String> iterator = arrayList.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
输出如下：
Hello
HuYa
iterator的hasNext方法用于判断集合中是否还有元素，next用于返回具体元素。 那么CopyOnWriteArrayList中迭代器的弱一致性又是啥意思？所谓弱一致性，是指返回迭代器后，其他线程对list的增删改对迭代器是不可见的。
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
//array的快照版本
private final Object[] snapshot;
//数组下标
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
public boolean hasNext() {
return cursor < snapshot.length;
}
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
}
上述代码中，当CopyOnWriteArrayList对象调用iterator()方法获取迭代器时实际上会返回COWIterator对象，COWIterator对象的snapshot变量保存了当前list的内容， cursor是遍历list时数据的下标。
特别对snapshot快照进行一个说明：
- 如果在一个线程使用list返回的迭代器遍历元素的过程中，其他线程没有对list进行修改，那么snapshot本身就是list的array了。
- 如果在一个线程使用list返回的迭代器遍历元素的过程中，其他线程有对list进行修改，那么snapshot就是array的一个快照了，因为修改后list里面的数组其实是被新数组替换了，这时候原来的数组是被snapshot继续引用。
这也说明一个线程获取了迭代器后，使用该迭代器元素时，其他线程对该list进行的修改是不可见的，因为它们操作的是两个不同的数组，这也就是弱一致性。
最后再来看看一个例子：
public class ListTest {
public static void main(String[] args) throws InterruptedException {
List<String> arrayList =new CopyOnWriteArrayList<>( );
arrayList.add("Hello");
arrayList.add("HuYa");
arrayList.add("Welcome");
arrayList.add("to");
arrayList.add("Guangzhou");
Thread thread = new Thread(() -> {
arrayList.set(1, "WeiXin");
arrayList.remove(2);
arrayList.remove(3);
});
//保证在修改线程启动前先获取迭代器
Iterator<String> iterator = arrayList.iterator();
Thread.sleep(1000);
//修改线程启动
thread.start();
//等待修改执行完毕
thread.join();
//迭代元素
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
}
输出结果如下：
Hello
HuYa
Welcome
to
Guangzhou
虽然说子线程对arrayList进行了修改，但是主线程在arrayList被修改之前先获取到了其迭代器，拿到了原来数组的快照，所以子线程的修改对于主线程使用迭代器进行迭代并没有影响。这就体现了CopyOnWriteArrayList迭代器的弱一致性。
四、总结
本期主要学习了CopyOnWriteArrayList一些主要方法的源码、思想，总结一下：
- 最主要的是它写时复制的策略，来保证List的一致性，获取、修改、写入三步操作不是原子性的，故在增删改的过程中都使用了独占锁，来保证同一时刻只能有一个线程对list进行修改。
- CopyOnWriteArrayList提供了弱一致性的迭代器，从而保证在获取迭代器后，其他线程对list的修改对于迭代器是不可见的。
- 综合CopyOnWriteArrayList上述的特性，它适用于读多写少的高并发场景。
但是CopyOnWriteArrayList也有缺点，开发时要注意一下：
- 内存占用问题。因为CopyOnWriteArrayList的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，即旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。如果这些对象占用的内存比较大，这个时候很有可能造成频繁的GC，应用响应时间也随之变长。
- 数据一致性问题。CopyOnWriteArrayList容器只能保证数据的最终一致性，不能保证数据的实时一致性。
加载全部内容