阿里面试官没想到，一个CopyOnWriteArrayList，我都能跟他吹半小时

亦凉 2021-05-12 11:50 378阅读 0赞

阿里面试官没想到，一个Java 的 CopyOnWriteArrayList，我都能跟他吹半小时，惊呆了。

> 先看再点赞，给自己一点思考的时间，微信搜索【**沉默王二**】关注这个靠才华苟且的程序员。  
> 本文 **GitHub** [github.com/itwanger][github.com_itwanger] 已收录，里面还有一线大厂整理的面试题，以及我的系列文章。

hello，同学们，大家好，我是沉默王二，在我为数不多的面试经历中，有一位姓马的面试官令我印象深刻，九年过去了，我还能记得他为数不多的发量。

老马：“兄弟，ArrayList 是线程安全的吗？”  
王二：“不是啊。”  
老马：“那有没有线程安全的 List？”  
王二：“有啊，Vector。”  
老马：“还有别的吗？”  
王二：“Vector 不就够用了吗？”  
老马看了一下左手腕上的表，说道：“今天差不多就到这里吧，你回去等通知。”

（不是，我特么不是刚进来，就回答了三个问题而已，就到这了？）

现在回想起来当时一脸懵逼的样子，脸上情不自禁地泛起了红晕，老马的意思是让我说说 Java 的 CopyOnWriteArrayList，可惜我当时几乎没怎么用过这个类，也不知道它就是个线程安全的 List，惭愧啊惭愧。

（地上有坑吗？我想跳进去。）

真正的勇士敢于直面过去的惨淡，经过这么多年的努力，我的技术功底已经大有长进了，是时候输出一波伤害了。希望这篇文章能够给不太了解 CopyOnWriteArrayList 的同学一点点帮助，到时候给面试官一个好看。

注：我用的是 OpenJDK 14。

### 01、Vector ###

Vector 的源码文档上直截了当地说了，“如果不需要线程安全，推荐使用 ArrayList 替代 Vector。”说实话，在我十多年的编程生涯中，的确很少使用 Vector，因为它的线程安全是建立在每个方法上都加了 `synchronized` 关键字的基础上，锁的粒度很高，意味着性能就不咋滴。

public synchronized boolean add(E e) { 
        modCount++;
        add(e, elementData, elementCount);
        return true;
    }
    
    public synchronized E remove(int index) { 
        modCount++;
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);
        E oldValue = elementData(index);
    
        int numMoved = elementCount - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        elementData[--elementCount] = null; // Let gc do its work
    
        return oldValue;
    }

就连 `size()` 这样的方法上都加了 synchronized，可想而知，Vector 有多铺张浪费，有多锦衣玉食。

如果对 synchronized 关键字不太了解的话，可以点击下面的链接查看我之前写的一篇文章。

[我去，你竟然还不会用 synchronized][synchronized]

高并发的情况下，一般都要求性能要给力，Vector 显然不够格，所以被遗忘在角落也是“罪有应得”啊。

### 02、SynchronizedList ###

那有些同学可能会说，可以使用 `Collections.synchronizedList()` 让 ArrayList 变成线程安全啊。

public static <T> List<T> synchronizedList(List<T> list) { 
        return (list instanceof RandomAccess ?
                new Collections.SynchronizedRandomAccessList<>(list) :
                new Collections.SynchronizedList<>(list));
    }

无论是 SynchronizedRandomAccessList 还是 SynchronizedList，它们都没有在方法级别上使用 synchronized 关键字，而是在方法体内使用了 `synchronized(this)` 块。

public void add(int index, E element) { 
        synchronized (mutex) { list.add(index, element);}
    }
    public E remove(int index) { 
        synchronized (mutex) { return list.remove(index);}
    }

其中 mutex 为 this 关键字，也就是当前对象。

final Object mutex;     // Object on which to synchronize
    
    SynchronizedCollection(Collection<E> c) { 
        this.c = Objects.requireNonNull(c);
        mutex = this;
    }

### 03、ConcurrentModificationException ###

ConcurrentModificationException 这个异常不知道同学们有没有遇到过？我先来敲段代码让它发生一次，让同学们认识一下。

List<String> list = new ArrayList<>();
    list.add("沉默王二");
    list.add("沉默王三");
    list.add("一个文章真特么有趣的程序员");
    
    for (String str : list) { 
        if ("沉默王二".equals(str)) { 
            list.remove(str);
        }
    }
    
    System.out.println(list);

