并发编程6：CopyOnWriteArrayList 的写时复制

淩亂°似流年 2022-06-10 13:15 208阅读 0赞

> 首先提个问题：
> 
>  *  线程安全的 List 集合有什么？
>  *  CopyOnWriteArrayList 的特点以及使用场景？
> 
> 如果这个问题你答不上来，那这篇文章可能就对你有些价值。

读完本文你将了解：

*  CopyOnWriteArrayList 简介
 *  CopyOnWriteArrayList 源码分析Android SDK 25
    
     *  底部实现
     *  读取操作
     *  修改操作
     *  迭代器
 *  CopyOnWriteArrayList 源码 JDK8 有什么不同
 *  总结
    
     *  优缺点
 *  Thanks

# CopyOnWriteArrayList 简介 #

在 Java 中多线程读写 List，有两种选择：

1.  Vector
2.  CopyOnWriteArrayList

[ Java 集合深入理解：古老的 Vector][Java _ Vector] 中我们了解到 `Vector` 几乎所有的读写操作都加了 synchronized ，意味着在多线程环境下，如果有多个线程同时想要操作这个 Vector，必须串行排队等着前面的操作完了才能下一个。

就好比我和小肉一起写一个项目，每次得等她完全写完要写的，我才能接着写，这效率实在差了点。

好在有 Git，小肉想帮我修改程序员审美 UI 时，可以拷贝一份代码进行修改，修改完后再合并到远程。

> Git 多人协作流程：  
> 当有人要修改代码时，拉取服务端代码到本地，先修改本地的代码，然后再提交到服务器，这样可以避免直接修改远端代码对别人造成的影响。  
> ![这里写图片描述][SouthEast]

`CopyOnWriteArrayList` 是一个**线程安全**的随机访问列表，实现了 `List` 接口：

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
        
        //...
    }

它的思想和 Git 有些相似，即使在多个线程中被并发访问， `CopyOnWriteArrayList` 的读操作（比如 `get()`）也不会阻塞其他操作；写操作则是通过复制一份，对复制版本进行操作，不会影响原来的数据。

和 `Vector` 相对效率提高不少。缺点就是可能读取的不是最新的值。

批量操作（比如 `addAll()`, `clear()`）是原子的，也就是说不存在重排序导致的未赋值就访问等情况。

在 [ Java 集合源码解析：Iterator][Java _Iterator] 中我们了解到：

> 在调用迭代器的 next，remove 方法时都会比较 expectedModCount 和 modCount 是否相等，如果不相等就会抛出 ConcurrentModificationException ，也就是成为了 fail-fast。

如果需要在遍历时操作列表，其中一种解决办法就是使用 `CopyOnWriteArrayList` ，它的迭代器永远不会抛出 `ConcurrentModificationException`异常。原因在于：**在创建一个迭代器时，它会拷贝一份列表数据，这样即使操作列表也不会影响迭代器，缺点和前面一样，可能无法反映数据的最新状态。**

# CopyOnWriteArrayList 源码分析（Android SDK 25） #

从名字就可以看出来 `CopyOnWriteArrayList` 的特点是 “CopyOnWrite”（写时复制），即在写入新元素时不直接操作原容器，而是先复制一个快照，对这个快照进行操作，在操作结束后再将原容器的引用指向新引用。

## 底部实现 ##

private transient volatile Object[] elements;

`CopyOnWriteArrayList` 底层也是一个数组，不同之处在于它被 volatile 修饰，对它的修改、读取具有“可见性”、“有序性”（但不保证原子性），因此可以不加同步块，直接读取。

有三种构造函数：

public CopyOnWriteArrayList() {
        elements = EmptyArray.OBJECT;
    }
    
    @SuppressWarnings("unchecked")
    public CopyOnWriteArrayList(Collection<? extends E> collection) {
        this((E[]) collection.toArray());
    }
    
    public CopyOnWriteArrayList(E[] array) {
        this.elements = Arrays.copyOf(array, array.length, Object[].class);
    }

分别创建了空的数组、使用指定集合和数组来创建新数组。

## 读取操作 ##

先看简单的几个读取操作：

public int size() {
        return elements.length;
    }
    
    @SuppressWarnings("unchecked")
    public E get(int index) {
        return (E) elements[index];
    }
    public boolean isEmpty() {
        return elements.length == 0;
    }

