【从入门到放弃-Java】并发编程-JUC-CopyOnWriteArrayList

前言

上文【从入门到放弃-Java】并发编程-JUC-ConcurrentHashMap中,我们学习了常用的并发容器CurrentHashMap,本文我们来了解下List的并发容器:CopyOnWriteArrayList
直接来看源码。

CopyOnWriteArrayList

add

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
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//使用synchronized加锁
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
//拷贝一份array,数组大小加一
es = Arrays.copyOf(es, len + 1);
//设置最后一位为需要添加的值e
es[len] = e;
//将新的array设置为当前List的中的值,array是volatile类型的,因此写入后其它线程能立即看到
setArray(es);
return true;
}
}

/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
//使用synchronized加锁
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException(outOfBounds(index, len));
Object[] newElements;
int numMoved = len - index;

if (numMoved == 0)
//如果是在尾部插入,则将List中的数组直接copy并将长度加一
newElements = Arrays.copyOf(es, len + 1);
else {
//如果不是在尾部插入,则以index处将原array分割成两部分copy到新数组中,空出index的位置
newElements = new Object[len + 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index, newElements, index + 1,
numMoved);
}
//在index出设置element的值
newElements[index] = element;
setArray(newElements);
}
}

addAll

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
72
73
74
75
76
77
78
79
80
81
82
/**
* Appends all of the elements in the specified collection to the end
* of this list, in the order that they are returned by the specified
* collection's iterator.
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
* @see #add(Object)
*/
public boolean addAll(Collection<? extends E> c) {
//获取数组
Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
if (cs.length == 0)
return false;
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
Object[] newElements;

if (len == 0 && cs.getClass() == Object[].class)
//如果当前List长度为0,则直接设置array为新数组
newElements = cs;
else {
//将原数组copy为新的数组,新的数组长度为len+cs.lenth
newElements = Arrays.copyOf(es, len + cs.length);
//从len处开始,设置为需要添加的数组
System.arraycopy(cs, 0, newElements, len, cs.length);
}
//将值写入List的成员变量array,array是volatile类型的,因此写入后其它线程能立即看到
setArray(newElements);
return true;
}
}

/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in this list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
* @see #add(int,Object)
*/
public boolean addAll(int index, Collection<? extends E> c) {
//获取数组
Object[] cs = c.toArray();
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException(outOfBounds(index, len));
if (cs.length == 0)
//如果当前List长度为0,直接返回false插入失败
return false;
int numMoved = len - index;
Object[] newElements;
if (numMoved == 0)
//如果List尾部插入,则直接在尾部copy要插入的数组
newElements = Arrays.copyOf(es, len + cs.length);
else {
//如果不是在尾部插入,则以index处将原array分割成两部分copy到新数组中,空出index到index+cs.length长度的位置
newElements = new Object[len + cs.length];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index,
newElements, index + cs.length,
numMoved);
}
//将index到index+cs.length填充需要插入的数组
System.arraycopy(cs, 0, newElements, index, cs.length);
setArray(newElements);
return true;
}
}

get

1
2
3
4
5
6
7
//get方式就比较简单了 因为array是volatile类型的,不需要任何同步操作就可取到值,保证了并发
public E get(int index) {
return elementAt(getArray(), index);
}
static <E> E elementAt(Object[] a, int index) {
return (E) a[index];
}

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
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/**
* 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) {
//同步锁
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
E oldValue = elementAt(es, index);
int numMoved = len - index - 1;
Object[] newElements;
if (numMoved == 0)
//如果是移除最后一个元素,则直接copy 0到len-2位置的元素即可
newElements = Arrays.copyOf(es, len - 1);
else {
//如果不是最后一个元素,则copy需要删除数组[0,index)和[index,length]的元素到新数组。
newElements = new Object[len - 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index + 1, newElements, index,
numMoved);
}
setArray(newElements);
return oldValue;
}
}

/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that {@code Objects.equals(o, get(i))}
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
Object[] snapshot = getArray();
//找到需要删除元素的索引
int index = indexOfRange(o, snapshot, 0, snapshot.length);
return index >= 0 && remove(o, snapshot, index);
}

/**
* A version of remove(Object) using the strong hint that given
* recent snapshot contains o at the given index.
*/
private boolean remove(Object o, Object[] snapshot, int index) {
synchronized (lock) {
Object[] current = getArray();
int len = current.length;
//加锁后验证数组是否在找到要删除的索引后改动过,如果改动的话,删除改动后的第一个o元素
if (snapshot != current) findIndex: {
int prefix = Math.min(index, len);
for (int i = 0; i < prefix; i++) {
if (current[i] != snapshot[i]
&& Objects.equals(o, current[i])) {
index = i;
break findIndex;
}
}
if (index >= len)
return false;
if (current[index] == o)
break findIndex;
index = indexOfRange(o, current, index, len);
if (index < 0)
return false;
}
//删除index位置的元素
Object[] newElements = new Object[len - 1];
System.arraycopy(current, 0, newElements, 0, index);
System.arraycopy(current, index + 1,
newElements, index,
len - index - 1);
setArray(newElements);
return true;
}
}

iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator provides a snapshot of the state of the list
* when the iterator was constructed. No synchronization is needed while
* traversing the iterator. The iterator does <em>NOT</em> support the
* {@code remove} method.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
//和ArrayList不同,CopyOnWriteArrayList在iterator遍历时,是对当前的array做了一个快照,在遍历期间,array可能会被别的线程更改,但快照不会改变,不受影响,因此在迭代中,数组元素不能改。
return new COWIterator<E>(getArray(), 0);
}

总结

通过源码分析我们了解到,CopyOnWriteArrayList写操作时,都是以加synchronized锁并copy一份数组进行修改的方式进行的,如果List比较大时,会非常占用资源。

读操作时不用加锁,因为array是volatile的,不需要额外同步,因此读性能非常高。

因此CopyOnWriteArrayList更适用于读多写少的并发操作中。

在遍历时,将当前的array做一个快照,不受其他线程更改的影响。因此,在iterator中,list中的元素是不能更改的(因为更改的是快照,不会写到原数组中,更改一定是无效的)。

但在for循环时,CopyOnWriteArrayList中的元素可以被更改,而ArrayList不行,因为ArrayList的元素被遍历到时总会先检查是否被更改,更改会抛出ConcurrentModificationException