JDK并发集合10:CopyOnWrite(并发容器)

CopyOnWrite的应用场景是多线程场景下多读少写,读的时候不加锁,修改数据的时候是通过拷贝一份数据进行修改,修改完后通过锁的形式写回来更新数据的。

CopyOnWriteArrayList

CopyOnWriteArrayList的类继承图:
--2020-10-14---5.33.27

  • 实现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;
}

新增

写的时候加锁:

  1. 使用ReentrantLock重入锁加锁;
  2. 新建一个数组,大小为原数组长度+1;
  3. 拷贝原数组数据到新数组;
  4. 把新增数据放到数组最后一位
  5. 设置array为新增数组
  6. 解锁

空间复杂度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();
    }
}

删除

删除的时候也需要加锁:

  1. 加锁
  2. 如果移除的是最后一位,则直接拷贝原数组到一个len-1大小的新数组
  3. 如果不是最后一位,新数组保存了原来的数组,并且index后面的数组往前挪一位。
  4. 解锁
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有两个缺点:

  1. 内存占用:数据修改的时候内存同时存在着两份拷贝,如果数据比较多,可能会造成频繁的GC。
  2. 一致性:数据在修改的时候,读线程还是读到的是旧的数组,牺牲了实时一致性,实现的是最终一致性。

CopyOnWriteArraySet

CopyOnWriteArraySet内部使用CopyOnWriteArrayList存储元素,add的时候调用CopyOnWriteArrayList的addIfAbsent即可。

// 内部使用CopyOnWriteArrayList存储元素
private final CopyOnWriteArrayList<E> al;//封装的CopyOnWriteArrayList

public boolean add(E e) {
    return al.addIfAbsent(e);
}
comments powered by Disqus