Java并发——CopyOnArrayList

发布于

一、CopyOnArrayList概述

1.1 概述

ArrayList是线程不安全的集合，而CopyOnWriteArrayList是一种线程安全的ArrayList，底层是基于数组实现，不过该数组使用了volatile关键字修饰。

实现线程安全的原理是，“人如其名”，就是 Copy On Write（写时复制），意思就是在对其进行修改操作的时候，复制一个新的ArrayList，在新的ArrayList上进行修改操作，从而不影响旧的ArrayList的读操作，完成修改之后，再将原容器的引用指向新的容器。

1.2 优点

线程安全

通过volatile关键字 + 锁 + 数组复制实现的线程安全

CopyOnWriteArrayList 利用了“不变性”原理，因为容器每次修改都是创建新副本，所以对于旧容器来说，其实是不可变的，也是线程安全的，无需进一步的同步操作。我们可以对 CopyOnWrite 容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素，也不会有修改。

读写分离

CopyOnWriteArrayList 的所有修改操作（add，set等）都是通过创建底层数组的新副本来实现的，所以 CopyOnWrite 容器也是一种读写分离的思想体现，读和写使用不同的容

迭代期间允许修改集合内容

CopyOnWriteArrayList 的迭代器在迭代的时候，如果数组内容被修改了，CopyOnWriteArrayList 不会报 ConcurrentModificationException 的异常，因为迭代器使用的依然是旧数组，只不过迭代的内容可能已经过时了

1.3 缺点

内存占用问题

因为 CopyOnWrite 的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，这一点会占用额外的内存空间

在元素较多或者复杂的情况下，复制的开销很大

复制过程不仅会占用双倍内存，还需要消耗 CPU 等资源，会降低整体性能

数据一致性问题

数据不是强一致的，是弱一致的

由于 CopyOnWrite 容器的修改是先修改副本，所以这次修改对于其他线程来说，并不是实时能看到的，只有在修改完之后才能体现出来。如果你希望写入的的数据马上能被其他线程看到，CopyOnWrite 容器是不适用的

二、适用场景

读操作可以尽可能的快，而写即使慢一些也没关系

在很多应用场景中，读操作可能会远远多于写操作。比如，有些系统级别的信息，往往只需要加载或者修改很少的次数，但是会被系统内所有模块频繁的访问。对于这种场景，我们最希望看到的就是读操作可以尽可能的快，而写即使慢一些也没关系。

再例如，新闻的场景

适合读多写少的场景

黑名单是最典型的场景，假如我们有一个搜索网站，用户在这个网站的搜索框中，输入关键字搜索内容，但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单中，黑名单并不需要实时更新，可能每天晚上更新一次就可以了。当用户搜索时，会检查当前关键字在不在黑名单中，如果在，则提示不能搜索。这种读多写少的场景也很适合使用 CopyOnWrite 集合。

三、CopyOnArrayList原理

使用ReentrantLock加锁，保证操作过程中线程安全。

使用volatile关键字修饰数组，保证当前线程对数组对象重新赋值后，其他线程可以及时感知到

四、源码分析

数据结构

代码语言：java
复制
public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();

/** CopyOnWriteArrayList底层由数组实现，volatile修饰，保证数组的可见性 */
private transient volatile Object[] array;

/**
 * Gets the array.  Non-private so as to also be accessible
 * from CopyOnWriteArraySet class.
 */
final Object[] getArray() {
    return array;
}
//初始化CopyOnWriteArrayList相当于初始化数组
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}</code></pre></div></div><h3 id="1k05p" name="%E6%B7%BB%E5%8A%A0%E5%85%83%E7%B4%A0-add">添加元素 add</h3><p>添加元素的流程：</p><p>①先使用ReentrantLock加锁，保证线程安全。</p><p>②再创建一个新数组，长度是原数组长度+1，并把原数组元素拷贝到新数组里面。</p><p>③然后在新数组末尾位置赋值</p><p>④使用新数组替换掉原数组</p><p>⑤最后释放锁</p><div class="rno-markdown-code"><div class="rno-markdown-code-toolbar"><div class="rno-markdown-code-toolbar-info"><div class="rno-markdown-code-toolbar-item is-type"><span class="is-m-hidden">代码语言：</span>java</div></div><div class="rno-markdown-code-toolbar-opt"><div class="rno-markdown-code-toolbar-copy"><i class="icon-copy"></i><span class="is-m-hidden">复制</span></div></div></div><div class="developer-code-block"><pre class="prism-token token line-numbers language-java"><code class="language-java" style="margin-left:0">    /**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    // 加锁，保证线程安全
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 获取原数组
        Object[] elements = getArray();
        int len = elements.length;
        // 创建一个新数组，长度原数组长度+1，并把原数组元素拷贝到新数组里面
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 直接赋值给新数组末尾位置
        newElements[len] = e;
        // 替换原数组
        setArray(newElements);
        // 释放锁
        return true;
    } finally {
        lock.unlock();
    }
}</code></pre></div></div><h3 id="8nrqv" name="get">get</h3><p>get 相关的操作没有加锁，保证了读取操作的高速</p><div class="rno-markdown-code"><div class="rno-markdown-code-toolbar"><div class="rno-markdown-code-toolbar-info"><div class="rno-markdown-code-toolbar-item is-type"><span class="is-m-hidden">代码语言：</span>java</div></div><div class="rno-markdown-code-toolbar-opt"><div class="rno-markdown-code-toolbar-copy"><i class="icon-copy"></i><span class="is-m-hidden">复制</span></div></div></div><div class="developer-code-block"><pre class="prism-token token line-numbers language-java"><code class="language-java" style="margin-left:0">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];

}

set

代码语言：java
复制
/**

* Replaces the element at the specified position in this list with the

* specified element.

*

* @throws IndexOutOfBoundsException {@inheritDoc}

*/

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();
    }
}</code></pre></div></div><h3 id="49eb8" name="remove%E5%88%A0%E9%99%A4%E5%85%83%E7%B4%A0">remove删除元素</h3><p>删除元素的流程：</p><p>①先使用ReentrantLock加锁，保证线程安全。</p><p>②再创建一个新数组，长度是原数组长度-1，并把原数组中剩余元素（不包含需要删除的元素）拷贝到新数组里面。</p><p>③使用新数组替换掉原数组</p><p>④最后释放锁</p><div class="rno-markdown-code"><div class="rno-markdown-code-toolbar"><div class="rno-markdown-code-toolbar-info"><div class="rno-markdown-code-toolbar-item is-type"><span class="is-m-hidden">代码语言：</span>java</div></div><div class="rno-markdown-code-toolbar-opt"><div class="rno-markdown-code-toolbar-copy"><i class="icon-copy"></i><span class="is-m-hidden">复制</span></div></div></div><div class="developer-code-block"><pre class="prism-token token line-numbers language-java"><code class="language-java" style="margin-left:0">// 按照下标删除元素



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) {
        // 0表示删除的是数组末尾的元素
        setArray(Arrays.copyOf(elements, len - 1));
    } else {
        // 创建一个新数组，长度是原数组长度-1
        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();
}



}

