月泉的博客

JUC-并发集合类List原理剖析

字数统计: 1.3k阅读时长: 5 min
2018/11/04 Share

java中能够直接支持并发的集合有2个类,分别为CopyOnWriteArrayListCopyOnWriteArraySet

CopyOnWriteArrayList

CopyOnWriteArrayList是什么

CopyOnWriteArrayListList的子类,它是线程安全的集合类,其主要思想是利用每次修改都采用复制的形式,但因为这种方式其对数据是弱一致性。

怎么使用?

1
2
3
4
5
6
7
public static void main(String[] args) {
List<String> names = new CopyOnWriteArrayList<>();
names.add("YueQuan");
System.out.println(names.get(0));
names.remove(0);
System.out.println(names.isEmpty());
}

因为其实现的是List接口,用过List的人都能很轻松的使用该类来做线程安全的集合元素操作

背后的原理

1
2
3
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}

可以上源码上观察到,在函数初始化的时候调用了setArray方法,并传入了一个Object数组且长度为0

1
2
3
final void setArray(Object[] a) {
array = a;
}
1
private transient volatile Object[] array;

可以看到setArray方法就是实例变量array这里用volatile语义修饰表示线程之间的可见性,还外加了transient关键字,这个关键字的含义是该值是瞬时态的不需要被持久化。

初始化小结

从创建一个CopyOnWriteArrayList的实例,从其构造函数可以看出在实例在实例化过程为其创建一个长度为0的Object数组。

add方法

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(); // 1
int len = elements.length; // 2
Object[] newElements = Arrays.copyOf(elements, len + 1); // 3
newElements[len] = e; // 4
setArray(newElements); // 5
return true;
} finally {
lock.unlock(); // 6
}
}

add的源码可以看出来,其使用了显示锁ReentrantLock来持有锁(未持有到锁的线程将会被阻塞)

  1. 获取当前array实例,
  2. 获取当前array的数组长度
  3. 创建一个比当前数组长度+1点数组且拷贝元素
  4. 给长度+1点数组位置处赋上要添加的元素
  5. 返回true
  6. 方法执行完执行unlock释放该锁

小结

非常简单,就是复制并创建一个比当前数组长度加1点数组然后将要添加的值赋上去

remove方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray(); // 1
int len = elements.length; // 2
E oldValue = get(elements, index); // 3
int numMoved = len - index - 1; // 4
if (numMoved == 0) // 5
setArray(Arrays.copyOf(elements, len - 1)); // 5.1
else { // 6
Object[] newElements = new Object[len - 1]; // 6.1
System.arraycopy(elements, 0, newElements, 0, index); // 6.2
System.arraycopy(elements, index + 1, newElements, index,
numMoved);// 6.3
setArray(newElements);// 6.4
}
return oldValue; // 7
} finally {
lock.unlock(); // 8
}
}

首先也是先获取锁,获取锁以后

  1. 首先还是获取当前数组
  2. 获取当前数组长度
  3. 拿到要删除的数组元素
  4. 长度 - 要删除的位置 - 1 (得知被删除元素后面还有多少个元素)
  5. 判断是不是删除的最后一个位置的元素
    1. 调用setArray复制当前数组,0到数组长度减1
  6. else
    1. 创建一个当前数组长度减1点数组
    2. 复制数组的前半段(除index位置)
    3. 复制数组的后半段(除index位置)
    4. 替换当前实例的数组实例
  7. 返回被删除的元素
  8. 解锁

System.arraycopy

1
2
3
public static native void arraycopy(Object src,  int  srcPos,
Object dest, int destPos,
int length);

该方法是Java中的一个native方法,说一下其具体的参数,src源数组,srcPos从源数组的起始位置,dest目标数组,destPos从目标数组的起始位置,length数量,这样分析下来就很容易理解了,就是从源数组的起始位置开始复制多少个元素到目标数组的起始位置开始。

1
System.arraycopy(elements, 0, newElements, 0, index); // 6.2

假如数组中有[1,2,3,4],我传入的index是2,那么此时调用该句出现的结果应该是,从elements数组的0下标开始复制2个元素到目标数组的起始位置开始

1
[1,2]

在来看后半段

1
2
System.arraycopy(elements, index + 1, newElements, index,
numMoved);// 6.3

首先我们举列除numMoved的值,其计算方式为:

1
length - index - 1  // 4 - 2 -1

得到到numMoved的值为1,其后面还有一个数组元素

然后道理就很简单了,从我要删除的位置处+1,复制后面数组元素剩余数量到目标数组的index处开始

get方法

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];
}

可以从源码处观察到,就是直接返回在数组下标的元素,但是传入的当前数组可能是一个相对新值,再传入后它位置处的元素可能已经变化了可能被插了也可能被删了,但你此时就已经是持有的一个旧值了返回旧值的该处元素(值的引用地址已经发生了变化,此时仍然指向堆中旧值的位置)

总结

从源码上看,可以发现CopyOnWriteArrayList是利用了数组复制和锁来实现的线程安全,但其在获取数据方面确实弱一致性,同时使用锁也会为其带来一定的性能开销。

原文作者:yuequan

原文链接:http://www.lunaspring.com/2018/11/04/juc_copy_on_write_array_list/

发表日期:November 4th 2018, 7:01:00 pm

更新日期:June 20th 2019, 4:08:06 pm

版权声明:© 月泉 - 邓亮泉 版权所有

CATALOG
  1. 1. CopyOnWriteArrayList
    1. 1.1. CopyOnWriteArrayList是什么
    2. 1.2. 怎么使用?
    3. 1.3. 背后的原理
      1. 1.3.1. 初始化小结
      2. 1.3.2. add方法
      3. 1.3.3. remove方法
      4. 1.3.4. get方法
    4. 1.4. 总结