并发容器-CopyOnWriteArrayList

并发容器一览

　　图源：https://time.geekbang.org/column/article/90201?utm_term=pc_interstitial_938

CopyOnWriteArrayList

该容器支持多个线程同时读（读不加锁），但同一时刻只能一个线程写（写加锁）。

　　内部维护了一个数组

1 /** The array, accessed only via getArray/setArray. */
2 private transient volatile Object[] array;

1.获取元素

可以看到没有做任何处理，直接返回数组中的元素。读取元素时是不加锁的，也就是可以任意线程同时读取。

 1 /**
 2  * {@inheritDoc}
 3  *
 4  * @throws IndexOutOfBoundsException {@inheritDoc}
 5  */
 6 public E get(int index) {
 7     return get(getArray(), index);
 8 }
 9 /**
10  * Gets the array.  Non-private so as to also be accessible
11  * from CopyOnWriteArraySet class.
12  */
13 final Object[] getArray() {
14     return array;
15 }
16 @SuppressWarnings("unchecked")
17 private E get(Object[] a, int index) {
18     return (E) a[index];
19 }

2.更新元素

　　可以看到，是直接深拷贝了原数组，然后修改新数组的值，最后将对象的数组指向新数组。更新元素是加了可重入锁的，同一时刻只有一个线程能够修改数组的值，其他线程要修改只能等待获得锁。

 1 /**
 2  * Replaces the element at the specified position in this list with the
 3  * specified element.
 4  *
 5  * @throws IndexOutOfBoundsException {@inheritDoc}
 6  */
 7 public E set(int index, E element) {
 8     final ReentrantLock lock = this.lock;
 9     lock.lock();
10     try {
11         Object[] elements = getArray();
12         E oldValue = get(elements, index);
13         // 判断原有位置元素是否和插入元素相同，不相同才插入
14         if (oldValue != element) {
15             int len = elements.length;
16             Object[] newElements = Arrays.copyOf(elements, len);
17             newElements[index] = element;
18             setArray(newElements);
19         } else {
20             // Not quite a no-op; ensures volatile write semantics
21             // 不是无用操作，是为了保证volatile写的意义
22             setArray(elements);
23         }
24         return oldValue;
25     } finally {
26         lock.unlock();
27     }
28 }
29 /**
30  * Sets the array.
31  */
32 final void setArray(Object[] a) {
33     array = a;
34 }

22行代码处的setArray(elements)，这里操作看似没有意义。因为elements是volatile修饰的，这里是为了保证happens-before原则：

　　1.volatile变量读操作happens-before写操作；

　　2.同一线程的代码顺序执行，先前的操作 happens-before 之后的操作

　　3.传递性

实际上这是为了保证非volatile变量的可见性。

像下面这个例子，线程1的set操作可以保证nonVolatileField 变量的修改对线程2的读取可见。

// initial conditions
int nonVolatileField = 0;
CopyOnWriteArrayList<String> list = /* a single String */

// Thread 1
nonVolatileField = 1;                 // (1)
list.set(0, "x");                     // (2)

// Thread 2
String s = list.get(0);               // (3)
if (s == "x") {
    int localVar = nonVolatileField;  // (4)
}

　　具体可以参考这个帖子：https://stackoverflow.com/questions/28772539/why-setarray-method-call-required-in-copyonwritearraylist

　　好像JDK11移除了这行代码。。。

3.插入元素

 1 /**
 2  * Appends the specified element to the end of this list.
 3  * 末尾增加元素
 4  * @param e element to be appended to this list
 5  * @return {@code true} (as specified by {@link Collection#add})
 6  */
 7 public boolean add(E e) {
 8     final ReentrantLock lock = this.lock;
 9     lock.lock();
10     try {
11         Object[] elements = getArray();
12         int len = elements.length;
13         Object[] newElements = Arrays.copyOf(elements, len + 1);
14         newElements[len] = e;
15         setArray(newElements);
16         return true;
17     } finally {
18         lock.unlock();
19     }
20 }
21 /**
22  * Inserts the specified element at the specified position in this
23  * list. Shifts the element currently at that position (if any) and
24  * any subsequent elements to the right (adds one to their indices).
25  *
26  * @throws IndexOutOfBoundsException {@inheritDoc}
27  */
28 public void add(int index, E element) {
29     final ReentrantLock lock = this.lock;
30     lock.lock();
31     try {
32         Object[] elements = getArray();
33         int len = elements.length;
34         if (index > len || index < 0)
35             throw new IndexOutOfBoundsException("Index: "+index+
36                                                 ", Size: "+len);
37         Object[] newElements;
38         int numMoved = len - index;
39         if (numMoved == 0)
40             newElements = Arrays.copyOf(elements, len + 1);
41         else {
42             newElements = new Object[len + 1];
43             System.arraycopy(elements, 0, newElements, 0, index);
44             System.arraycopy(elements, index, newElements, index + 1,
45                              numMoved);
46         }
47         newElements[index] = element;
48         setArray(newElements);
49     } finally {
50         lock.unlock();
51     }
52 }

　　可以看到，增加元素和更新元素一样，也是创建一个新数组复制原有元素，然后插入新增元素。同时也是加了可重入锁，同一时刻只有一个线程能进行修改。

4.删除元素

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

　　可以看到也是创建了一个新数组，直接复制原数组元素。然后将数组引用指向新数组。

并发容器-CopyOnWriteArrayList

推荐阅读