ArrayList与CopyOnWriteArrayList常见操作与问题

发表于 | 更新于: | 分类于

ArrayList循环遍历并删除元素的常见陷阱

在工作和学习中，经常碰到删除ArrayList里面的某个元素，看似一个很简单的问题，却很容易出bug。不妨把这个问题当做一道面试题目，我想一定能难道不少的人。今天就给大家说一下在ArrayList循环遍历并删除元素的问题。首先请看下面的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.ArrayList;
public class ArrayListRemove
{
　　public static void main(String[]args)
　　{
　　　　ArrayList<String>list=newArrayList<String>();
　　　　list.add("a");
　　　　list.add("b");
　　　　list.add("b");
　　　　list.add("c");
　　　　list.add("c");
　　　　list.add("c");
　　　　remove(list);
　　　　for(Strings:list)
　　　　{
　　　　　　System.out.println("element : "+s);
　　　　}
　　}
　　public static void remove(ArrayList<String> list)
　　{
　　// TODO:
　　}
}

如果要想删除list的b字符，有下面两种常见的错误例子：

错误写法实例一：

1
2
3
4
5
6
7
8
9
10
11
public static void remove(ArrayList<String> list)
{
    for(inti=0;i<list.size();i++)
    {
        Strings=list.get(i);
        if(s.equals("b"))
        {
            list.remove(s);
        }
    }
}

错误的原因：这种最普通的循环写法执行后会发现第二个“b”的字符串没有删掉。

错误写法实例二：

1
2
3
4
5
6
7
8
9
10
public static void remove(ArrayList<String> list)
{
    for(Strings:list)
    {
        if(s.equals("b"))
        {
            list.remove(s);
        }
    }
}

错误的原因：这种for-each写法会报出著名的并发修改异常：java.util.ConcurrentModificationException。

先解释一下实例一的错误原因。翻开JDK的ArrayList源码，先看下ArrayList中的remove方法（注意ArrayList中的remove有两个同名方法，只是入参不同，这里看的是入参为Object的remove方法）是怎么实现的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean remove(Objecto){
    if(o==null){
        for(intindex=0;index<size;index++)
            if(elementData[index]==null){
                fastRemove(index);
                return true;
            }
            }else{
                for(intindex=0;index<size;index++)
                if(o.equals(elementData[index])){
                fastRemove(index);
                return true;
            }
    }
    return false;
}

一般情况下程序的执行路径会走到else路径下最终调用faseRemove方法：

1
2
3
4
5
6
7
private void fastRemove(int index){
        modCount++;
        intnumMoved=size-index-1;
        if(numMoved>0)             
        　　System.arraycopy(elementData,index+1,elementData,index,numMoved);
        elementData[--size]=null;// Let gc do its work
}

可以看到会执行System.arraycopy方法，导致删除元素时涉及到数组元素的移动。针对错误写法一，在遍历第一个字符串b时因为符合删除条件，所以将该元素从数组中删除，并且将后一个元素移动（也就是第二个字符串b）至当前位置，导致下一次循环遍历时后一个字符串b并没有遍历到，所以无法删除。针对这种情况可以倒序删除的方式来避免：

1
2
3
4
5
6
7
8
9
10
11
public static void remove(ArrayList<String> list)
{
    for(inti=list.size()-1;i>=0;i--)
    {
        Strings=list.get(i);
        if(s.equals("b"))
        {
            list.remove(s);
        }
    }
}

因为数组倒序遍历时即使发生元素删除也不影响后序元素遍历。

接着解释一下实例二的错误原因。错误二产生的原因却是foreach写法是对实际的Iterable、hasNext、next方法的简写，问题同样处在上文的fastRemove方法中，可以看到第一行把modCount变量的值加一，但在ArrayList返回的迭代器（该代码在其父类AbstractList中）：

1
2
3
public Iterator<E> iterator() {
        return new Itr();
}

这里返回的是AbstractList类内部的迭代器实现private class Itr implements Iterator，看这个类的next方法：

1
2
3
4
5
6
7
8
9
10
11
public E next() {
        checkForComodification();
        try {
            E next = get(cursor);
            lastRet = cursor++;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
}

第一行checkForComodification方法：

1
2
3
4
final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
}

这里会做迭代器内部修改次数检查，因为上面的remove(Object)方法修改了modCount的值，所以才会报出并发修改异常。要避免这种情况的出现则在使用迭代器迭代时（显示或for-each的隐式）不要使用ArrayList的remove，改为用Iterator的remove即可。

1
2
3
4
5
6
7
8
9
10
11
12
public static void remove(ArrayList<String> list) 
    {
        Iterator<String> it = list.iterator();
        while (it.hasNext()) 
        {
            String s = it.next();
            if (s.equals("b")) 
            {
                it.remove();
            }
        }
}

CopyOnWriteArrayList

Doug Lea 大师就为我们提供 CopyOnWriteArrayList 容器可以保证线程安全，保证读读之间在任何时候都不会被阻塞，CopyOnWriteArrayList 也被广泛应用于很多业务场景之中，CopyOnWriteArrayList 值得被我们好好认识一番。

CopyOnWrite的设计思想

如果简单的使用读写锁的话，在写锁被获取之后，读写线程被阻塞，只有当写锁被释放后读线程才有机会获取到锁从而读到最新的数据，站在读线程的角度来看，即读线程任何时候都是获取到最新的数据，满足数据实时性。既然我们说到要进行优化，必然有 trade-off,我们就可以牺牲数据实时性满足数据的最终一致性即可。而 CopyOnWriteArrayList 就是通过 Copy-On-Write(COW)，即写时复制的思想来通过延时更新的策略来实现数据的最终一致性，并且能够保证读线程间不阻塞。

