CopyOnWriteArrayList的继承体系
简介
CopyOnWriteArrayList是ArrayList的线程安全版本，内部也是通过数组实现，每次对数组的修改都完全拷贝一份新的数组来修改，修改完了再替换掉老数组，这样保证了只阻塞写操作，不阻塞读操作，实现读写分离。
属性
// 用于修改时加锁
final transient ReentrantLock lock = new ReentrantLock();
//真正存储元素的地方，只能通过getArray()/setArray()访问
private transient volatile Object[] array;
- lock:用于修改时加锁，使用transient修饰表示不自动序列化。
- array:真正存储元素的地方，使用transient修饰表示不自动序列化，使用volatile修饰表示一个线程对这个字段的修改另外一个线程立即可见。
构造方法
public CopyOnWriteArrayList() {
// 所有对array的操作都是通过setArray()和getArray()进行
setArray(new Object[0]);
}
final void setArray(Object[] a) {
array = a;
}
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
// 判断集合是否是CopyOnWriteArrayList
if (c.getClass() == CopyOnWriteArrayList.class)
// 直接调用getArray方法获取元素
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
// toArray方法获取数组
elements = c.toArray();
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 判断是否是Object.class 类型数组，进行拷贝
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
// 设置数组
setArray(elements);
}
// 设置数组
public CopyOnWriteArrayList(E[] toCopyIn) {
// 拷贝设置数组
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
add
public boolean add(E e) {
// 获取锁
final ReentrantLock lock = this.lock;
// 加锁
lock.lock();
try {
// 获取数组
Object[] elements = getArray();
// 获取数组长度
int len = elements.length;
// 拷贝出一个n+1长度的数组
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 设置插入的值
newElements[len] = e;
// 重新设置数组
setArray(newElements);
// 返回true
return true;
} finally {
// 解锁
lock.unlock();
}
}
// 指定位置添加元素
public void add(int index, E element) {
// 获取锁
final ReentrantLock lock = this.lock;
// 加锁
lock.lock();
try {
// 获取数组
Object[] elements = getArray();
// 获取数组长度
int len = elements.length;
// 判断插入位置是否越界
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
// 定义新数组
Object[] newElements;
// 定义要移动的位置
int numMoved = len - index;
// 判断是否是最后一位
if (numMoved == 0)
// 创建并拷贝一个n+1长度的原数组
newElements = Arrays.copyOf(elements, len + 1);
else {
// 创建一个新数组长度为n+1
newElements = new Object[len + 1];
// 拷贝旧数据，从0到index的元素到新数组中
System.arraycopy(elements, 0, newElements, 0, index);
// 拷贝index及以后的数据到新数组中
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
// 设置新数据
newElements[index] = element;
// 设置数组
setArray(newElements);
} finally {
// 释放锁
lock.unlock();
}
}
// 添加元素，数组中没有该元素就添加
public boolean addIfAbsent(E e) {
// 获取当前数组为快照数组
Object[] snapshot = getArray();
// 判断原数组中是否存在该元素，不存在进行添加
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
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[i] == null)
return i;
} else {
// 不为null，比较equals，返回索引
for (int i = index; i < fence; i++)
if (o.equals(elements[i]))
return i;
}
// 不存在返回-1
return -1;
}
private boolean addIfAbsent(E e, Object[] snapshot) {
// 获取锁
final ReentrantLock lock = this.lock;
// 加锁
lock.lock();
try {
// 获取当前数组
Object[] current = getArray();
// 获取当前数组长度
int len = current.length;
// 比较快照数组和当前数组是否相同
if (snapshot != current) {
// Optimize for lost race to another addXXX operation
// 获取快照数组和当前数组小的数
int common = Math.min(snapshot.length, len);
// 循环最小的数
for (int i = 0; i < common; i++)
// 当前数组和快照数组有差异，并且当前数组里面有该元素，返回false
if (current[i] != snapshot[i] && eq(e, current[i]))
return false;
// 判断当前元素是否在当前数组中
if (indexOf(e, current, common, len) >= 0)
return false;
}
// 创建并拷贝一个n+1长度的数组
Object[] newElements = Arrays.copyOf(current, len + 1);
// 设置当前元素
newElements[len] = e;
// 设置数组
setArray(newElements);
return true;
} finally {
// 解锁
lock.unlock();
}
}
get
// 指定索引位置获取元素
public E get(int index) {
return get(getArray(), index);
}
final Object[] getArray() {
return array;
}
// 返回当前元素
private E get(Object[] a, int index) {
return (E) a[index];
}
remove
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)
// 设置并拷贝一个n-1长度的数组
setArray(Arrays.copyOf(elements, len - 1));
else {
// 创建一个n-1长度的数组
Object[] newElements = new Object[len - 1];
// 拷贝从0到index数组
System.arraycopy(elements, 0, newElements, 0, index);
// 拷贝从index到末尾的数组
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
// 设置数组
setArray(newElements);
}
// 返回当前数组
return oldValue;
} finally {
// 解锁
lock.unlock();
}
}
size
public int size() {
return getArray().length;
}
总结
- CopyOnWriteArrayList使用ReentrantLock重入锁加锁，保证线程安全；
- CopyOnWriteArrayList的写操作都要先拷贝一份新数组，在新数组中做修改，修改完了再用新数组替换老数组，所以空间复杂度是O(n)，性能比较低下；
- CopyOnWriteArrayList的读操作支持随机访问，时间复杂度为O(1)；
- CopyOnWriteArrayList采用读写分离的思想，读操作不加锁，写操作加锁，且写操作占用较大内存空间，所以适用于读多写少的场合；
- CopyOnWriteArrayList只保证最终一致性，不保证实时一致性；