浅析JDK1.7 CopyOnWriteArrayList源码。

写在开篇

CopyOnWriteArrayList使用了一种写时复制的方法，当有新元素添加到CopyOnWriteArrayList时，先从原有的数组中拷贝一份出来，然后在新的数组做写操作，写完之后，再将原来的数组引用指向到新数组。

CopyOnWriteArrayList采用了读写分离的思想，读和写不同的容器。如果写操作未完成或者引用还未指向新数组，那么从原数组读取数据；如果写操作完成，并且引用已经指向了新的数组，那么从新数组中读取数据。所以CopyOnWriteArrayList只能保证数据的最终一致性，不能保证数据的实时一致性。

类的继承关系

CopyOnWriteArrayList跟ArrayList一样实现了List，RandomAccess， Cloneable，Serializable接口，但是没有继承AbstractList。

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

成员变量

1
2
3
4
5
/** 可重入锁 */
   transient final ReentrantLock lock = new ReentrantLock();

   /** 对象数组 */
   private volatile transient Object[] array;

构造方法

CopyOnWriteArrayList有三个构造方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
    * 创建一个空数组
    */
public CopyOnWriteArrayList() {
       setArray(new Object[0]);
   }

   /**
    * 以一个实现了Collection接口的集合类，来创建array
    */
   public CopyOnWriteArrayList(Collection<? extends E> c) {
       Object[] elements = c.toArray();
       
       if (elements.getClass() != Object[].class)
           elements = Arrays.copyOf(elements, elements.length, Object[].class);
       setArray(elements);
   }

   /**
    * 以一个CopyOnWriteArrayList的集合类，来创建array
    */
   public CopyOnWriteArrayList(E[] toCopyIn) {
       setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
   }

List接口的实现

add()

和ArrayList一样的，CopyOnWriteArrayList有两种插入元素的方法。先看第一种，默认在数组尾部插入元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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); // 将array复制到一个扩容了的新数组
           newElements[len] = e; // 插入新值
           setArray(newElements); // 将array引用指向新数组
           return true;
       } finally {
           lock.unlock(); // 释放锁
       }
   }

另一种是在指定下标插入元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
           if (numMoved == 0) // 在数组尾部插入元素
               newElements = Arrays.copyOf(elements, len + 1);
           else {
           	// 扩容
               newElements = new Object[len + 1];
               // 拷贝旧数组0到index处的到新数组0到index
               System.arraycopy(elements, 0, newElements, 0, index);
               // 拷贝旧数组index到最后的数组到新数组index+1到最后
               System.arraycopy(elements, index, newElements, index + 1,
                                numMoved);
           }
           newElements[index] = element; // 插入新元素
           setArray(newElements); // 将array引用指向新数组
       } finally {
           lock.unlock(); // 释放锁
       }
   }

get()

读的时候不加锁，代码很简单。

1
2
3
4
5
6
7
public E get(int index) {
       return get(getArray(), index);
   }

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

set()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 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); // 将array引用指向新数组
         } else {
             setArray(elements);
         }
         return oldValue;
     } finally {
         lock.unlock(); // 释放锁
     }
 }

remove()

同样地，CopyOnWriteArrayList有两个remove()，先来看一下根据下标删除元素的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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];
            // 拷贝旧数组0到index处的到新数组0到index
            System.arraycopy(elements, 0, newElements, 0, index);
            // 拷贝旧数组index+1到最后处的到新数组index到最后
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements); // 将array引用指向新数组
        }
        return oldValue;
    } finally {
        lock.unlock(); // 释放锁
    }
}

接着看一下删除第一个相同元素的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public boolean remove(Object o) {
       final ReentrantLock lock = this.lock;
       lock.lock(); // 获取锁
       try {
           Object[] elements = getArray();
           int len = elements.length;
           if (len != 0) {
               
               int newlen = len - 1;
               Object[] newElements = new Object[newlen];

			// 删除第一个出现的相同元素
               for (int i = 0; i < newlen; ++i) {
                   if (eq(o, elements[i])) {
                       // 将相同元素后面的元素复制到新数组末尾
                       for (int k = i + 1; k < len; ++k)
                           newElements[k-1] = elements[k];
                       setArray(newElements); // 将array引用指向新数组
                       return true;
                   } else
                       newElements[i] = elements[i];
               }

               if (eq(o, elements[newlen])) {
                   setArray(newElements);
                   return true;
               }
           }
           return false;
       } finally {
           lock.unlock(); // 释放锁
       }
   }