【CopyOnWriteArrayList源码分析】

目录

一、CopyOnWriteArrayList概述

二、源码分析

add()方法

get()方法

remove()方法

removeRange(int fromIndex, int toIndex)

addAll(int index, Collection c)

retainAll(Collection c)方法

clear()清空集合

三、总结：

CopyOnWriteArrayList 具有以下特性：

---

一、CopyOnWriteArrayList概述

        Copy-On-Write 简称 COW ，是一种用于集合的并发访问的优化策略。基本思想是：当 我们往一个集合容器中写入元素时（添加、修改、删除），并不会直接在集合容器中写入，而 是先将当前集合容器进行Copy，复制出一个新的容器，然后新的容器里写入元素，写入操作 完成之后，再将原容器的引用指向新的容器。

         这样做的好处：实现对 CopyOnWrite 集合容器写入操作时的线程安全，但同时并不影响 进行并发的读取操作。所以 CopyOnWrite 容器也是一种读写分离的思想。从 JDK1.5 开始 Java 并发包里提供了两个使用 CopyOnWrite 机制实现的并发集合容器,它们是 CopyOnWri teArrayList 和 CopyOnWriteArraySet 。

         CopyOnWriteArrayList 相当于线程安全的 ArrayList ，内部存储结构采用 Obj ect[] 数组，线程安全使用 ReentrantLock 实现，允许多个线程并发读取，但只能有一个 线程写入。

二、源码分析

add()方法

        添加新元素至集合时，会将当前数组 Copy 复制新数组，并将新元素添加至新数组，最后替换原数组。执行过程 中，使用 ReentrantLock 加锁，保证线程安全，避免多个线程复制数组。

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
 
        // 复制出新数组
        Object[] newElements = Arrays.copyOf(elements, len + 1);
 
        // 把新元素添加到新数组里
        newElements[len] = e;
 
        // 把原数组引用指向新数组
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

get()方法

根据指定下标，到原数组中读取元素。读取过程中不加锁，允许多个线程并发读取。但是 如果读取的时候，有其它线程向集合中添加新元素，此时仍然读取到的是旧数据。因为添加操 作没有对原数组加锁。

public E get(int index) {
    // 根据指定下标，从原数组中读取元素
    return get(getArray(), index);
}
 
private E get(Object[] a, int index) {
    return (E) a[index];
}

remove()方法

        删除指定下标元素。根据指定下标，从原数组中， Copy 复制其它元素至新数组，最后替 换原数组。

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)
            // 复制原数组中，除最后一个元素以外的所有元素，至新数组
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 复制原数组中，除删除元素以外的所有元素，至新数组
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

removeRange(int fromIndex, int toIndex)

删除指定范围的元素

 void removeRange(int fromIndex, int toIndex) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            //获取原数组
            Object[] elements = getArray();
            int len = elements.length;
 
            //判断下标是否越界
            if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
                throw new IndexOutOfBoundsException();
 
           //原数组长度
             int newlen = len - (toIndex - fromIndex);
            int numMoved = len - toIndex;
 
           //判断指定尾下标是否是数组尾下标
             if (numMoved == 0)
                //复制newLen长度
                setArray(Arrays.copyOf(elements, newlen));
            else {
                Object[] newElements = new Object[newlen];
                //复制fromIndex长度
                System.arraycopy(elements, 0, newElements, 0, fromIndex);
 
               //原数组从toIndex下标开始，新数组从fromIndex开始复制numMoved长度
                 System.arraycopy(elements, toIndex, newElements,
                                 fromIndex, numMoved);
                setArray(newElements);
            }
        } finally {
            //解锁
            lock.unlock();
        }
    }

addAll(int index, Collection c)

在指定位置批量添加元素

 // 在指定位置批量添加元素
    public boolean addAll(int index, Collection c) {
      // 将集合c转换为数组并赋值给cs
        Object[] cs = c.toArray();
        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);
//        如果集合c为空，则直接返回false
            if (cs.length == 0)
                return false;
            int numMoved = len - index;
            Object[] newElements;
 
//         如果numMoved等于0，则代表在原集合末尾添加
            if (numMoved == 0)
//         复制原集合，个数为原集合元素个数加要添加的元素个数
                newElements = Arrays.copyOf(elements, len + cs.length);
            else {
//         创建新集合
                newElements = new Object[len + cs.length];
//              该操作与add(int index, E element)方法同理
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index,
                                 newElements, index + cs.length,
                                 numMoved);
            }
//               复制数组至新数组
            System.arraycopy(cs, 0, newElements, index, cs.length);
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

retainAll(Collection c)方法

    public boolean retainAll(Collection c) {
    	//判断集合是否为null
        if (c == null) throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
			//获取当前集合对象中数组
            Object[] elements = getArray();
            int len = elements.length;
            //若当前数组不为空
            if (len != 0) {
                // temp array holds those elements we know we want to keep
                int newlen = 0;
                //创建新temp数组
                Object[] temp = new Object[len];
				//遍历数组
                for (int i = 0; i < len; ++i) {
                    Object element = elements[i];
                    //判断集合c中是否包含elements中的元素
                    if (c.contains(element))
                    	//包含则将元素存入temp数组
                        temp[newlen++] = element;
                }
                //中间数组下标+1之后不等于elements数组长度
                if (newlen != len) {
                	//使用newlen作为新数组长度复制
                    setArray(Arrays.copyOf(temp, newlen));
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

clear()清空集合

 public void clear() {
        //加锁
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            //设置数组为空数组
            setArray(new Object[0]);
        } finally {
            //解锁
            lock.unlock();
        }
    }

三、总结：

CopyOnWriteArrayList 具有以下特性：

1在保证并发读取的前提下，确保了写入时的线程安全；

2 由于每次写入操作时，进行了Copy复制原数组，所以无需扩容；

3 适合读多写少的应用场景。由于 add() 、 set() 、 remove() 等修改操作需要复制整 个数组，所以会有内存开销大的问题。

4 CopyOnWriteArrayList 由于只在写入时加锁，所以只能保证数据的最终一致性，不能 保证数据的实时一致性。