迭代器

迭代器有两个重要的属性，分别是 Object[] snapshot 和 int cursor。

其中 snapshot 代表数组的快照，也就是创建迭代器那个时刻的数组情况，而 cursor 则是迭代器的游标。

迭代器在被构建的时候，会把当时的 elements 赋值给 snapshot，而之后的迭代器所有的操作都基于 snapshot 数组进行的

在 next 方法中可以看到，返回的内容是 snapshot 对象，所以，后续就算原数组被修改，这个 snapshot 既不会感知到，也不会受影响，执行迭代操作不需要加锁，也不会因此抛出异常。迭代器返回的结果，和创建迭代器的时候的内容一致

代码语言：java
复制
static final class COWIterator<E> implements ListIterator<E> {

/** Snapshot of the array /

private final Object[] snapshot;

/* Index of element to be returned by subsequent call to next.  */

private int cursor;


    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }

    public boolean hasNext() {
        return cursor &lt; snapshot.length;
    }

    public boolean hasPrevious() {
        return cursor &gt; 0;
    }

    @SuppressWarnings(&#34;unchecked&#34;)
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }</code></pre></div></div><h2 id="8nllm" name="%E4%BA%94%E3%80%81Demo">五、Demo</h2><div class="rno-markdown-code"><div class="rno-markdown-code-toolbar"><div class="rno-markdown-code-toolbar-info"><div class="rno-markdown-code-toolbar-item is-type"><span class="is-m-hidden">代码语言：</span>java</div></div><div class="rno-markdown-code-toolbar-opt"><div class="rno-markdown-code-toolbar-copy"><i class="icon-copy"></i><span class="is-m-hidden">复制</span></div></div></div><div class="developer-code-block"><pre class="prism-token token line-numbers language-java"><code class="language-java" style="margin-left:0">/**



    

  • 描述： 演示CopyOnWriteArrayList迭代期间可以修改集合的内容
    
*/
    • 



public class CopyOnWriteArrayListDemo {


public static void main(String[] args) {
    CopyOnWriteArrayList&lt;Integer&gt; list = new CopyOnWriteArrayList&lt;&gt;(new Integer[]{1, 2, 3});
    System.out.println(list); //[1, 2, 3]

    //Get iterator 1
    Iterator&lt;Integer&gt; itr1 = list.iterator();
    //Add one element and verify list is updated
    list.add(4);
    System.out.println(list); //[1, 2, 3, 4]
    //Get iterator 2
    Iterator&lt;Integer&gt; itr2 = list.iterator();
    System.out.println(&#34;====Verify Iterator 1 content====&#34;);
    itr1.forEachRemaining(System.out::println); //1,2,3
    System.out.println(&#34;====Verify Iterator 2 content====&#34;);
    itr2.forEachRemaining(System.out::println); //1,2,3,4

}



}
代码语言：java
复制
[1, 2, 3]


[1, 2, 3, 4]


====Verify Iterator 1 content====


1


2


3


====Verify Iterator 2 content====


1


2


3


4

这两个迭代器打印出来的内容是不一样的。第一个迭代器打印出来的是 1, 2, 3，而第二个打印出来的是 1, 2, 3, 4。虽然它们的打印时机都发生在第四个元素被添加之后，但它们的创建时机是不同的。由于迭代器 1 被创建时的 List 里面只有三个元素，后续无论 List 有什么修改，对它来说都是无感知的

#并发#高并发#java