CopyOnWrite的应用场景是多线程场景下多读少写,读的时候不加锁,修改数据的时候是通过拷贝一份数据进行修改,修改完后通过锁的形式写回来更新数据的。
CopyOnWriteArrayList
CopyOnWriteArrayList的类继承图:
- 实现List提供列表的增删改查功能。
- 实现RandomAccess提供随机访问。
- 实现Cloneable可被克隆。
- 实现Serializable可被序列化。
锁
使用ReentrantLock用于修改的时候加锁。与ArrayList一样,内部也是通过一个Object[]
数组来存储数据的。注意array加了volatile,这样在修改的时候切换数组就可以立即生效。还加了transient,自己实现序列化方法。
/** The lock protecting all mutators */
/** 用于修改时加锁 */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
/** 真正存储元素的地方,只能通过getArray()/setArray()访问 */
private transient volatile Object[] array;
读
读取元素不需要加锁。
final Object[] getArray() {
return array;
}
public E get(int index) {
// 获取元素不需要加锁
// 直接返回index位置的元素
// 这里是没有做越界检查的, 因为数组本身会做越界检查
return get(getArray(), index);
}
private static int indexOf(Object o, Object[] elements,
int index, int fence) {
if (o == null) {
for (int i = index; i < fence; i++)
if (elements[i] == null)
return i;
} else {
for (int i = index; i < fence; i++)
if (o.equals(elements[i]))
return i;
}
return -1;
}
新增
写的时候加锁:
- 使用ReentrantLock重入锁加锁;
- 新建一个数组,大小为原数组长度+1;
- 拷贝原数组数据到新数组;
- 把新增数据放到数组最后一位
- 设置array为新增数组
- 解锁
空间复杂度O(n),性能比较低下。
public boolean addIfAbsent(E e) {
// 获取元素数组, 取名为快照
Object[] snapshot = getArray();
// 检查如果元素不存在,直接返回false
// 如果存在再调用addIfAbsent()方法添加元素
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
public boolean add(E e) {
// 加锁
final ReentrantLock lock = this.lock;
lock.lock();//加悲观锁
try {
// 获取旧数组
Object[] elements = getArray();
int len = elements.length;
// 将旧数组元素拷贝到新数组中
// 新数组大小是旧数组大小加1
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 将元素放在最后一位
//写的时候先拷贝一份
newElements[len] = e;
setArray(newElements);//新数组赋值
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;
// 检查是否越界, 可以等于len
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
Object[] newElements;
int numMoved = len - index;
if (numMoved == 0)
// 如果插入的位置是最后一位
// 那么拷贝一个n+1的数组, 其前n个元素与旧数组一致
newElements = Arrays.copyOf(elements, len + 1);
else {
// 如果插入的位置不是最后一位
// 那么新建一个n+1的数组
newElements = new Object[len + 1];
// 拷贝旧数组前index的元素到新数组中
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
// 将index及其之后的元素往后挪一位拷贝到新数组中
// 这样正好index位置是空出来的
}
// 将元素放置在index处
newElements[index] = element;
setArray(newElements);
} finally {
// 释放锁
lock.unlock();
}
}
删除
删除的时候也需要加锁:
- 加锁
- 如果移除的是最后一位,则直接拷贝原数组到一个len-1大小的新数组
- 如果不是最后一位,新数组保存了原来的数组,并且index后面的数组往前挪一位。
- 解锁
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];
// 将前index的元素拷贝到新数组中
System.arraycopy(elements, 0, newElements, 0, index);
// 将index后面(不包含)的元素往前挪一位
// 这样正好把index位置覆盖掉了, 相当于删除了
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
// 释放锁
lock.unlock();
}
}
缺点
COW有两个缺点:
- 内存占用:数据修改的时候内存同时存在着两份拷贝,如果数据比较多,可能会造成频繁的GC。
- 一致性:数据在修改的时候,读线程还是读到的是旧的数组,牺牲了实时一致性,实现的是最终一致性。
CopyOnWriteArraySet
CopyOnWriteArraySet内部使用CopyOnWriteArrayList存储元素,add的时候调用CopyOnWriteArrayList的addIfAbsent即可。
// 内部使用CopyOnWriteArrayList存储元素
private final CopyOnWriteArrayList<E> al;//封装的CopyOnWriteArrayList
public boolean add(E e) {
return al.addIfAbsent(e);
}