JAVA集合系列——CopyOnWriteArrayList实现原理

文章目录

1. 1. CopyOnWriteArrayList实现原理
   1. 1.1. 特点
   2. 1.2. 数据结构
   3. 1.3. 存取实现
      1. 1.3.1. 初始化
      2. 1.3.2. 存储
      3. 1.3.3. 获取
      4. 1.3.4. 删除
      5. 1.3.5. 迭代
   4. 1.4. 相关

CopyOnWriteArrayList实现原理

特点

1. COW机制实现
2. 有序的
3. 线程安全
4. 读写分离

数据结构

COW就是Copy-On-Write，是程序设计的一种优化策略；当我们需要对一份共享的数据进行修改时，我们可以先将这份共享数据拷贝一份，待我们修改完成后再将这份拷贝放回原始引用处，所以COW实现机制的容器也被叫做即写时复制容器。这样做的好处就是在多线程的环境中，我们获取元素的时候仍然不需要加锁。CopyOnWriteArrayList底层和ArrayList一样，都是使用数组来保存所有元素的。

//锁，在新增修改是实现并发控制
transient final ReentrantLock lock = new ReentrantLock();
//数组，用来保存元素，volatile实现多线程时的可见性
private volatile transient Object[] array;

存取实现

初始化

CopyOnWriteArrayList和ArrayList的初始化有些不同，ArrayList有几个初始化方法，包括设置初始容量和加载因子等，但是CopyOnWriteArrayList没有初始容量和加载因子设置，默认构造函数初始化的容器容量为0。为什么CopyOnWriteArrayList没有初始容量和加载因子呢？大家考虑下。

//默认构造
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

//集合构造
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements = c.toArray();
	// c.toArray might (incorrectly) not return Object[] (see 6260652)
	if (elements.getClass() != Object[].class)
	    elements = Arrays.copyOf(elements, elements.length, Object[].class);
	setArray(elements);
}

//数组构造
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

存储

新增元素的时候，仍然需要锁，不然并发环境下，每次新增的时候都拷贝一份副本，JVM受得了吗！

//新增
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;
	    //判断index是否越界
	    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 {
    	    //拷贝一个副本，并扩容1位
    		newElements = new Object[len + 1];
    		//将index前的元素拷贝到副本中
    		System.arraycopy(elements, 0, newElements, 0, index);
    		//将index后的元素拷贝到副本中
    		System.arraycopy(elements, index, newElements, index + 1,
				 numMoved);
	    }
	    //将新增的元素放到index位子
	    newElements[index] = element;
	    //将原始容器引用指向副本
	    setArray(newElements);
	} finally {
	    //解锁
	    lock.unlock();
	}
}

//替换
public E set(int index, E element) {
	final ReentrantLock lock = this.lock;
	//加锁
	lock.lock();
	try {
	    Object[] elements = getArray();
	    //获取原来index位置的元素
	    Object oldValue = 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);
	    }
	    //返回旧值
	    return (E)oldValue;
	} finally {
	    //解锁
	    lock.unlock();
	}
}

获取

CopyOnWriteArrayList的获取元素十分的简单，没有加锁，即使是在多线程并发的环境下。所以CopyOnWriteArrayList的获取效率十分的高，适用在读大于写的场景中。

//根据索引获取元素
public E get(int index) {
    return (E)(getArray()[index]);
}

删除

//根据索引删除元素
public E remove(int index) {
	final ReentrantLock lock = this.lock;
	lock.lock();
	try {
	    Object[] elements = getArray();
	    int len = elements.length;
	    //获取老元素
	    Object oldValue = elements[index];
	    //需要移动元素的个数
	    int numMoved = len - index - 1;
	    //如果不需要移动，则拷贝一个副本，并且容量-1
	    if (numMoved == 0)
		    setArray(Arrays.copyOf(elements, len - 1));
	    else {
	        //新建一个数组
    		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 (E)oldValue;
	} finally {
	    lock.unlock();
	}
}

//根据对象删除元素
public boolean remove(Object o) {
	final ReentrantLock lock = this.lock;
	//加锁
	lock.lock();
	try {
	    Object[] elements = getArray();
	    int len = elements.length;
	    if (len != 0) {
    		// Copy while searching for element to remove
    		// This wins in the normal case of element being present
    		// 新建一个容量为len-1的数组
    		int newlen = len - 1;
    		Object[] newElements = new Object[newlen];
            
    		for (int i = 0; i < newlen; ++i) {
    		    //如果匹配到了
    		    if (eq(o, elements[i])) {
        			// 依次将之后的元素拷贝到新数组中，然后返回ture
        			for (int k = i + 1; k < len; ++k)
        			    newElements[k-1] = elements[k];
        			setArray(newElements);
        			return true;
    		    } else
    		        //没有匹配就拷贝元素
    			    newElements[i] = elements[i];
    		}
    
    		// 对最后一个元素进行匹配
    		if (eq(o, elements[newlen])) {
    		    setArray(newElements);
    		    return true;
    		}
	    }
	    return false;
	} finally {
	    //解锁
	    lock.unlock();
	}
}

//删除索引范围内的元素
private void removeRange(int fromIndex, int toIndex){
    ...
}

迭代

CopyOnWriteArrayList也有迭代器，但是是阉割版的,迭代器中不支持调用add，set，remove等方法，否则会抛出异常；当使用迭代器时，迭代器会使用一个引用指向当前的原始数据，所以并发环境下，其他线程修改元素数据的时候，不会影响到迭代的数据，是线程安全的。

 private static class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array **/
    //用于保存迭代时的数据
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }
    
    ...
    
    public void remove() {
        throw new UnsupportedOperationException();
    }

    public void set(E e) {
        throw new UnsupportedOperationException();
    }
  
    public void add(E e) {
        throw new UnsupportedOperationException();
    }
}

相关

CopyOnWriteArrayList适用于读大于写的场景中，不适合大量的写操作，因为会产生内存大量占用的问题和数据一致性的问题；比如我们要添加多个元素到CopyOnWriteArrayList中的时候，避免使用循环add方法的方式，而是采用addAll的方式，这样就不会产生大量的内存占用，甚至内存溢出；在数据一致性要求比较严格的情景，也要避免使用CopyOnWriteArrayList，要知道CopyOnWriteArrayList只能保证数据的最终一致性，而不能保证实时的数据一致性。