COW 通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行 Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。对 CopyOnWrite 容器进行并发的读的时候，不需要加锁，因为当前容器不会添加任何元素。所以 CopyOnWrite 容器也是一种读写分离的思想，延时更新的策略是通过在写的时候针对的是不同的数据容器来实现的，放弃数据实时性达到数据的最终一致性。

CopyOnWriteArrayList 的实现原理

现在我们来通过看源码的方式来理解 CopyOnWriteArrayList，实际上 CopyOnWriteArrayList 内部维护的就是一个数组

1
2
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

并且该数组引用是被 volatile 修饰，注意这里仅仅是修饰的是数组引用，其中另有玄机，稍后揭晓。关于 volatile 很重要的一条性质是它能够够保证可见性，关于 volatile 的详细讲解可以看这篇文章。对 list 来说，我们自然而然最关心的就是读写的时候，分别为 get 和 add 方法的实现。

get 方法实现原理

get 方法的源码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
public E get(int index) {
    return get(getArray(), index);
}
/**
 * Gets the array.  Non-private so as to also be accessible
 * from CopyOnWriteArraySet class.
 */
final Object[] getArray() {
    return array;
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

可以看出来 get 方法实现非常简单，几乎就是一个“单线程”程序，没有对多线程添加任何的线程安全控制，也没有加锁也没有 CAS 操作等等，原因是，所有的读线程只是会读取数据容器中的数据，并不会进行修改。

add 方法实现原理

再来看下如何进行添加数据的？add 方法的源码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
	//1. 使用Lock,保证写线程在同一时刻只有一个
    lock.lock();
    try {
		//2. 获取旧数组引用
        Object[] elements = getArray();
        int len = elements.length;
		//3. 创建新的数组，并将旧数组的数据复制到新数组中
        Object[] newElements = Arrays.copyOf(elements, len + 1);
		//4. 往新数组中添加新的数据
		newElements[len] = e;
		//5. 将旧数组引用指向新的数组
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

add 方法的逻辑也比较容易理解，请看上面的注释。需要注意这么几点：

  1. 采用 ReentrantLock，保证同一时刻只有一个写线程正在进行数组的复制，否则的话内存中会有多份被复制的数据；
  2. 前面说过数组引用是 volatile 修饰的，因此将旧的数组引用指向新的数组，根据 volatile 的 happens-before 规则，写线程对数组引用的修改对读线程是可见的。
  3. 由于在写数据的时候，是在新的数组中插入数据的，从而保证读写实在两个不同的数据容器中进行操作。

总结

我们知道 COW 和读写锁都是通过读写分离的思想实现的，但两者还是有些不同，可以进行比较：

COW vs 读写锁

相同点：1. 两者都是通过读写分离的思想实现；2.读线程间是互不阻塞的

不同点：对读线程而言，为了实现数据实时性，在写锁被获取后，读线程会等待或者当读锁被获取后，写线程会等待，从而解决“脏读”等问题。也就是说如果使用读写锁依然会出现读线程阻塞等待的情况。而 COW 则完全放开了牺牲数据实时性而保证数据最终一致性，即读线程对数据的更新是延时感知的，因此读线程不会存在等待的情况。

对这一点从文字上还是很难理解，我们来通过 debug 看一下，add 方法核心代码为：

1
2
3
4
5
1.Object[] elements = getArray();
2.int len = elements.length;
3.Object[] newElements = Arrays.copyOf(elements, len + 1);
4.newElements[len] = e;
5.setArray(newElements);

假设 COW 的变化如下图所示：

http://static.cyblogs.com/QQ20200216-233236@2x.jpg

数组中已有数据 1,2,3，现在写线程想往数组中添加数据 4，我们在第 5 行处打上断点，让写线程暂停。读线程依然会“不受影响”的能从数组中读取数据，可是还是只能读到 1,2,3。如果读线程能够立即读到新添加的数据的话就叫做能保证数据实时性。当对第 5 行的断点放开后，读线程才能感知到数据变化，读到完整的数据 1,2,3,4，而保证数据最终一致性，尽管有可能中间间隔了好几秒才感知到。

这里还有这样一个问题： 为什么需要复制呢？ 如果将 array 数组设定为 volitile 的， 对 volatile 变量写 happens-before 读，读线程不是能够感知到 volatile 变量的变化。

原因是，这里 volatile 的修饰的仅仅只是数组引用，数组中的元素的修改是不能保证可见性的。因此 COW 采用的是新旧两个数据容器，通过第 5 行代码将数组引用指向新的数组。

这也是为什么 concurrentHashMap 只具有弱一致性的原因，关于 concurrentHashMap 的弱一致性可以看这篇文章。

COW 的缺点

CopyOnWrite 容器有很多优点，但是同时也存在两个问题，即内存占用问题和数据一致性问题。所以在开发的时候需要注意一下。

  1. 内存占用问题：因为 CopyOnWrite 的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对 象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对 象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。如果这些对象占用的内存比较大，比 如说 200M 左右，那么再写入 100M 数据进去，内存就会占用 300M，那么这个时候很有可能造成频繁的 minor GC 和 major GC。
  2. 数据一致性问题：CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用 CopyOnWrite 容器。

参考文章

如果大家喜欢我的文章，可以关注个人订阅号。欢迎随时留言、交流。如果想加入微信群的话一起讨论的话，请加管理员简栈文化-小助手（lastpass4u），他会拉你们进群。

简栈文化服务订阅号