Java集合 | CopyOnWriteArrayList源码分析(JDK 1.7)

一、基本结构

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

二、基本属性

// 加锁的方法，在增加、移除操作的时候都需要加锁
transient final ReentrantLock lock = new ReentrantLock();

// 底层的数组
private volatile transient Object[] array;

三、构造方法

// 无参构造函数
public CopyOnWriteArrayList() {
    // 实例化一个 Object 类型的长度为 0 的数组，并赋值给 array
    setArray(new Object[0]);
}

// 有参构造函数，参数是集合类型
public CopyOnWriteArrayList(Collection<? extends E> c) {
    // 将集合转变成数组
    Object[] 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);
    // 将转变之后的数组赋给 array
    setArray(elements);
}

// 有参构造函数，参数是数组
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

通用方法

// 获取 array 底层数组
final Object[] getArray() {
    return array;
}

// 更新底层数组 array
final void setArray(Object[] a) {
    array = a;
}

四、增加

CopyOnWriteArrayList 中的 add 方法

// 增加方法
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 获取执行 add 方法的那个对象的对象锁
    lock.lock();
    try {
        // 获取底层数组，赋给 elements
        Object[] elements = getArray();
        int len = elements.length;
        // 将底层数组 array 复制到新的数组 newElements
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 在新数组 newElements 添加元素
        newElements[len] = e;
        // 将新数组 newElements 赋给底层数组 array
        setArray(newElements);
        return true;
    } finally {
        // 释放当前对象的锁
        lock.unlock();
    }
}

在 CopyOnWriteArrayList 中增加元素的时候，需要对当前对象加锁，即在一个线程添加元素的时候，其他线程是不能同时进行增加操作的

在添加元素的时候，不是直接在底层数组 array 上添加的，而是先复制了一个新的数组，然后在这个新的数组上添加元素，最后在把新的数组赋值给底层数组

增加一个元素的图示如下

Java集合 | CopyOnWriteArrayList源码分析(JDK 1.7)

五、删除

CopyOnWriteArrayList 中的 remove() 方法，分为两种，一种是根据位置进行删除，还有一种是根据传入的元素进行删除