就是直接读取数组的内容，简单粗暴，快速高效。

## 修改操作 ##

读取时轻松，但修改时就需要做同步操作了。先看添加元素 `add()`：

public synchronized boolean add(E e) {
        Object[] newElements = new Object[elements.length + 1];
        System.arraycopy(elements, 0, newElements, 0, elements.length);
        newElements[elements.length] = e;
        //这步执行前，其他线程访问的就是旧数据
        elements = newElements;
        return true;
    }
    
    public synchronized void add(int index, E e) {
        Object[] newElements = new Object[elements.length + 1];
        System.arraycopy(elements, 0, newElements, 0, index);
        newElements[index] = e;
        System.arraycopy(elements, index, newElements, index + 1, elements.length - index);
        elements = newElements;
    }

可以看到，在添加元素时调用 `System.arraycopy()` 拷贝了一个新数组，然后添加进去元素，最后将原数组的引用修改为拷贝数组。

**如果其他线程在“原始数组引用更新”之前读取数据，那它访问到的就是旧数据。**

**方法被 `synchronized` 修饰，因此在这个过程中，其他调用这个方法的线程都会阻塞等待，只有这个方法结束后才有获得锁的机会。**

`set()` 方法也是类似的：

public synchronized E set(int index, E e) {
        Object[] newElements = elements.clone();
        @SuppressWarnings("unchecked")
        E result = (E) newElements[index];
        newElements[index] = e;
        elements = newElements;
        return result;
    }

