并发安全的CopyOnWriteArrayList

in java并发 with 0 comment

CopyOnWriteArrayList是ArrayList的线程安全版本,内部也是通过数组实现,每次对数组的修改都完全拷贝一份新的数组来修改,修改完了再替换掉老数组,这样保证了只阻塞写操作,不阻塞读操作,实现读写分离。

内部的主要实现

主要是通过ReentrantLock加锁和一个volatile修饰的Object数组。
真正的对象都存放在Object数组中

    // 修改时加锁
    final transient ReentrantLock lock = new ReentrantLock();
    // 真正存储元素的地方,只能通过getArray()和setArray()方法访问
    private transient volatile Object[] array;

构造方法

他的构造方法有三个

    // 创建一个空数组
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

    public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements;
        if (c.getClass() == CopyOnWriteArrayList.class)
            // 如果c也是CopyOnWriteArrayList类型那么直接把它的数组拿过来使用
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
            // 否则将集合元素转化为数组
            elements = c.toArray();
            // c.toArray 可能不是一个Object类型的数组
            if (elements.getClass() != Object[].class)
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
	// 浅拷贝
        setArray(elements);
    }	
    // 把toCopyIn的元素拷贝给当前list的数组
    public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

真正操作数组的两个方法

真正操作数组的只有getArray()和setArray()方法

getArray()方法

final Object[] getArray() {
        return array;
    }

直接返回的是volatile修饰的Object数组

setArray()方法

final void setArray(Object[] a) {
        array = a;
    }

将volatile修饰的Object数组变为a

add增加元素的方法

 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;
            // 重新定义整一手volatile类型的数组
            setArray(newElements);
            return true;
        } finally {
            // 释放锁
            lock.unlock();
        }
    }

使用getArray方法搞到真实的数组,然后操作一手,再把操作后的数组setArray

get获得元素的方法

public E get(int index) {
        // 直接返回index位置的元素
        // 这里是没有做越界检查的, 因为数组本身会做越界检查
        return get(getArray(), index);
    }
private E get(Object[] a, int index) {
        return (E) a[index];
    }

可以看见,CopyOnWriteArrayList它在获得元素时,并没有加锁。它获得的元素时此刻的真实Object数组,所以,在并发条件下,CopyOnWriteArrayList获得的元素是不一致的。

remove移除元素

public E remove(int index) {
        final ReentrantLock lock = this.lock;
        // 加锁
        lock.lock();
        try {
            // 获得真实的数组
            Object[] elements = getArray();
            // 获得长度
            int len = elements.length;
            // 简单的讲这里就是获得当前index位置的元素,也相当于做了一次越界检查
            E oldValue = get(elements, index);
            // 长度减一
            int numMoved = len - index - 1;
            if (numMoved == 0)
                // 刚好删除的是最后一位, 直接拷贝一份len-1的新数组, 最后一位就自动删除了
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                // 不是最后一位就创建一个长度减一的新数组
                Object[] newElements = new Object[len - 1];
                // 数组的复制
                System.arraycopy(elements, 0, newElements, 0, index);
                // 将index后面(不包含)的元素往前挪一位 就等于删除了index位置元素
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                // 设置Object数组为新的数组
                setArray(newElements);
            }
            return oldValue;
        } finally {
            // 解锁
            lock.unlock();
        }
    }

在移除元素时,加锁保证安全。最后的移除操作也是通过数组复制,然后将新数组设置为volatile修饰的Object数组。

关于CopyOnWriteArrayList的size属性

ArrayList是有size属性的,它记录了ArrayList的长度,同时也是用来ArrayList扩容的。
但是CopyOnWriteArrayList它是没有size属性的。
因为每次修改都是拷贝一份正好可以存储目标个数元素的数组,所以不需要size属性了,数组的长度就是集合的大小,而不像ArrayList数组的长度实际是要大于集合的大小的。
比如,add(E e)操作,先拷贝一份n+1个元素的数组,再把新元素放到新数组的最后一位,这时新数组的长度为len+1了,也就是集合的size了。
它的size方法

    // 获得当前数组的size
    public int size() {
        return getArray().length;
    }

它在获得size长度也是没有加锁的,在这里,还是不保证实时一致性。

总结

  1. CopyOnWriteArrayList使用ReentrantLock加锁
  2. CopyOnWriteArrayList的写操作都要加锁的,实现的过程是先拷贝一份新数组,在新数组中做修改,修改完了再用新数组替换老数组。性能低
  3. CopyOnWriteArrayList的读操作是通过获得数组的元素,所以CopyOnWriteArrayList不保证实时一致性。
  4. CopyOnWriteArrayList使用读写分离的思想,读操作不加锁,写操作加锁。
  5. CopyOnWriteArrayList在写操作因为会拷贝数组,所以会空间占有较大。
  6. CopyOnWriteArrayList的使用场景是读多写少的并发条件。如黑名单和白名单。
  7. CopyOnWriteArrayList没有size属性。它的长度是由真正存放元素的Object数组确定的。