Collection - CopyOnWriteArrayList 源码解析

介绍

Java 中的 ArrayList 是一个非线程安全的集合类，也就是说，当多个线程对 ArrayList 进行并发读写时，就可能会出现问题。

虽然可以使用 Vector 来保证同步操作，解决线程安全问题，但是由于 Vector 只是简单的在接口上加 synchronized 关键字进行同步，即使 synchronized 已经做了很多优化（性能极大地提升），但是 Vector 中在方法级别加 synchronized，同步的代码区域太大，吞吐量并不会太高。

CopyOnWriteArrayList，就是线程安全版的 ArrayList，可以支持多线程并发修改获取数组元素，利用的就是上面写时复制的原理。

CopyOnWriteArrayList 的实现

重要属性

/**
 * 用于加锁（可重入，默认为非公平锁）
 */
final transient ReentrantLock lock = new ReentrantLock();
 
/**
 * 保存数据的数组
 */
private transient volatile Object[] array;

对的，CopyOnWriteArrayList 就只有上面两个属性，比 ArrayList 少了很多，ArrayList 中初始容量、扩容阈值、树化阈值、负载因子....

CopyOnWriteArrayList 中的数组（也就是array），每次都是毫不浪费，刚好装下所有元素（其实是每次添加元素的时候则增加一个位置，删除元素后就释放一个位置，所以数组的长度始终和元素的个数相同）。

getArray() 和 setArray()

CopyOnWriteArrayList 中有两个私有的方法，用来获取和设置 array 属性值，几乎贯穿 CopyOnWriteArrayList 整个源码。

/**
 * 获取当前的数组
 */
final Object[] getArray() {
    return array;
}
 
/**
 * 将传入的数组替换掉已有的数组（修改数据后替换掉旧数组）
 */
final void setArray(Object[] a) {
    array = a;
}

构造方法

/**
 * 创建一个空数组的CopyOnWriteArrayList实例
 */
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}
 
/**
 * 利用已有的集合元素创建CopyOnWriteArrayList实例
 */
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements; // 副本
 
    if (c.getClass() == CopyOnWriteArrayList.class) {
        elements = ((CopyOnWriteArrayList<?>) c).getArray();
    } else {
        // 将传入的集合转为数组形式
        elements = c.toArray();
        if (elements.getClass() != Object[].class) {
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
    }
 
    // 将array属性设置指向本次创建的副本
    setArray(elements);
}
 
/**
 * 利用传入的数组来创建CopyOnWriteArrayList实例
 */
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

获取元素

获取元素，和 ArrayList 接口一样，都是 get(index)，但是需要注意的是，CopyOnWriteArrayList 在 get 元素的时候并不做数组越界检测。

/**
 * 获取数组index位置的元素
 */
public E get(int index) {
    // 先调用getArray获取数组，然后调用内部的get方法进行返回元素
    return get(getArray(), index);
}
 
/**
 * 获取指定数组的指定位置元素
 */
private E get(Object[] a, int index) {
    return (E) a[index];
}

添加元素

/**
 * 追加元素到集合中
 */
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;
 
        // 插入位置越界检测
        if (index > len || index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + len);
        }
 
        // 计算需要移动的元素个数
        Object[] newElements;
        int numMoved = len - index;
 
        if (numMoved == 0) {
            // 需要移动元素的个数为0，表示追加（直接申请len+1长度的数组）
            newElements = Arrays.copyOf(elements, len + 1);
        } else {
            // 有元素需要移动，先申请len+1长度的数组
            newElements = new Object[len + 1];
             
            // 将旧数组中0 - index-1元素拷贝到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            // 将旧数组中index以及后面的元素拷贝到新数组中（index位置空余）
            System.arraycopy(elements, index, newElements, index + 1, numMoved);
        }
         
        // 将新元素放入空出的index位置
        newElements[index] = element;
         
        // 新数组替换掉旧数组
        setArray(newElements);
    } finally {
        // 解锁
        lock.unlock();
    }
}

删除元素

/**
 * 删除指定位置的元素
 */
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) {
            // 如果要移动的元素为0，证明删除的最后一个元素
            // 则直接创建一个新数组（长度为len-1），并将前len-1个元素拷贝到新数组中，并替换掉旧数组
            setArray(Arrays.copyOf(elements, len - 1));
        } else {
            // 删除的元素不是在最后，那么就申请len-1长度的数组
            Object[] newElements = new Object[len - 1];
 
            // 将0~len-1和len+1~end的元素拷贝到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index, numMoved);
             
            // 替换掉旧数组
            setArray(newElements);
        }
         
        // 返回删除的元素
        return oldValue;
    } finally {
        // 解锁
        lock.unlock();
    }
}

/**
 * 删除元素（删除成功范围true，未找到或者删除失败返回false）
 */