删除操作 `` `remove()`` 也是类似:

public synchronized E remove(int index) {
        @SuppressWarnings("unchecked")
        E removed = (E) elements[index];
        removeRange(index, index + 1);
        return removed;
    }
    
    public synchronized boolean remove(Object o) {
        int index = indexOf(o);
        if (index == -1) {
            return false;
        }
        remove(index);
        return true;
    }
    private void removeRange(int from, int to) {
        Object[] newElements = new Object[elements.length - (to - from)];
        System.arraycopy(elements, 0, newElements, 0, from);
        System.arraycopy(elements, to, newElements, from, elements.length - to);
        elements = newElements;
    }

## 迭代器 ##

public Iterator<E> iterator() {
        Object[] snapshot = elements;    //读取的是快照
        return new CowIterator<E>(snapshot, 0, snapshot.length);
    }
    
    //读取的也是快照，并且不支持 remove() 
    public ListIterator<E> listIterator(int index) {
        Object[] snapshot = elements;
        if (index < 0 || index > snapshot.length) {
            throw new IndexOutOfBoundsException("index=" + index + ", length=" + snapshot.length);
        }
        CowIterator<E> result = new CowIterator<E>(snapshot, 0, snapshot.length);
        result.index = index;
        return result;
    }
    
    /**
     * Equivalent to {@code listIterator(0)}.
     */
    public ListIterator<E> listIterator() {
        Object[] snapshot = elements;
        return new CowIterator<E>(snapshot, 0, snapshot.length);
    }

返回的迭代器是 `CowIterator`，实现了 `ListIterator` 接口:

static class CowIterator<E> implements ListIterator<E> {
        
            private final Object[] snapshot;
            private final int from;
            private final int to;
            private int index = 0;
    
            CowIterator(Object[] snapshot, int from, int to) {
                this.snapshot = snapshot;
                this.from = from;
                this.to = to;
                this.index = from;
            }
    
            public void add(E object) {
                throw new UnsupportedOperationException();
            }
            //...
    
            public void remove() {
                throw new UnsupportedOperationException();
            }
    
            public void set(E object) {
                throw new UnsupportedOperationException();
            }
            //...
    }

可以看到 `CopyOnWriteArrayList` 或者它的子列表返回的迭代器不能修改列表数据，尤其是 `Iterator.remove()`, `ListIterator.add()`, `ListIterator.set()` 方法都会抛出 `UnsupportedOperationException` 异常。

# CopyOnWriteArrayList 源码 JDK8 有什么不同 #

看完 android-25 的 `CopyOnWriteArrayList` 代码，再去看 JDK8 的，发现两者差别有点大啊，真是坑。

在[知乎的一个问题][Link 1]下了解了 Android SDK 的 Java 源码为什么和 JDK 不一致，摘抄如下：

> Android 使用的Java 库是Apache的Harmony, 与官方Java库接口相同，里面实现不一样。
> 
> 就在06年的时候Sun公司宣布会将JDK开源，但是直到2009年4月才正式发布，而Android已经在2008年发布第一步部智能手机了。所以Google最早的时候使用了当时Apache的Java开源实现Harmony项目。
> 
> 可惜Sun公司一直不承认Harmony，前不久Harmony那一帮人怒了，给Oracle放狠话说再不承认我我就抵制Java7，结果反倒把Google吓坏了，于是就出现了google宣布切换到openjdk上这条新闻。在Android N上，已经切换到OpenJDK了；基本可以认为Android SDK下的源码与JDK相同。
> 
> 作者：weishu  
> 链接：[https://www.zhihu.com/question/40103672/answer/84730730][https_www.zhihu.com_question_40103672_answer_84730730]  
> 来源：知乎

JDK8 中的 `CopyOnWriteArrayList` 底层实现也是数组，不同之处在于使用 Lock 而不是 synchronized 进行同步：

public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
        
        private static final long serialVersionUID = 8673264195747942595L;
    
        //锁住所有修改操作
        final transient ReentrantLock lock = new ReentrantLock();
    
        //只能被getArray/setArray 访问
        private transient volatile Object[] array;
        //...
    }

**构造函数**也有些区别：

final void setArray(Object[] a) {
        array = a;
    }
    
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }
    
    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);
    }
    
    public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

在使用集合作为参数构造时，做了一些优化：如果这个集合也是 `CopyOnWriteArrayList`，就直接指向该集合的数组；否则复制一下。

**读取操作**没什么变化，都是读的数组，不同之处在于通过 getter 方法包了一层：

public int size() {
        return getArray().length;
    }
    
    public boolean isEmpty() {
        return size() == 0;
    }
    
    private E get(Object[] a, int index) {
        return (E) a[index];
    }
    
    public E get(int index) {
        return get(getArray(), index);
    }

**添加操作 `add()`**：

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

唯一的区别就是使用了 `ReentrantLock`，它和 `synchronized` 的区别大致如下：

*  synchronized 无法中断一个正在等候获得锁的线程，也无法通过投票得到锁
 *  ReentrantLock 拥有与 synchronized 相同的并发性和内存语义，但是添加了类似锁投票、定时锁等候和可中断锁等候的一些特性

> 摘自：[http://blog.csdn.net/fw0124/article/details/6672522][http_blog.csdn.net_fw0124_article_details_6672522]

**删除操作**也差不多：

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

# 总结 #

核心思想就两点：

1.  底部实现（这里是数组） volatile 修饰，保证一致性
2.  写时复制，写完更新引用

有了这两点，我们自己写个 `CopyOnWriteHashMap` 也是分分钟的事，有兴趣可以自己写一下。

## 优缺点 ##

优点：

*  可以在多线程环境下操作 List
 *  读的效率很高

缺点：

*  读的可能不是最新值
 *  每次写需要创建个新数组，占用额外内存

可以看到，应该在并发读远大于并发写的情况下使用这个容器，比如保存缓存数据。

> 类似的思想还有个 `CopyOnWriteArraySet`。

# Thanks #

[http://ifeve.com/java-copy-on-write/][http_ifeve.com_java-copy-on-write]  
[http://blog.csdn.net/fw0124/article/details/6672522][http_blog.csdn.net_fw0124_article_details_6672522]  
[http://coolshell.cn/articles/11175.html][http_coolshell.cn_articles_11175.html]

[Java _ Vector]: http://blog.csdn.net/u011240877/article/details/52900893
[SouthEast]: /images/20220610/69214febc341442fa7746c4f79544765.png
[Java _Iterator]: http://blog.csdn.net/u011240877/article/details/52743564#t17
[Link 1]: https://www.zhihu.com/question/40103672?from=profile_question_card
[https_www.zhihu.com_question_40103672_answer_84730730]: https://www.zhihu.com/question/40103672/answer/84730730
[http_blog.csdn.net_fw0124_article_details_6672522]: http://blog.csdn.net/fw0124/article/details/6672522
[http_ifeve.com_java-copy-on-write]: http://ifeve.com/java-copy-on-write/
[http_coolshell.cn_articles_11175.html]: http://coolshell.cn/articles/11175.html