《CopyOnWriteArrayList源码分析》

CopyOnWriteArrayList

CopyOnWriteArrayList是线程安全的ArrayList，可直接在多线程环境下使用，无需加锁。它通过ReentrantLock锁+数组copy+volatile关键字保证了线程安全。

1 .CopyOnWriteArrayList类的底层代码是由ReentrantLock加锁实现线程安全，并且它的底层数组通过volatile关键字修饰，数组一旦被修改，其他线程会立马感知到。

// 使用ReentrantLock 可重入锁加锁
final transient ReentrantLock lock = new ReentrantLock();
// volatile 关键字保证数组可见性
private transient volatile Object[] array; // 内部用来存放数据的数组

2. 读取操作

读取操作就是获取array数组，此操作不会对元素的值做出改变，因此不需要加锁，允许多个线程同时读取。
CopyOnWriteArrayList 支持并发读，只有当写的时候才会加锁，所以在读多写少的场景下性能更好。

 final Object[] getArray() {		
        return array;	// 返回array数组
    }

    final void setArray(Object[] a) {
        array = a;	// 当前数组指向参数数组
    }
1
2
3
4
5
6
7

首先CopyOnWriteArrayList会在无参构造方法中初始化一个长度为0的数组

// 无参构造方法
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);		// 创建了一个个数为0的新数组
    }

	// 有参构造方法
    public CopyOnWriteArrayList(Collection c) {      // 传入一个集合	
        Object[] elements;

		// 判断当前集合对象是否属于CopyOnWriteArrayList类
        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); // 返回新数组
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

写入操作

CopyOnWriteArrayList的添加，修改，替换都属于写入操作，在这些过程中都需要通过加锁来实现线程安全，保证了在这次写入操作时只有一个线程来获取当前锁对其进行改变。

1. 替换

替换元素就是将原数组作为备份，创建长度不变的新数组，然后(在指定位置)替换元素，并且新数组替换原数组(此过程需要加锁)。

// 替换指定下标的数据
    public E set(int index, E element) {
        final ReentrantLock lock = this.lock; // 获取当前线程的锁
        lock.lock(); // 加锁
        try {
            Object[] elements = getArray(); // 获取array数组并赋给elements

			// 获取原来指定下标位置的值
            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(); // 释放锁
        }
    }
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

2. 添加

添加操作同样就是创建原数组容器的备份作为新数组容器，并且长度加一，然后(在指定位置)添加数据，添加完成后将新数组替换成旧数组(此过程需要加锁)。

// 添加
    public boolean add(E e) {
        final ReentrantLock lock = this.lock; // 使用ReentrantLock可重入锁同步线程
        lock.lock(); // 加锁
        try {
            Object[] elements = getArray(); // 得到原数组
            int len = elements.length;

			// 将原数组复制到新数组，新数组长度+1
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            
			// 在新数组末尾添加新元素
			newElements[len] = e;

			// 替换掉原来的数组
            setArray(newElements);
            return true;
        } finally {
			// finally块中释放锁
            lock.unlock();
        }
    }

	// 在指定位置添加元素
    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;
			
			// 如果插入的位置等于数组末尾位置,直接复制数组并且长度+1
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {
				// 如果插入的位置在数组中间，将原数组分两部分复制到新数组
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
			// 给指定位置添加指定元素
            newElements[index] = element;
			// 返回新数组
            setArray(newElements);
        } 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

// 指定位置添加集合
    public boolean addAll(int index, Collection c) {
		// 将传入的集合转化为数组
        Object[] cs = c.toArray();
        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);
			// 如果传入的数组长度为0
            if (cs.length == 0)
                return false;
            int numMoved = len - index; 
            Object[] newElements;

			// 如果在原数组末尾添加
            if (numMoved == 0)
				// 复制原数组到新数组并且长度+len
                newElements = Arrays.copyOf(elements, len + cs.length);
            else {
				// 如果在原数组中间添加元素
				// 将数组分成三部分复制：
                newElements = new Object[len + cs.length];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index,
                                 newElements, index + cs.length,
                                 numMoved);
            }
            System.arraycopy(cs, 0, newElements, index, cs.length);

			// 返回新数组
            setArray(newElements);
            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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

3. 删除

删除操作首先也是创建一个新数组，但是其长度等于原数组长度-1，然后把原数组中除了要删除的元素都拷贝到新数组中，并且返回到新数组(此过程需要加锁)。

// 删除
    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 {
				// 如果要删除的数据在数组中间
				// 创建一个新数组，长度等于原数组长度+1
				// 按指定下标位置划分成两部分拷贝
                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();
        }
    }

	// 批量删除
    void removeRange(int fromIndex, int toIndex) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
			// 得到原数组 
            Object[] elements = getArray();
            int len = elements.length;

			// 判断传入的起始位置和结束位置是否符合常理
            if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
                throw new IndexOutOfBoundsException();
            int newlen = len - (toIndex - fromIndex); // 新数组的长度
            int numMoved = len - toIndex; // 要删除的数组长度
            
			// 如果删除个数为0
			if (numMoved == 0)
				// 直接将原数组复制并返回
                setArray(Arrays.copyOf(elements, newlen));
            else {
				// 删除个数>0
				// 创建新数组 
                Object[] newElements = new Object[newlen];
				
				// 将起始位置之前，结束位置之后的数组内容分别复制到新数组 
                System.arraycopy(elements, 0, newElements, 0, fromIndex);
                System.arraycopy(elements, toIndex, newElements,
                                 fromIndex, numMoved);

				// 将新数组返回
                setArray(newElements);
            }
        } 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

4.清除

清除操作就是将原来的数组的初始化为一个空数组，此过程也需要加锁。

 // 清除
    public void clear() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
			// 将数组长度初始化为0
            setArray(new Object[0]);
        } finally {
            lock.unlock();
        }
    }
1
2
3
4
5
6
7
8
9
10
11

总结

CopyOnWriteArrayList是线程安全的ArrayList,它的读操作作用在旧容器，写操作作用在新容器下(拷贝数组)，不会影响到原来的数组。
CopyOnWriteArrayList在对数组操作时会：
加锁；
将原数组拷贝到新数组；
在新数组上进行操作，并返回(不会影响到原数组 安全！)；
解锁。

从写入操作(添加，修改，删除等)可以看出：它的线程安全是通过加锁+拷贝数组+volatile保证的。

ReentrantLock加锁：保证同一时刻数组只能被一个线程操作
数组拷贝：保证数组内存地址修改后会触发volatile的可见性，其他线程会立马知道该数组被修改
volitile：值被修改后，其他线程能够立马知道。

它具有读写分离的思想：读操作不加锁，写操作加锁，它支持并发读，所以CopyOnWriteArrayList在读多写少的环境下效率较高，只不过每次写入操作都会复制数组，比较消耗内存。