关于面试:CopyOnWriteArrayList-使用入门及源码详解

35次阅读

共计 9896 个字符，预计需要花费 25 分钟才能阅读完成。

CopyOnWriteArrayList

官网定义

CopyOnWriteArrayList 是 ArrayList 的线程平安变体，其中通过创立底层数组的新副原本实现所有可变操作（增加，设置等）。

这通常老本太高，然而当遍历操作大大超过渐变时，它可能比代替办法更无效，并且当您不能或不想同步遍历但须要排除并发线程之间的烦扰时十分有用。

“快照”款式迭代器办法在创立迭代器时应用对数组状态的援用。

这个数组在迭代器的生命周期中永远不会扭转，所以烦扰是不可能的，并且保障迭代器不会抛出 ConcurrentModificationException。自迭代器创立以来，迭代器不会反映列表的增加，删除或更改。不反对对迭代器自身进行元素更改操作（删除，设置和增加）。这些办法抛出 UnsupportedOperationException。

容许所有元素，包含 null。

内存一致性成果：与其余并发汇合一样，在将对象放入 CopyOnWriteArrayList 之前，线程中的操作产生在从另一个线程中的 CopyOnWriteArrayList 拜访或删除该元素之后的操作之前。

应用例子

网上这种代码大同小异。

ArrayList 版本

上面来看一个列子：两个线程一个线程循环读取，一个线程批改 list 的值。

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class CopyOnWriteArrayListDemo {
    /**
     * 读线程
     */
    private static class ReadTask implements Runnable {
        List<String> list;

        public ReadTask(List<String> list) {this.list = list;}

        public void run() {for (String str : list) {System.out.println(str);
            }
        }
    }
    /**
     * 写线程
     */
    private static class WriteTask implements Runnable {
        List<String> list;
        int index;

        public WriteTask(List<String> list, int index) {
            this.list = list;
            this.index = index;
        }

        public void run() {list.remove(index);
            list.add(index, "write_" + index);
        }
    }

    public void run() {
        final int NUM = 10;
        List<String> list = new ArrayList<String>();
        for (int i = 0; i < NUM; i++) {list.add("main_" + i);
        }
        ExecutorService executorService = Executors.newFixedThreadPool(NUM);
        for (int i = 0; i < NUM; i++) {executorService.execute(new ReadTask(list));
            executorService.execute(new WriteTask(list, i));
        }
        executorService.shutdown();}

    public static void main(String[] args) {new CopyOnWriteArrayListDemo().run();}
}

这个运行后果会报错。

因为咱们在读取的时候，对列表进行了批改。

CopyOnWriteArrayList 版本

间接列表创立替换即可：

List<String> list = new CopyOnWriteArrayList<String>();

则运行后果失常。

CopyOnWriteArrayList 优缺点

长处

  1. 保障多线程的并发读写的线程平安

毛病

内存耗费

有数组拷贝天然有内存问题。如果理论利用数据比拟多，而且比拟大的状况下，占用内存会比拟大，这个能够用 ConcurrentHashMap 来代替。

  • 如何防止

内存占用问题。因为 CopyOnWrite 的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（留神: 在复制的时候只是复制容器里的援用，只是在写的时候会创立新对象增加到新容器里，而旧容器的对象还在应用，所以有两份对象内存）。如果这些对象占用的内存比拟大，比如说 200M 左右，那么再写入 100M 数据进去，内存就会占用 300M，那么这个时候很有可能造成频繁的 Yong GC 和 Full GC。之前咱们零碎中应用了一个服务因为每晚应用 CopyOnWrite 机制更新大对象，造成了每晚 15 秒的 Full GC，利用响应工夫也随之变长。

针对内存占用问题，能够通过压缩容器中的元素的办法来缩小大对象的内存耗费，比方，如果元素全是 10 进制的数字，能够思考把它压缩成 36 进制或 64 进制。或者不应用 CopyOnWrite 容器，而应用其余的并发容器，如 ConcurrentHashMap。

数据一致性

CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你心愿写入的的数据，马上能读到，请不要应用 CopyOnWrite 容器

应用场景

CopyOnWrite 并发容器用于读多写少的并发场景。

