Java源码分析系列笔记-10.CopyOnWriteArrayList
目录[*]1. 是什么
[*]2. 如何使用
[*]3. 原理
[*]3.1. 构造方法
[*]3.2. add方法
[*]3.2.1. 先加锁
[*]3.2.2. 复制数组并在这份数组上操作
[*]3.2.3. 将复制的数组set回属性
[*]3.3. remove方法
[*]3.3.1. 找到要删除元素的位置
[*]3.3.2. 加锁并把除了被删除之外的其他元素复制到新数组中，set回属性中
[*]3.4. get(index)方法
[*]3.4.1. 没加锁，通过数组获取
[*]3.5. contains
[*]3.5.1. 不加锁遍历数据查询
[*]3.6. set
[*]3.6.1. 先加锁
[*]3.6.2. 从原数组中获取index位置的值
[*]3.6.3. 如果index位置不相等，那么复制新数组、修改并set回属性
[*]3.6.4. 即使相等也要set回去保证volatile语义
[*]4. 总结
[*]5. 参考
1. 是什么
这个list借鉴的是读写分离的思想（弱一致性）
[*]读的时候可以并发读，不加锁；
[*]写的时候需要加锁，复制一份原有数据进行修改，改完后写回list
2. 如何使用
public class CopyOnWriteArrayListTest
{
public static void main(String[] args)
{
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.remove("a");
System.out.println(list.contains("a"));//false
System.out.println(list.get(0));//b
list.set(0, "d");
System.out.println(list);//
System.out.println(Thread.currentThread().getName() + "读取list:" + list);//
new Thread(()->{
System.out.println(Thread.currentThread().getName() + "读取list:" + list);//
try
{
TimeUnit.SECONDS.sleep(2);
}
catch (InterruptedException e)
{
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + "再次读取list:" + list);//
}).start();
new Thread(()->{
System.out.println(Thread.currentThread().getName() + "读取list:" + list);//
try
{
TimeUnit.SECONDS.sleep(2);
}
catch (InterruptedException e)
{
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + "再次读取list:" + list);//
}).start();
try
{
TimeUnit.SECONDS.sleep(1);
}
catch (InterruptedException e)
{
e.printStackTrace();
}
list.remove(0);
System.out.println(Thread.currentThread().getName() + "读取修改后的list:" + list);//
}
}3. 原理
3.1. 构造方法
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
//用于写时加锁
final transient ReentrantLock lock = new ReentrantLock();
//底层通过object数组实现, 通过 getArray/setArray访问
//volatile修饰保证多线程能及时看到最新结果
private transient volatile Object[] array;
public CopyOnWriteArrayList() {
//初始化数组长度为0
setArray(new Object);
}
//get set都没做什么同步措施
final void setArray(Object[] a) {
array = a;
}
final Object[] getArray() {
return array;
}
}
[*]可以看到底层是通过object数组实现,
[*]通过 getArray/setArray访问，这两个方法都没做什么同步措施
[*]使用volatile修饰保证多线程能及时看到最新结果
[*]并且有一个ReentrantLock，保证写时加锁
3.2. add方法
public boolean add(E e) {
//多个线程同时调用add方法保证只有一个能进入
final ReentrantLock lock = this.lock;
lock.lock();
try {
//获取原数组
Object[] elements = getArray();
int len = elements.length;
//复制并扩容数组
Object[] newElements = Arrays.copyOf(elements, len + 1);
//赋值
newElements = e;
//写回数组
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
[*]4行：加锁。写的操作必须加锁
[*]7-12行：copy原数组，扩容并修改
[*]14行：写回原数组
下面具体说明：
3.2.1. 先加锁
//多个线程同时调用add方法保证只有一个能进入
final ReentrantLock lock = this.lock;
lock.lock();
//。。。。。
} finally {
lock.unlock();
}3.2.2. 复制数组并在这份数组上操作
//获取原数组
Object[] elements = getArray();
int len = elements.length;
//复制并扩容数组
Object[] newElements = Arrays.copyOf(elements, len + 1);
//赋值
newElements = e;3.2.3. 将复制的数组set回属性
//写回数组
//array = a;
//由于array是volatile修饰的，一旦改变之后其他线程会清空工作内存中的array，这样读取新值
setArray(newElements);3.3. remove方法
[*]remove
public boolean remove(Object o) {
//获取原数组
Object[] snapshot = getArray();
//从原数组的0-最后一个位置查找o是否存在并获取其下标
int index = indexOf(o, snapshot, 0, snapshot.length);
//存在则删除
return (index < 0) ? false : remove(o, snapshot, index);
}
[*]3-5行：找到数组中值o的位置index
[*]7行：加锁删除数组中的index位置
下面具体说明：
3.3.1. 找到要删除元素的位置
[*]indexOf
private static int indexOf(Object o, Object[] elements,
int index, int fence) {
//要找的值为null
if (o == null) {
for (int i = index; i < fence; i++)
if (elements == null)
return i;
//不为null
} else {
for (int i = index; i < fence; i++)
if (o.equals(elements))
return i;
}
return -1;
}这个方法没有加锁，只是把判断值是否为null分别进行处理
3.3.2. 加锁并把除了被删除之外的其他元素复制到新数组中，set回属性中
[*]remove
//再snapshot数组删除下标为index且值为o的元素
private boolean remove(Object o, Object[] snapshot, int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
//获取现在的数组（可能已经改变过了）
Object[] current = getArray();
int len = current.length;
//数组改变过了
if (snapshot != current) findIndex: {
//遍历原数组和改变后的数组0-index位置是否相同，相同则可以删除
//有一个位置不相同 且 改变后的数组这个位置xx的元素与要删除的元素相同，那么重新从0-xx比较
int prefix = Math.min(index, len);
for (int i = 0; i < prefix; i++) {
if (current != snapshot && eq(o, current)) {
index = i;
break findIndex;
}
}
//改变后的数组长度比index短了，那么不可能删除了，返回false
if (index >= len)
return false;
//改变后的数组index位置仍然是o
if (current == o)
//退出findIndex这段代码，即执行34行
break findIndex;
//在改变后的数组中index-len位置重新寻找值为o的元素
index = indexOf(o, current, index, len);
//没找到，删除不了返回false
if (index < 0)
return false;
}
//创建原数组长度-1的新数组
Object[] newElements = new Object;
//复制index左边的元素到新数组
System.arraycopy(current, 0, newElements, 0, index);
//复制index右边的元素到新数组（等于删除了index位置的元素）
System.arraycopy(current, index + 1,
newElements, index,
len - index - 1);
//修改为新数组
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}3.4. get(index)方法
public E get(int index) {
return get(getArray(), index);
}get方法属于读取操作，所以不需要加锁，直接原数组上通过下标获取
3.4.1. 没加锁，通过数组获取
[*]get
private E get(Object[] a, int index) {
return (E) a;
}3.5. contains
public boolean contains(Object o) {
//获取原数组
Object[] elements = getArray();
//再查找下标
return indexOf(o, elements, 0, elements.length) >= 0;
}
[*]3行：contains方法属于读方法，所以没加锁
[*]5行：直接遍历数组查找
3.5.1. 不加锁遍历数据查询
[*]indexOf
private static int indexOf(Object o, Object[] elements,
int index, int fence) {
//要找的值为null
if (o == null) {
for (int i = index; i < fence; i++)
if (elements == null)
return i;
//要找的值不为null
} else {
for (int i = index; i < fence; i++)
if (o.equals(elements))
return i;
}
return -1;
}3.6. set
//修改index位置的值为element
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
//获取原数组
Object[] elements = getArray();
//获取原数组index位置的值
E oldValue = get(elements, index);
//index位置不是element
if (oldValue != element) {
//复制原数组到新数组，修改index位置的值，set回array
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements = element;
setArray(newElements);
//index位置已经是element了，那么直接set回array（保证volatile语义）
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}
[*]4行：set方法属于写方法，所以需要先加锁
[*]7-9行：通过下标查找值
[*]12-18行：第2步查找到的值跟现在数组中的值不同，说明有改变。那么copy原数组、修改、写回原数组
[*]19-22 行：第2步查找到的值跟现在数组中的值相同，说明没有改变。虽然不做什么处理也行，但为了保证volatile语义，还是set回数组
下面详细说明：
3.6.1. 先加锁
final ReentrantLock lock = this.lock;
lock.lock();
try {
} finally {
lock.unlock();
}3.6.2. 从原数组中获取index位置的值
//获取原数组
Object[] elements = getArray();
//获取原数组index位置的值
E oldValue = get(elements, index);3.6.3. 如果index位置不相等，那么复制新数组、修改并set回属性
//index位置不是element
if (oldValue != element) {
//复制原数组到新数组，修改index位置的值，set回array
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements = element;
setArray(newElements);
} 3.6.4. 即使相等也要set回去保证volatile语义
//index位置已经是element了，那么直接set回array（保证volatile语义）
else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}4. 总结
[*]适合读多写少的场景
[*]当调用add方法的时候加锁修改，内存中有两份数组，一份原始的，另一份是当前线程修改的数组
[*]当调用get方法时不加锁，获取的是原有的数组
5. 参考
[*]Java CopyOnWriteArrayList详解 - 简书
[*]聊聊并发-Java中的Copy-On-Write容器 | 并发编程网 – ifeve.com
[*]CopyOnWriteArrayList你都不知道，怎么拿offer？_weixin_34034261的博客-CSDN博客
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]