并发包中并发 List 只有 CopyOnWriteArrayList 这一个, CopyOnWriteArrayList 是一个线程安全的 ArrayList, 对其进行修改操作和元素迭代操作都是在底层创建一个拷贝数组 (快照) 上进行的, 也就是写时拷贝策略.
我们首先看一下 CopyOnWriteArrayList 的类图有哪些属性和方法, 如下图所示:
如上, CopyOnWriteArrayList 的类图, 每个 CopyOnWriteArrayList 对象里面有一个 array 数组对象用来存放具体元素, ReentrantLock 独占锁对象用来保证同时只有一个线程对 array 进行修改, 这里只要记得 ReentrantLock 是独占锁, 同时只有一个线程可以获取就可以了.
那么问题来了, 如果让我们自己去做一个写时拷贝的线程安全的 List, 我们会怎么做, 要考虑哪些要点?
1.list 何时初始化, 初始化 list 元素个数为多少, list 是有限大小?
2. 如何保证线程安全, 比如多个线程进行读写时候, 如果保证是线程安全的?
3. 如何使用迭代器遍历 list 时候的数据一致性?
那么我们就进入 CopyOnWriteArrayList 源码去看, 看看设计者是如何处理的.
CopyOnWriteArrayList 源码分离如下:
1. 初始化, 首先看一下 CopyOnWriteArrayList 的无参构造函数, 如下代码内部创建了一个大小为 0 的 Object 数据作为 array 的初始值. 源码如下:
- public CopyOnWriteArrayList() {
- setArray(new Object[0]);
- }
接下来再看看 CopyOnWriteArrayList 的有参构造函数, 源码如下:
- // 创建一个 list, 其内部元素是入参 toCopyIn 的拷贝
- public CopyOnWriteArrayList(E[] toCopyIn) {
- setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
- }
- // 入参为集合, 拷贝集合里面元素到本 list
- 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);
- }
2. 添加元素, CopyOnWriteArrayList 中添加元素函数有 add(E e) , add(int index , E element) ,addIfAbsent(E e) , addAllAbsent(Collection<? extends E> c) 等操作, 原理一致,
接下来就以 add(E e)进行讲解. 源码如下:
- public boolean add(E e) {
- // 加独占锁(1)
- final ReentrantLock lock = this.lock;
- lock.lock();
- try {
- // 获取 array(2)
- Object[] elements = getArray();
- // 拷贝 array 到新数组, 添加元素到新数组(3)
- int len = elements.length;
- Object[] newElements = Arrays.copyOf(elements, len + 1);
- newElements[len] = e;
- // 使用新数组替换添加前的数组(4)
- setArray(newElements);
- return true;
- } finally {
- // 释放独占锁(5)
- lock.unlock();
- }
- }
如上代码, 调用 add 方法的线程会首先执行代码 (1) 去获取独占锁, 如果多个线程都调用 add 则只有一个线程会获取该锁, 其他线程会被阻塞挂起知道锁被释放. 所以一个线程获取到锁后, 就保证了在该线程添加元素过程中, 其他线程不会对 array 进行修改.
线程获取锁后执行代码 (2) 获取 array, 然后执行代码 (3) 拷贝 array 到一个新数组(从这里可以知道新数组的大小是原来数组大小加增加 1, 所以 CopyOnWriteArrayList 是无界 List), 并把要新增的元素添加到新数组.
然后执行到代码 (4) 把新数组替换原数组, 然后返回前要释放锁, 由于加了锁, 所以整个 add 过程是个原子操作, 需要注意的是添加元素时候首先是拷贝了一个快照, 然后在快照上进行的添加, 而不是直接在源来的数组上进行.
3. 获取指定位置元素, E get(int index)获取下标为 index 的元素, 如果元素不存在会抛出 IndexOutOfBoundsException 异常, 源码如下:
- 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];
- }
- }
如上代码, 获取指定位置的元素分为两步, 首先获取到当前 list 里面的 array 数组, 这里称为步骤 1, 然后通过随机访问的下标方式访问指定位置的元素, 这里称为步骤 2.
从代码中可以看到整个过程并没有加锁, 这就可能会导致当执行完步骤 1 后执行步骤 2 前, 另外一个线程 C 进行了修改操作, 比如 remove 操作, 就会进行写时拷贝删除当前 get 方法要访问的元素, 并且修改当前 list 的 array 为新数组.
而这之后步骤 2 可能才开始执行, 步骤 2 操作的是线程 C 删除元素前的一个快照数组(因为步骤 1 让 array 指向的是原来的数组), 所以虽然线程 C 已经删除了 index 处的元素, 但是步骤 2 还是返回 index 处的元素, 这其实就是写时拷贝策略带来弱一致性.
4. 修改指定元素, 修改 list 中指定元素的值, 如果指定位置的元素不存在则抛出 IndexOutOfBoundsException 异常, 源码码如下:
- 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();
- }
- }
如上代码, 首先获取了独占锁控制了其他线程对 array 数组的修改, 然后获取当前数组, 并调用 get 方法获取指定位置元素.
如果指定的位置元素与新值不一致则创建新数组并拷贝元素, 在新数组上修改指定位置元素值并设置新数组到 array.
如果指定位置元素与新值一样, 则为了保障 volatile 语义, 还是需要重新设置下 array, 虽然 array 内容并没有改变(为了保证 volatile 语义是考虑到 set 方法本身应该提供 volatile 的语义).
5. 删除元素, 删除 list 里面指定的元素, 主要的方法有如下方法:
- E remove(int index)
- boolean remove(Object o)
boolean remove(Object o, Object[] snapshot, int index) 等方法, 原理一致, 这里讲解下 remove(int index) 方法, 源码如下:
- 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();
- }
- }
正如上面代码所示, 其实和新增元素时候是类似的, 首先是获取独占锁保证删除数组期间, 其他线程不能对 array 进行修改, 然后获取数组中要给删除的元素, 并把剩余的原始拷贝到新数组后, 把新数组替换原来的数组, 最后在返回前释放锁.
6. 接下来要讲解一下弱一致性的迭代器.
遍历列表元素可以使用迭代器进行迭代操作, 讲解什么是迭代器的弱一致性前先上一个例子说明下迭代器的使用. 代码如下:
- import java.util.concurrent.CopyOnWriteArrayList;
- /**
- * Created by cong on 2018/6/9.
- */
- public class CopyOnWriteArrayListTest {
- public static void main( String[] args ) {
- CopyOnWriteArrayList<String> arrayList = new CopyOnWriteArrayList<>();
- arrayList.add("hello");
- arrayList.add("java");
- Iterator<String> itr = arrayList.iterator();
- while(itr.hasNext()){
- System.out.println(itr.next());
- }
- }
- }
运行结果如下:
其中迭代器的 hasNext 方法用来判断是否还有元素, next 方法则是具体返回元素. 那么接下来看 CopyOnWriteArrayList 中迭代器是弱一致性, 所谓弱一致性是指返回迭代器后, 其他线程对 list 的增删改对迭代器不可见, 无感知的, 那么下面就看看是如何做到的. 源码如下:
- public Iterator<E> iterator() {
- return new COWIterator<E>(getArray(), 0);
- }
- static final class COWIterator<E> implements ListIterator<E> {
- //array 的快照版本
- private final Object[] snapshot;
- // 数组下标
- private int cursor;
- // 构造函数
- private COWIterator(Object[] elements, int initialCursor) {
- cursor = initialCursor;
- snapshot = elements;
- }
- // 是否遍历结束
- public boolean hasNext() {
- return cursor <snapshot.length;
- }
- // 获取元素
- public E next() {
- if (! hasNext())
- throw new NoSuchElementException();
- return (E) snapshot[cursor++];
- }
- }
如上代码当调用 iterator()方法获取迭代器时候实际是返回一个 COWIterator 对象, COWIterator 的 snapshot 变量保存了当前 list 的内容, cursor 是遍历 list 数据的下标.
这里为什么说 snapshot 是 list 的快照呢? 明明是指针传递的引用, 而不是拷贝. 如果在该线程使用返回的迭代器遍历元素的过程中, 其他线程没有对 list 进行增删改, 那么 snapshot 本身就是 list 的 array, 因为它们是引用关系.
但是如果遍历期间, 有其他线程对该 list 进行了增删改, 那么 snapshot 就是快照了, 因为增删改后 list 里面的数组被新数组替换了, 这时候老数组只有被 snapshot 索引用, 所以这也就说明获取迭代器后, 使用改迭代器进行变量元素时候, 其它线程对该 list 进行的增删改是不可见的,
因为它们操作的是两个不同的数组, 这也就是弱一致性的达成.
下面通过一个例子来演示多线程下, 迭代器的弱一致性的效果: 代码如下:
- import java.util.Iterator;
- import java.util.concurrent.CopyOnWriteArrayList;
- /**
- * Created by cong on 2018/6/9.
- */
- public class CopyOnWriteArrayListTest {
- private static volatile CopyOnWriteArrayList<String> arrayList = new CopyOnWriteArrayList<>();
- public static void main( String[] args ) throws InterruptedException
- {
- arrayList.add("hello");
- arrayList.add("Java");
- arrayList.add("welcome");
- arrayList.add("to");
- arrayList.add("hangzhou");
- Thread threadOne = new Thread(new Runnable() {
- @Override
- public void run() {
- // 修改 list 中下标为 1 的元素为 JavaSe
- arrayList.set(1, "JavaSe");
- // 删除元素
- arrayList.remove(2);
- arrayList.remove(3);
- }
- });
- // 保证在修改线程启动前获取迭代器
- Iterator<String> itr = arrayList.iterator();
- // 启动线程
- threadOne.start();
- // 等在子线程执行完毕
- threadOne.join();
- // 迭代元素
- while(itr.hasNext()){
- System.out.println(itr.next());
- }
- }
- }
运行结果如下:
如上代码 main 函数首先初始化了 arrayList, 然后在启动线程前获取到了 arrayList 迭代器, 子线程 ThreadOne 启动后首先修改了 arrayList 第一个元素的值, 然后删除了 arrayList 中坐标为 2,3 的元素.
主线程等待子线程执行完毕后使用获取的迭代器遍历数组元素, 从打印的结果来看, 子线程里面进行的操纵是一个都没有生效, 这就是迭代器的弱一致性的效果, 需要注意的是获取迭代器必须在子线程操作之前进行.
注意: CopyOnWriteArrayList 使用写时拷贝的策略来保证 list 的一致性, 而获取 - 拷贝 - 写入 三步并不是原子性的, 所以在修改增删改的过程中都是用了独占锁, 并保证了同时只有一个线程才能对 list 数组进行修改.
另外 CopyOnWriteArrayList 提供了弱一致性的迭代器, 保证在获取迭代器后, 其他线程对 list 的修改该不可见, 迭代器遍历时候的数组是获取迭代器时候的一个快照, 另外并发包中 CopyOnWriteArraySet 底层就是使用它进行实现, 感兴趣的可以去翻翻看.
来源: https://www.cnblogs.com/huangjuncong/p/9160713.html