基于写时复制技术的并发集合———CopyOnWriteArrayList源码分析

目录

概述：

源码分析：

构造方法：CopyOnWriteArrayList()

构造方法：CopyOnWriteArrayList(Collection c)

set(int index, E element)：修改某个下标值

 add(E e)：在尾部添加新元素

add(int index, E element)：在指定位置添加值

remove(int index)：删除指定下标的值

removeRange(int fromIndex, int toIndex)：根据范围删除元素

 clear()：清空集合

addAll(int index, Collection c)：在指定下标位置批量添加元素

概述：

        CopyOnWriteArrayList作为一种线程安全的集合，它通过加Lock锁来实现线程安全，并且它的写是复制技术是指在对集合进行添加或修改。删除等操作时，不会直接对当前集合进行操作，而是根据原集合进行复制一份出来，然后再对拷贝的集合进行操作，当对新集合写入完毕时，再将原集合的引用指向当前的新集合，从而实现写时复制。CopyOnWriteArrayList内部使用Object[]类型数组存储数据，它允许多个线程并发读取，但在写入时，只能有一个线程操作当前集合。

源码分析：

构造方法：CopyOnWriteArrayList()

	// 默认构造方法，创建大小为0的数组
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

构造方法：CopyOnWriteArrayList(Collection c)

	// 有参构造方法，传入一个集合
    public CopyOnWriteArrayList(Collection c) {
        Object[] elements;
        // 如果传入的集合c的Class对象等于CopyOnWriteArrayList的Class对象
        if (c.getClass() == CopyOnWriteArrayList.class)
            // 将c集合强转为CopyOnWriteArrayList并转为数组赋值给elements
            elements = ((CopyOnWriteArrayList)c).getArray();
        else {
            // 否则直接将集合c转为数组赋值给elements
            elements = c.toArray();
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            // 如果elements不等于Object类型则对数组进行复制
            if (elements.getClass() != Object[].class)
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        setArray(elements);
    }

set(int index, E element)：修改某个下标值

// 修改某个下标的值
    public E set(int index, E element) {
		// 加锁
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
			// 获取原数组
            Object[] elements = getArray();
			// 得到下标为index的值
            E oldValue = get(elements, index);
 
			// 如果要修改的值和原值不同则执行
            if (oldValue != element) {
				// 得到新数组的长度
                int len = elements.length;
				// 根据原数组的内容以及长度进行复制
                Object[] newElements = Arrays.copyOf(elements, len);
				// 替换下标为index的值
                newElements[index] = element;
				// 将原数组的引用重新指向新数组
                setArray(newElements);
			// 如果要修改的值和原值相同则执行
            } else {
                // Not quite a no-op; ensures volatile write semantics
				// 将原数组的引用重新指向原数组
                setArray(elements);
            }
			// 将原数组中index下标的值返回
            return oldValue;
        } finally {
			// 解锁
            lock.unlock();
        }
    }

 add(E e)：在尾部添加新元素

// 添加新元素
    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);
 
			// 将添加的元素e添加到新数组的末尾
            newElements[len] = e;
 
			// 重新指向
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

add(int index, E element)：在指定位置添加值

// 在指定位置添加值
    public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
			// 如果下标大于数组长度或小于0 抛下标越界异常
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);
            Object[] newElements;
            int numMoved = len - index;
			// 如果添加位置是最后一个位置，
            if (numMoved == 0)
				// 新数组长度直接加1就行
                newElements = Arrays.copyOf(elements, len + 1);
            else {
				// 否则，新创建一个数组长度为len + 1 的数组
                newElements = new Object[len + 1];
				// 分别复制要插入位置前后两边的数组
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
 
			// 将新元素加入到空出来的那个下标位置
            newElements[index] = element;
            setArray(newElements);
        } finally {
            lock.unlock();
        }
    }

remove(int index)：删除指定下标的值

// 删除指定下标的元素
    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
			// 获取原数组中下标为index的值oldValue
            E oldValue = get(elements, index);
			// 计算要删除的元素是否是最后一个
            int numMoved = len - index - 1;
			// 如果是
            if (numMoved == 0)
				// 直接复原原数组直到最后一个元素之前并重新指向
                setArray(Arrays.copyOf(elements, len - 1));
            else {
				// 创建原数组长度 - 1的数组
                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;
			
			// 如果开始下标<0 或者结束下标大于数组长度或者结束下标小于开始下标
			// 抛下标越界异常
            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 {
				// 新建一个数组，长度为newlen的
                Object[] newElements = new Object[newlen];
				// 同上
                System.arraycopy(elements, 0, newElements, 0, fromIndex);
                System.arraycopy(elements, toIndex, newElements,
                                 fromIndex, numMoved);
                setArray(newElements);
            }
        } finally {
            lock.unlock();
        }
    }
 

 clear()：清空集合

// 清空集合中元素
    public void clear() {
        final ReentrantLock lock = this.lock;
	// 加锁
        lock.lock();
        try {
		// 将原数组修改我object[]类型的空数组
            setArray(new Object[0]);
        } 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];
		// 同上
                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();
        }
    }
}