并发容器一览
图源: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
// 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)
}
好像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();
}
}
可以看到也是创建了一个新数组,直接复制原数组元素。然后将数组引用指向新数组。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章