运行这段代码就会抛出 ConcurrentModificationException：

Exception in thread "main" java.util.ConcurrentModificationException
    	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1012)
    	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:966)

通过异常的堆栈信息可以查找到，异常发生在 ArrayList 的内部类 Itr 的 `checkForComodification()` 方法中。

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

也就是说，在执行 `checkForComodification()` 方法的时候，发现 modCount 和 expectedModCount 不等，就抛出了 `ConcurrentModificationException` 异常。

为什么会这样呢？之前的代码也没有调用 `checkForComodification()` 方法啊！

那就只能来看一下反编译后的字节码了，原来 for-each 这个语法糖是通过 Iterator 实现的。

List<String> list = new ArrayList();
    list.add("沉默王二");
    list.add("沉默王三");
    list.add("一个文章真特么有趣的程序员");
    Iterator var3 = list.iterator();
    
    while (var3.hasNext()) { 
    	String str = (String) var3.next();
    	if ("沉默王二".equals(str)) { 
    		list.remove(str);
    	}
    }
    
    System.out.println(list);

在执行 `list.iterator()` 的时候，其实返回的就是 ArrayList 的内部类 Itr。

public Iterator<E> iterator() { 
        return new ArrayList.Itr();
    }

迭代器 Iterator 是 fail-fast 的，如果以任何方式（包括 remove 和  
add）对迭代器进行修改的话，就会抛出 ConcurrentModificationException。

迭代器在执行 `remove()` 方法的时候，会对 modCount 加 1。`remove()` 方法内部会调用 `fastRemove()` 方法。

private void fastRemove(Object[] es, int i) { 
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }

当在进行下一次 `next()` 会执行 `checkForComodification()` 方法，结果发现 modCount 为 4，而 expectedModCount 为 3，于是就抛出了异常。

![format_png][]

之所以在单线程的情况下就抛出 ConcurrentModificationException，就是为了在多线程并发的情况下，不冒任何的危险，提前规避掉其他线程对 List 修改的可能性。

ArrayList 返回的迭代器是 fail-fast 的，Vector 的也是，SynchronizedList 的也是。这就意味着它们在多线程环境下通过 for-each 遍历进行增删操作的时候会出问题。

### 04、CopyOnWriteArrayList ###

瞧，为了引出 CopyOnWriteArrayList，我花了多少心思。

List<String> list = new CopyOnWriteArrayList();
    list.add("沉默王二");
    list.add("沉默王三");
    list.add("一个文章真特么有趣的程序员");
    
    for (String str : list) { 
        if ("沉默王二".equals(str)) { 
            list.remove(str);
        }
    }
    
    System.out.println(list);

把 ArrayList 换成 CopyOnWriteArrayList，程序就能够正常执行了，输出结果如下所示。

[沉默王三, 一个文章真特么有趣的程序员]

之所以不抛出 ConcurrentModificationException 异常，是因为 CopyOnWriteArrayList 是 fail-safe 的，迭代器遍历的是原有的数组，remove 的时候 remove 的是复制后的新数组，然后再将新数组赋值给原有的数组。

不过，任何在获取迭代器之后对 CopyOnWriteArrayList 的修改将不会及时反映迭代器里。

CopyOnWriteArrayList<String> list1 =
            new CopyOnWriteArrayList<>(new String[] { "沉默王二", "沉默王三"});
    Iterator itr = list1.iterator();
    list1.add("沉默王四");
    while(itr.hasNext()) { 
        System.out.print(itr.next() + " ");
    }

沉默王四并不会出现在输出结果中。

沉默王二 沉默王三

ArrayList 的迭代器 Itr 是支持 remove 的。

List<String> list = new ArrayList();
    list.add("沉默王二");
    list.add("沉默王三");
    list.add("一个文章真特么有趣的程序员");
    Iterator var3 = list.iterator();
    
    while (var3.hasNext()) { 
        String str = (String) var3.next();
        if ("沉默王二".equals(str)) { 
            var3.remove();
        }
    }
    
    System.out.println(list);

程序输出的结果如下所示：

[沉默王三, 一个文章真特么有趣的程序员]

而 CopyOnWriteArrayList 的迭代器 COWIterator 是不支持 remove 的。

public void remove() { 
                throw new UnsupportedOperationException();
            }

![format_png 1][]

CopyOnWriteArrayList 实现了 List 接口，不过，它不在 java.util 包下，而在 java.util.concurrent 包下，算作是 ArrayList 的增强版，线程安全的。

