Java-CopyOnWriteArrayList的实现原理

一些基本概念

所在包路径: java.util.concurrent
作用: CopyOnWriteArrayList可以理解为是线程安全版本的ArrayList,功能和ArrayList类似
数据结构: 底层同ArrayList一样,是一个Object类型的数组,用来存放元素
实现原理: 使用了写锁, 采用数组复制的形式完成数据的修改(增/删/改)操作
特点: 线程安全, 查询效率高, 数据保证最终一致性

如何添加数据? add()方法

首先, CopyOnWriteArrayList里申明了两个属性

1. Lock 锁, 用来在写操作的时候进行加锁,保证多线程下的数据安全
2. Objeck数组, 用来存放实际写进去的数据, 使用了volatile关键词修饰,保证多线程数据可见

/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

添加过程如下:

1. 在方法最外层加锁
2. 获取到原始Object数组
3. 创建一个新的数组,大小为原始数组的大小+1
4. 将新元素保存在新数组上
5. 将新数组替换掉老数组
6. 解锁

是不是很简单, 来一起看下源码吧:

public boolean add(E e) {
// 1.在方法最外层加锁 这里的lock就是上文说到的在类属性里申明的ReentrantLock锁
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 2.获取到原始Object数组, 就很简单地直接将我们在上文申明的Object数组返回就好啦
// final Object[] getArray() {
//
return array;
// }
Object[] elements = getArray();
// 3.创建一个新的数组,大小为原始数组的大小+1, 
//
因为要新添加一个元素嘛,所以数组大小+1,这样就不用专门对数组进行扩容操作了
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 4.将新元素保存在新数组上, 这一步正式完成数据插入操作
newElements[len] = e;
// 5.将新数组替换掉老数组, 这一步也超简单地将新数据进行一个赋值操场就行啦,这样老数组就被覆盖了
// final void setArray(Object[] a) {
//
array = a;
// }
setArray(newElements);
return true;
} finally {
// 6.最后,记得解锁呦,这里放在finally里是为了保证即使代码抛异常也可以正常解锁
lock.unlock();
}
}

如何读取数据? get(int index)方法

获取数据的方法更加简单粗暴啦,直接根据下标index,获取到数组里对应的数据即可,是不是敲简单~~~

public E get(int index) {
// final Object[] getArray() {
//
return array;
// }
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}

CopyOnWriteArrayList使用了写锁的概念,也就是只在写的时候加锁,读的时候不加锁,那这样聪明如你是否一下就发现了问题:
新的数组添加完数据,但是还没有替换老数组的时候,其他线程是无法读取到最新添加的数据的!!!
因为复制数组的这种添加机制, CopyOnWriteArrayList也就只能退而求次地保证数据的最终一致性啦
但是因为读数据是不需要任何加锁操作的,所以保证了很好的查询效率

如何删除数据? remove()方法

删除数据和添加数据的思路完全一样:

1. 加锁
2. 获取到原始数组
3. 定位到需要删除的index索引下标
4. 将除了这个位置的其他数据写入新数组并新数组替换掉老数组
5. 解锁

public E remove(int index) {
// 1.加锁,保证多线程下的数据安全
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 2.获取到原始数组
Object[] elements = getArray();
int len = elements.length;
// 3.定位到需要删除的index索引下标
E oldValue = get(elements, index);
int numMoved = len - index - 1;
// 4.将除了这个位置的其他数据写入新数组, 这里分为了两种情况
if (numMoved == 0)
// 情况1: 删除的元素是数组的第一个下标
setArray(Arrays.copyOf(elements, len - 1));
else {
// 情况2: 删除的元素在其他位置上
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 {
// 6.同样,在finally完成最后的解锁操作
lock.unlock();
}
}

如何获取数组大小? size()方法

简单! 粗暴!

public int size() {
return getArray().length;
}

迭代器需要特殊处理嘛? 需要

CopyOnWriteArrayList在内部自己实现ListIterator接口定义了自己的迭代器 COWIterator
主要申明了两个属性:

1. 需要循环遍历的数组
2. 开始的位置

/** Snapshot of the array */
private final Object[] snapshot;
/** Index of element to be returned by subsequent call to next.
*/
private int cursor;

这里的数组使用了 snapshot 作为变量名,突出了 快照 的特性 —— 调用iterator()方法时,生成一个新的迭代器实例, 将生成时的那个时刻的array数组赋值给迭代器内部的snapshot数组, 这个迭代器里的所有对数组的操作都是使用的snapshot数组,而不是外部的array数组
这样,在迭代器遍历的过程中, 外部array数组无论发生怎样的变化都不会影响此次迭代的顺利完成,同样, 在迭代过程中新添加的数据本次迭代也就无法读取到了
在同一个迭代过程中:

1. 无法读取到这个迭代过程中新增加的数据
2. 可以读到这个迭代过程中已删除的数据

也就是说 CopyOnWriteArrayList 在这里也是只保证了 数据保证最终一致性

好啦, CopyOnWriteArrayList原理到此分享结束,欢迎关注~~~

最后

以上就是忧郁未来为你收集整理的Java-CopyOnWriteArrayList的实现原理的全部内容，希望文章能够帮你解决Java-CopyOnWriteArrayList的实现原理所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。