public boolean remove(Object o) {
    // 获取当前数组
    Object[] snapshot = getArray();
 
    // 在数组中查找要删除的元素
    int index = indexOf(o, snapshot, 0, snapshot.length);
 
    // index<0，表示未找到元素；否则进行删除元素
    return (index < 0) ? false : remove(o, snapshot, index);
}
 
/**
 * 在elements数组中的index到fence范围内查找元素o
 *
 * @param o        要查找的元素
 * @param elements 在该数组中查找
 * @param index    查找的其实位置
 * @param fence    屏障（查找结束的位置）
 * @return 如果查找到元素，则返回元素所在位置；如果没有查找到，则返回-1
 */
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;
            }
        }
    }
 
    // 未找到元素，则返回-1
    return -1;
}
 
/**
 * 删除snapshot数组中index位置的元素o
 * 不是直接删除快照数组中的index位置的元素，而是经过一番比较，确定要删除的元素的真实位置
 * 然后在申请一个新数组，将index以外的其他元素拷贝到新数组中，并替换新数组，以此达到删除的效果
 */
private boolean remove(Object o, Object[] snapshot, int index) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    try {
        // 获取数组
        Object[] current = getArray();
        int len = current.length;
 
        // 如果传入的数组快照和当前的最新数组不匹配（发生了增删）
        if (snapshot != current) findIndex:{
            // 获取新数组的长度，与传入的index进行比较（确定查找范围，以小者为准）
            int prefix = Math.min(index, len);
 
            // 遍历数组，
            for (int i = 0; i < prefix; i++) {
                // 如果数组快照和新数组的元素不匹配，并且最新数组的该位置上的元素就是要删除的元素
                // 此时修改要index（改为要删除元素当前的最新位置），并结束循环
                if (current[i] != snapshot[i] && eq(o, current[i])) {
                    index = i;
                    break findIndex;
                }
            }
 
            // 如果新数组的长度小于传入的要删除元素的index，则证明未找到该元素
            if (index >= len) {
                return false;
            }
 
            // 如果当前数组的index位置为要删除的元素（找到要删除的元素位置），则跳出if
            if (current[index] == o) {
                break findIndex;
            }
 
            // 在最新数组中查找要删除的元素，如果最新数组未找到要删除的元素，则删除失败，返回false
            index = indexOf(o, current, index, len);
            if (index < 0) {
                return false;
            }
        }
 
        // 当前最新的数组为len，因为找到了要删除的元素，则申请一个新的数组（长度为len-1）
        Object[] newElements = new Object[len - 1];
 
        // 将当前最新的数据，0~index-1的元素拷贝到新数组中
        System.arraycopy(current, 0, newElements, 0, index);
        // 将当前最新的数据，index+1及后面的数据拷贝到新数组中
        System.arraycopy(current, index + 1, newElements, index, len - index - 1);
 
        // 使用新数组替换掉旧数组，因为删除了元素，所以返回true
        setArray(newElements);
        return true;
    } finally {
        // 解锁
        lock.unlock();
    }
}

修改元素

/**
 * 修改index位置的元素，设置为element，并返回旧值
 */
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    try {
        // 获取旧数组中index位置的值
        Object[] elements = getArray();
        E oldValue = get(elements, index);
 
        // 如果index位置的值和要修改的值不相同，那需要进行修改操作
        if (oldValue != element) {
            // 获取当前数组的长度
            int len = elements.length;
             
            // 创建一个新数组（新数组长度和旧数组长度保持一致），并将旧数组中全部元素拷贝到新数组中
            Object[] newElements = Arrays.copyOf(elements, len);
            // 修改新数组中的index位置的元素
            newElements[index] = element;
             
            // 新数组替换掉旧数组
            setArray(newElements);
        } else {
            // 如果index位置的值和要修改的值相同，那么不用进行修改操作（避免申请数组、拷贝的开销）
            setArray(elements);
        }
         
        // 返回旧值
        return oldValue;
    } finally {
        lock.unlock();
    }
}

元素增删改总结

上面在添加元素、删除元素、修改元素中，可以看到，CopyOnWriteArrayList 每次进行写操作的时候，都是这样一个步骤：

• 加锁；
• 获取当前数组（snapshot快照）；
• 创建新数组，然后在新数组中进行修改操作；
• 将修改完后的新数组替换掉snapshot快照数组；
• 解锁。

需要注意的是，当一个线程 A 在遍历 CopyOnWriteArrayList 时，当另外一个线程 B 对 CopyOnWriteArrayList 进行了修改操作，线程 B 修改完成后（已经将新数组替换掉旧数组），但是线程 A 查看的仍旧是旧的数组（snapshot），除非重新获取数组。

适用场景

CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。

但是 CopyOnWriteArrayList 有其缺陷：

• 内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
• 数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

参考

• https://www.cnblogs.com/-beyond/p/13130040.html