比方白名单，黑名单，商品类目标拜访和更新场景，如果咱们有一个搜寻网站，用户在这个网站的搜寻框中，输出关键字搜寻内容，然而某些关键字不容许被搜寻。这些不能被搜寻的关键字会被放在一个黑名单当中，黑名单每天晚上更新一次。当用户搜寻时，会查看以后关键字在不在黑名单当中，如果在，则提醒不能搜寻。

实现代码如下：

/**
 * 黑名单服务
 */
public class BlackListServiceImpl {
    private static CopyOnWriteMap<String, Boolean> blackListMap = new CopyOnWriteMap<String, Boolean>(1000);
    public static boolean isBlackList(String id) {return blackListMap.get(id) == null ? false : true;
    }
    public static void addBlackList(String id) {blackListMap.put(id, Boolean.TRUE);
    }
    /**
     * 批量增加黑名单
     *
     * @param ids
     */
    public static void addBlackList(Map<String,Boolean> ids) {blackListMap.putAll(ids);
    }
}

代码很简略，然而应用 CopyOnWriteMap 须要留神两件事件：

  1. 缩小扩容开销。依据理论须要，初始化 CopyOnWriteMap 的大小，防止写时 CopyOnWriteMap 扩容的开销。
  2. 应用批量增加。因为每次增加，容器每次都会进行复制，所以缩小增加次数，能够缩小容器的复制次数。如应用下面代码里的 addBlackList 办法。

为什么没有并发列表？

问：JDK 5 在 java.util.concurrent 里引入了 ConcurrentHashMap，在须要反对高并发的场景，咱们能够应用它代替 HashMap。

然而为什么没有 ArrayList 的并发实现呢？

难道在多线程场景下咱们只有 Vector 这一种线程平安的数组实现能够抉择么？为什么在 java.util.concurrent 没有一个类能够代替 Vector 呢？

  • 他人的了解

ConcurrentHashMap 的呈现更多的在于保障并发，从它采纳了锁分段技术和弱一致性的 Map 迭代器去防止并发瓶颈可知。(jdk7 及其以前)

而 ArrayList 中很多操作很难防止锁整表，就如 contains()、随机取 get()等，进行查问搜寻时都是要整张表操作的，那多线程时数据的实时一致性就只能通过锁来保障，这就限度了并发。

  • 集体的了解

这里说的并不确切。

如果没有数组的长度变动，那么能够通过下标进行分段，不同的范畴进行锁。然而这种有个问题，如果数组呈现删除，减少就会不行。

说到底，还是性能和平安的均衡。

  • 比拟中肯的答复

在 java.util.concurrent 包中没有退出并发的 ArrayList 实现的次要起因是：很难去开发一个通用并且没有并发瓶颈的线程平安的 List。

像 ConcurrentHashMap 这样的类的真正价值（The real point/value of classes）并不是它们保障了线程平安。而在于它们在保障线程平安的同时不存在并发瓶颈。

举个例子，ConcurrentHashMap 采纳了锁分段技术和弱一致性的 Map 迭代器去躲避并发瓶颈。

所以问题在于，像“Array List”这样的数据结构，你不晓得如何去躲避并发的瓶颈。拿 contains() 这样一个操作来说，当你进行搜寻的时候如何防止锁住整个 list？

另一方面，Queue 和 Deque (基于 Linked List)有并发的实现是因为他们的接口相比 List 的接口有更多的限度，这些限度使得实现并发成为可能。

CopyOnWriteArrayList 是一个乏味的例子，它躲避了只读操作（如 get/contains）并发的瓶颈，然而它为了做到这点，在批改操作中做了很多工作和批改可见性规定。

此外，批改操作还会锁住整个 List，因而这也是一个并发瓶颈。

所以从实践上来说，CopyOnWriteArrayList 并不算是一个通用的并发 List。

源码解读

类定义

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {private static final long serialVersionUID = 8673264195747942595L;}

实现了最根本的 List 接口。

属性

咱们看到前几次重复提及的 ReentrantLock 可重入锁。

array 比拟好了解，以前的 List 也是通过数组实现的。

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

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
/**
 * Gets the array.  Non-private so as to also be accessible
 * from CopyOnWriteArraySet class.
 */
final Object[] getArray() {return array;}
/**
 * Sets the array.
 */
final void setArray(Object[] a) {array = a;}

结构器

/**
 * Creates an empty list.
 */
public CopyOnWriteArrayList() {setArray(new Object[0]);
}

/**
 * Creates a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection of initially held elements
 * @throws NullPointerException if the specified collection is null
 */
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);
}