顾名思义，CopyOnWriteArrayList 在进行写操作（add、set、remove）的时候会先进行拷贝，底层是通过数组复制来实现的。

Java 8 的时候，CopyOnWriteArrayList 的增删改操作方法使用的是 ReentrantLock（可重入锁，一个线程获得了锁之后仍然可以反复的加锁，不会出现自己阻塞自己的情况）。

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);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally { 
            lock.unlock();
        }
    }

Java 14 的时候，已经改成 synchronized 块了。

public boolean add(E e) { 
        synchronized (lock) { 
            Object[] es = getArray();
            int len = es.length;
            es = Arrays.copyOf(es, len + 1);
            es[len] = e;
            setArray(es);
            return true;
        }
    }

其中的 lock 是一个 Object 对象（注释上说和 ReentrantLock 有一点关系）。

/** * The lock protecting all mutators. (We have a mild preference * for builtin monitors over ReentrantLock when either will do.) */
    final transient Object lock = new Object();

使用 ReentrantLock 性能更好，还是 synchronized 块性能更好，同学们可以试验一下。不过，从另外一些细节上看，Java 14 的写法比 Java 8 更简洁一些，其中就少了一个 newElements 变量的创建。

再来看 `set()` 方法：

public E set(int index, E element) { 
        synchronized (lock) { 
            Object[] es = getArray();
            E oldValue = elementAt(es, index);
    
            if (oldValue != element) { 
                es = es.clone();
                es[index] = element;
            }
            // Ensure volatile write semantics even when oldvalue == element
            setArray(es);
            return oldValue;
        }
    }

同样使用了 synchronized 块，并且调用了封装好的 `clone()` 方法进行了复制。

然后来看 `remove()` 方法：

public E remove(int index) { 
        synchronized (lock) { 
            Object[] es = getArray();
            int len = es.length;
            E oldValue = elementAt(es, index);
            int numMoved = len - index - 1;
            Object[] newElements;
            if (numMoved == 0)
                newElements = Arrays.copyOf(es, len - 1);
            else { 
                newElements = new Object[len - 1];
                System.arraycopy(es, 0, newElements, 0, index);
                System.arraycopy(es, index + 1, newElements, index,
                        numMoved);
            }
            setArray(newElements);
            return oldValue;
        }
    }

synchronized 块是必须的，数组复制（`System.arraycopy()`）也是必须的。

和 Vector 不同的是，CopyOnWriteArrayList 的 `get()`、`size()` 方法不再加锁。

public int size() { 
        return getArray().length;
    }
    
    public E get(int index) { 
        return elementAt(getArray(), index);
    }

简单总结一下就是：第一，CopyOnWriteArrayList 在修改时，复制出一个新数组，修改的操作在新数组中完成，最后将新数组赋值给原有的数组引用。第二，CopyOnWriteArrayList 的写加锁，读不加锁。

CopyOnWriteArrayList 有很多优势，但数组复制是沉重的，如果写的操作比较多，而读的操作比较少，内存就会被占用得比较多；另外，CopyOnWriteArrayList 无法保证数据是实时同步的，因为读写操作是分离的，写的操作都建立在复制的新数组上，而读的是原有的数组。

### 05、最后 ###

如果九年前，我就看到了这样一篇文章，一定就不会被老马刁难呢，保不准还能再拖延半个小时，让他多问二十个问题。但我想同学们一定是比我幸运的，至少现在看到了，不晚，对不对？

--------------------

我是沉默王二，一枚有颜值却靠才华苟且的程序员。**关注即可提升学习效率，别忘了三连啊，点赞、收藏、留言，我不挑，奥利给**。

注：如果文章有任何问题，欢迎毫不留情地指正。

如果你觉得文章对你有些帮助欢迎微信搜索「**沉默王二**」第一时间阅读，回复「**小白**」更有我肝了 4 万+字的 Java 小白手册 2.0 版，本文 **GitHub** [github.com/itwanger][github.com_itwanger] 已收录，欢迎 star。

[github.com_itwanger]: https://github.com/itwanger/itwanger.github.io
[synchronized]: https://mp.weixin.qq.com/s/yQx6GqWLnVOfSXqLRLD9Pw
[format_png]: /images/20210511/8e97e805321e41d6a4246091fe9c59cc.png
[format_png 1]: /images/20210511/cdb4f6b807944dd3ae4dad42eb32f631.png