根据通过传入的位置进行删除

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 获取执行 remove 方法的那个对象的对象锁
    lock.lock();
    try {
        // 获取底层数组 array
        Object[] elements = getArray();
        int len = elements.length;
        // 从 elements 数组中获取位置是 index 的值（即要被删除的元素）
        E oldValue = get(elements, index);
        // 获得从被删元素所在位置到数组的最后一位之间的元素个数
        int numMoved = len - index - 1;
        // 如果个数是 0，说明此时被删元素是数组的最后一位，直接复制最后一位之前的所有元素，将赋值的结果赋值给底层数组 array
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        // 如果被删元素不是数组的最后一位
        else {
            // 先实例化一个个数少 1 的新数组，用于存放删除指定元素之后的数组
            Object[] newElements = new Object[len - 1];
            // 首先将 elements 数组被删元素之前的所有元素复制到新数组(从新数组第0位开始接收)
            System.arraycopy(elements, 0, newElements, 0, index);
            // 然后将 elements 数组被删元素之后的所有元素复制到新数组(从新数组第index位开始接收)
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            // 将新数组 newElements 赋值给底层数组 array
            setArray(newElements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

根据传入的对象进行删除

public boolean remove(Object o) {
    final ReentrantLock lock = this.lock;
    // 获取对象
    lock.lock();
    try {
        // 将底层数组 array 赋给 elements
        Object[] elements = getArray();
        int len = elements.length;
        // 如果数组长度大于 0
        if (len != 0) {
            // Copy while searching for element to remove
            // This wins in the normal case of element being present
            int newlen = len - 1;
            // 实例化一个长度比 array 数组长度小 1 的新数组
            Object[] newElements = new Object[newlen];

            // 遍历新数组
            for (int i = 0; i < newlen; ++i) {
  				// 如果传入对象和底层数组中当前位置的值相同(底层通过equals)判断
                if (eq(o, elements[i])) {
                    // found one;  copy remaining and exit
                    // 从被删元素的后一位开始遍历
                    for (int k = i + 1; k < len; ++k)
       					// 将被删除元素之后的所有元素赋给新数组
                        newElements[k-1] = elements[k];
                    // 将新数组赋给底层数组 array
                    setArray(newElements);
                    return true;
                } else
                 	// 如果传入对象和底层数组中当前位置的值不同，则直接将底层数组当前位置的元素赋值给新数组
                    newElements[i] = elements[i];
            }

            // special handling for last cell
            // 如果底层数组只有1个元素
            if (eq(o, elements[newlen])) {
                // 直接将这一个元素赋值给底层数组 array
                setArray(newElements);
                return true;
            }
        }
        return false;
    } finally {
        lock.unlock();
    }
}

通用方法

// 获取数组中的某个位置的值
private E get(Object[] a, int index) {
    // 获取数组中 index 位置的值
    return (E) a[index];
}

private static boolean eq(Object o1, Object o2) {
    // CopyOnWriteArrayList 中并没有重写 equals 方法
    return (o1 == null ? o2 == null : o1.equals(o2));
}

删除方法共有2种，一种是根据位置进行删除，另一种是根据元素进行删除

对于根据位置进行删除的情况，步骤如下：

将底层数组复制给新数组 elements
根据删除元素的位置进行区分

2.1 如果删除原数组中的最后一个元素，直接将最后一个元素之前的所有元素复制到一个临时数组中，然后将这个临时的数组赋给底层数组 array

2.2 如果不是删除原数组中的最后一个元素，先创建一个长度比原来小 1 的新数组 newElements。首先将原数组被删元素之前的所有元素复制到新数组 newElements，在将原数组被删元素之后的所有元素复制到新数组 newElements。最后再把新数组 newElements 赋给底层数组 array

对于根据元素进行删除的情况，步骤如下：

将底层数组复制给新数组 elements
实例化一个数组长度比原来小 1 的新数组 newElements
遍历 newElements 数组

3.1 如果要删除的值和 elements 数组当前位置的值相同，则循环遍历将 elements 数组中除了被删元素之外的所有元素按原来的次序放入 newElements 中。放完之后，将放完的 newElements 赋给底层数组 array，然后直接退出

3.2 如果要删除的值和 elements 数组当前位置的值不同，则直接将 elements 数组中当前位置的元素赋给 newElements 中的当前位置
如果原数组长度是 1，且要删除的元素和这唯一的一个元素相同，则直接将空的数组赋给底层数组 array（将唯一一个元素删除自然就变成空数组了）

和 add 方法一样，执行 remove 方法之前也是需要获取对象锁的，也是先复制一份和底层数组 array 一样的数组，然后对这个新的数组进行删除操作，最后在将新的数组赋值给底层数组 array

六、其他方法

CopyOnWriteArrayList 的 get 方法

public E get(int index) {
    // 传入底层的数组 array 和数组中的位置
    return get(getArray(), index);
}

private E get(Object[] a, int index) {
    return (E) a[index];
}

读取的方法是不用加锁的

七、遍历

// 集合遍历的方法
public Iterator<E> iterator() {
    // 传入底层数组，和开始遍历的位置(从0开始)
    return new COWIterator<E>(getArray(), 0);
}

内部类 COWIterator

private static 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.  */
    // 当前遍历在 snapshot 数组中的位置
    private int cursor;
	
    // 实例化迭代器的时候调用该构造函数
    private COWIterator(Object[] elements, int initialCursor) {
        // 传入初始遍历的位置，赋值给 cursor
        cursor = initialCursor;
        // 将底层数组赋值给新数组 snapshot
        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();
        // 从新的 snapshot 数组中获取 cursor 位置的值
        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;
    }

    /**
      * Not supported. Always throws UnsupportedOperationException.
      * @throws UnsupportedOperationException always; <tt>remove</tt>
      *         is not supported by this iterator.
      */
    // 不支持直接在迭代器中使用 remove 方法
    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
      * Not supported. Always throws UnsupportedOperationException.
      * @throws UnsupportedOperationException always; <tt>set</tt>
      *         is not supported by this iterator.
      */
    public void set(E e) {
        throw new UnsupportedOperationException();
    }

    /**
      * Not supported. Always throws UnsupportedOperationException.
      * @throws UnsupportedOperationException always; <tt>add</tt>
      *         is not supported by this iterator.
      */
    public void add(E e) {
        throw new UnsupportedOperationException();
    }
}

可以看到，CopyOnWriteArrayList 下的 Iterator 方法，并不是对底层数组 array 进行直接遍历的，而是先将底层数组复制到新数组 snapshot，然后对这个新的数组遍历取值

此时如果在遍历的时候，执行 CopyOnWrieArrayList 的 add 或者 remove 方法，并不会影响遍历，在使用迭代器进行遍历的时候，都是对迭代器在的 snapshot 这个数组执行的，而执行集合的 add 或者 remove 方法，只是对底层的数组 array 进行操作，发生改变的也只是 array 这个数组，并没有影响到 Iterator 中的 snapshot 这个数组

正因为这个机制，会出现这么一种情况，一边使用 Iterator 遍历 CopyOnWriteArrayList，一边使用集合的 remove 方法删除遍历出来的元素，当遍历结束的时候，CopyOnWriteArrayList 中已经没有元素了，而迭代器中仍然存有遍历之前底层数组中的所有元素

因为 CopyOnWriteArrayList 的迭代器不是对底层数组进行操作，所有也不会出现 ArrayList 和 HashMap 这种在使用迭代器的过程中如果集合中增加或者删除元素而发生的 ConcurrentModificationException 异常

同时要注意的是，CopyOnWriteArrayList 迭代器下的 remove、set 和 add 方法都是不能使用的，都会抛出 UnsupportedOperationException 异常

八、关于读和写

设想这么一个场景，如果有两个线程，一个线程执行读，另一个线程执行写，这里需要分以下几种情况：

1.使用Iterator进行读

这种情况我们上面已经研究过了，如果一个线程在完成了 Iterator 的初始化之后，其他线程才开始对 CopyOnWriteArrayList 集合进行写，即使写操作已经完成了，但是执行读操作的那个线程读到的依然是旧的数组

2.使用get方式进行读

使用 get 方法需要分这么三种情况：

如果一个线程写操作（在复制的数组中放了新的元素）未完成，另一个线程读到的依然是旧的数组的元素
如果一个线程写操作完成，但是没有赋给底层数组，另一个线程读到的依然是旧的数组的元素
如果一个线程写操作完成，同时也赋给了底层数组，另一个线程读到的则是新数组的元素

需要强调的是，读操作是不加锁的

九、缺点

这里我直接引用别人写的，写的还是挺清楚的

https://blog.csdn.net/linsongbin1/article/details/54581787

十、参考

https://www.cnblogs.com/dolphin0520/p/3938914.html

https://blog.csdn.net/linsongbin1/article/details/54581787

https://mp.weixin.qq.com/s?__biz=MzIxNTQ3NDMzMw==&mid=2247483989&idx=1&sn=6610ee7d7938a620452284eec215d213&scene=19#wechat_redirect

Java集合 | CopyOnWriteArrayList源码分析(JDK 1.7)

一、基本结构

二、基本属性

三、构造方法

四、增加

五、删除

六、其他方法

七、遍历

八、关于读和写

1.使用Iterator进行读

2.使用get方式进行读

九、缺点

十、参考

继续阅读

Java集合在JDK1.7和JDK1.8中的不同——JDK1.7和JDK1.8中集合的对比研究——java集合深入理解1、ArrayList

java基础-Java集合框架-Map接口-HashMap原理（jdk1.7和jdk1.8）Java集合框架-Map接口-HashMap原理和源码

Java并发编程之原子性问题什么是原子性问题简单总结参考

Timer和TimerTask源码解读（面试题：双重定时器）Timer和TimerTask源码解读

HashSet集合解读

Python求两个list的差集、交集与并集的方法（转）一.两个list差集二. 获取两个list 的并集三. 获取两个 list 的差集

Java多线程之synchronized进阶篇

Python基础：元组&集合&字典

jQuery callbacks函数

18_张孝祥_多线程_阻塞队列的应用

15_张孝祥_多线程_Semaphere同步工具

Java1.8 对HashMap的resize()的理解

初探OpenStack Mitaka二．部署

# Linux常用命令 #

集合练习题1

基于jdk1.8的Vector源码分析