/**
 * Creates a list holding a copy of the given array.
 *
 * @param toCopyIn the array (a copy of this array is used as the
 *        internal array)
 * @throws NullPointerException if the specified array is null
 */
public CopyOnWriteArrayList(E[] toCopyIn) {setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

这几种结构器都是对立调用的 setArray 办法：

/**
 * Sets the array.
 */
final void setArray(Object[] a) {array = a;}

这个办法非常简单，就是初始化对应的数组信息。

外围办法

我大略看了下，很多办法和以前大同小异，咱们来重点关注下几个批改元素值的办法：

set

办法通过 ReentrantLock 可重入锁管制加锁和解锁。

这里最奇妙的中央在于，首先会判断指定 index 的值是否和预期值雷同。

按理说雷同，是能够不进行更新的，这样性能更好；不过 jdk 中还是会进行一次设置。

如果值不同，则会对原来的 array 进行拷贝，而后更新，最初从新设置。

这样做的益处就是写是不阻塞读的，毛病就是比拟节约内存，拷贝数组也是要花工夫的。

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

ps: 这里的所有变更操作是互斥的。

add

/**
 * 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;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {lock.unlock();
    }
}

也是通过 ReentrantLock 进行加锁。

这里比起更新更加简略间接，因为是增加元素，所以新数组的长度间接 +1。

jdk 中数组的这种复制都是应用的 Arrays.copy 办法，这个以前实测，性能还是不错的。

add(int, E)

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {Object[] elements = getArray();
        int len = elements.length;

        // 越界校验
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index:"+index+
                                                ", Size:"+len);
        Object[] newElements;
        int numMoved = len - index;

        // 如果是放在数组的最初，其实就等价于下面的 add 办法了。if (numMoved == 0)
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // 如果元素不是在最初，就从两边开始复制即可：//0...index-1
            //index+1..len

            newElements = new Object[len + 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        
        // 对立设置 index 地位的元素信息
        newElements[index] = element;
        setArray(newElements);
    } finally {lock.unlock();
    }
}

remove 删除元素

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).  Returns the element that was removed from the list.
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
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;

        // 如果删除最初一个元素，间接从 0..len-1 进行拷贝即可。if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 新的数组比原来长度 -1
            Object[] newElements = new Object[len - 1];

            //0...index-1 拷贝
            //indx+1...len-1 拷贝
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {lock.unlock();
    }
}

删除元素实际上和增加元素的流程是相似的。

不过很奇怪，没有做越界判断？

迭代器

阐明

COWList 的迭代器和惯例的 ArrayList 迭代器还是有差别的，咱们以前可能会被问过，一边遍历一边删除如何实现？

答案可能就是 Iterator。

然而 COW 的 Iterator 恰好是不能反对变更的，集体了解是为了保障并发只在下面提及的几个变更中管制。

实现

迭代器定义

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 < snapshot.length;}
public boolean hasPrevious() {return cursor > 0;}
@SuppressWarnings("unchecked")
public E next() {if (! hasNext())
        throw new NoSuchElementException();
    return (E) snapshot[cursor++];
}
@SuppressWarnings("unchecked")
public E previous() {if (! hasPrevious())
        throw new NoSuchElementException();
    return (E) snapshot[--cursor];
}
public int nextIndex() {return cursor;}
public int previousIndex() {return cursor-1;}

不反对的操作

public void remove() {throw new UnsupportedOperationException();
}
public void set(E e) {throw new UnsupportedOperationException();
}
public void add(E e) {throw new UnsupportedOperationException();
}

@Override
public void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);
    Object[] elements = snapshot;
    final int size = elements.length;
    for (int i = cursor; i < size; i++) {@SuppressWarnings("unchecked") E e = (E) elements[i];
        action.accept(e);
    }
    cursor = size;
}

小结

COW 这种思维是十分有优良的，在写少读多的场景，能够通过空间换取工夫。

心愿本文对你有帮忙，如果有其余想法的话，也能够评论区和大家分享哦。

各位 极客 的点赞珍藏转发，是老马继续写作的最大能源！

正文完
面试
发表至： 面试
2020-10-31
 0
关于面试:天道酬勤进字节了
关于面试:mysql-面试总结
关于面试:算法题两数之和JavaScript及Java实现
关于面试:每日算法刷穿-LeetCode9-回文数简单