转载

JDK源码分析-CopyOnWriteArrayList

1. 概述

CopyOnWriteArrayList，从名字可以看出它跟 ArrayList 有点关系，可以理解为线程安全的 ArrayList。它的类签名和继承结构如下：

implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

它主要实现了 List 接口，也是一个集合类，下面分析其代码实现。

2. 代码分析

仍然先从构造器进行分析。

2.1 构造器

// 构造器一：无参构造器

setArray(new Object[0]);

}

// 构造器二：入参为集合类型

elements = ((CopyOnWriteArrayList<?>)c).getArray();

// c.toArray might (incorrectly) not return Object[] (see 6260652)

elements = Arrays.copyOf(elements, elements.length, Object[].class);

}

setArray(elements);

}

// 构造器三：入参为数组

setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));

}

它们都调用了 setArray 方法，如下：

// 存储元素的数组

final Object[] getArray() {

}

这个 Object 数组就是 CopyOnWriteArrayList 用于存储数据的，而这几个构造器主要就是对该数组进行初始化。

由于它是一个集合类，主要操作就是增删改查，下面对这些操作进行分析。

2.2 增加

添加单个元素的方法有以下三个：

add(E): 将指定元素添加到 List 末尾。

// 获取锁

final ReentrantLock lock = this.lock;

// 获取原数组

Object[] elements = getArray();

// 将原数据复制一个新的数组，容量增加 1

Object[] newElements = Arrays.copyOf(elements, len + 1);

newElements[len] = e; // 将新元素插入新数组的末尾

// 用新的数组替换旧的数组

setArray(newElements);

}

}

add(int, E): 将给定元素添加到指定位置。

public void add(int index, E element) {

// 获取原数组

Object[] elements = getArray();

Object[] newElements;

// 若将新元素添加到末尾，直接复制一个新的数组（容量增加 1）

newElements = Arrays.copyOf(elements, len + 1);

// 否则，创建一个新的空数组（容量增加 1）

// 然后先把 index 前面的数据复制到新数组，再把 index 后面的数据复制到新数组

newElements = new Object[len + 1];

System.arraycopy(elements, 0, newElements, 0, index);

System.arraycopy(elements, index, newElements, index + 1,

numMoved);

}

// 把新元素添加到新数组的末尾，然后替换原数组

newElements[index] = element;

setArray(newElements);

}

}

addIfAbsent(E): 当给定元素不存在时才添加。

// 获取原数组（当前的快照）

Object[] snapshot = getArray();

// indexOf >= 0 表示该元素已存在，直接返回 false

addIfAbsent(e, snapshot);

}

// 再次获取原数组

Object[] current = getArray();

// 二者不等，表示期间有其它线程进行修改

// Optimize for lost race to another addXXX operation

// 判断 e 是否存在于当前数组

// e 存在于 current，则返回 false（前面已判断 snapshot 中不存在）

}

Object[] newElements = Arrays.copyOf(current, len + 1);

newElements[len] = e;

setArray(newElements);

}

}

值得注意的是，addIfAbsent 方法执行期间，可能存在其它线程对数组进行修改，因此内部需要判断是否有修改。

这几个方法的共同点：

都使用互斥锁（ReentrantLock ）实现线程安全；
在新增元素时，并非直接修改原数组，而是复制出来一个新的数组，在新数组上修改，修改之后再覆盖原先的数组（这名字 Copy-On-Write 大概是这么来的吧）。

2.3 删除

remove(E): 删除指定位置的元素。

// 获取原数组

Object[] elements = getArray();

// 获取该索引处的旧值

E oldValue = get(elements, index);

// 删除的是末尾元素

// 复制 index 前面的所有元素，并替换原数组

setArray(Arrays.copyOf(elements, len - 1));

// 删除的不是末尾元素，新建一个空数组（容量减 1）

Object[] newElements = new Object[len - 1];

System.arraycopy(elements, index + 1, newElements, index,

numMoved);

// 替换旧数组

setArray(newElements);

}

}

remove(Object): 删除指定的元素。

// 获取原数组（快照）

Object[] snapshot = getArray();

// 获取给定元素的索引，若小于零表示不存在，返回 false

}

// 再次获取原数组（这里的操作逻辑和前面的 addIfAbsent 类似）

Object[] current = getArray();

index = i;

}

index = indexOf(o, current, index, len);

}

System.arraycopy(current, 0, newElements, 0, index);

System.arraycopy(current, index + 1,

newElements, index,

len - index - 1);

setArray(newElements);

}

}

这两个方法的共同点：

使用互斥锁（ReentrantLock ）实现线程安全；
在删除元素时，也不是直接修改原数组，而是复制出来一个新的数组，在新数组上修改，修改之后再覆盖原先的数组（与增加操作类似）。

2.4 修改

set(int, E): 将指定位置的元素设置为给定的元素。

// 获取原数组

Object[] elements = getArray();

// 获取该位置的旧值

Object[] newElements = Arrays.copyOf(elements, len);

newElements[index] = element;

setArray(newElements);

} else { // 新旧值相同

// Not quite a no-op; ensures volatile write semantics

setArray(elements);

}

}

该方法与前面的增加删除操作也是类似的。

2.5 读取

get(int): 获取给定位置的元素（不加锁）。

}

分析到这里，简单总结下增删改查操作：

增删改操作都使用了互斥锁，读操作不加锁；
增删改操作都会把当前数组复制一份副本出来，在副本上做修改，然后再覆盖原数组；
修改过程中仍可以读取，但读取到的可能是旧数组（脏读）。

这是一种读写分离的思想，可以提高并发性能（读多写少的场景下）。

2.6 迭代器

迭代器方法：

// 获取当前数组，作为快照传入 COWIterator

}

COWIterator 是一个内部嵌套类，主要代码如下：

static final class COWIterator<E> implements ListIterator<E> {

// 数组的快照

// 对 next 的后续调用将返回的元素的索引

cursor = initialCursor;

snapshot = elements;

}

}

}

}

}

}

}

// 该迭代器不支持修改操作

}

}

该迭代器会使用当前数组的一个快照进行迭代，在此期间若有其它线程对集合进行修改，迭代器是读不到的。而且不支持在迭代过程中对数组进行增加、删除、修改操作。

3. 小结

CopyOnWriteArrayList 是一个集合类，它的主要特点如下：

CopyOnWriteArrayList 可以理解为一个线程安全的 ArrayList；
在"增删改"操作中使用互斥锁保证线程安全，读操作不加锁；
采用写入时复制（Copy-On-Write）的思想，读写分离，可能造成脏读；
适用于读多写少的场景。

它也有一个明显的缺点：当集合中数据量较大时，如果做一些修改操作比较耗费内存（内存中会同时存在两份数据）。

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

JDK源码分析-CopyOnWriteArrayList

1. 概述

2. 代码分析

2.1 构造器

2.2 增加

2.3 删除

2.4 修改

2.5 读取

2.6 迭代器

3. 小结

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流