Java并发编程与技术内幕:CopyOnWriteArrayList、CopyOnWriteArraySet源码解析

桃扇骨 2021-09-11 00:26 363阅读 0赞

林炳文Evankaka原创作品。转载请注明出处[http://blog.csdn.net/evankaka][http_blog.csdn.net_evankaka]  
摘要：本文主要讲了Java中CopyOnWriteArrayList 、CopyOnWriteArraySet的源码分析

# 一、CopyOnWriteArrayList源码分析 #

CopyOnWriteArrayList在java的并发场景中用得其实并不是非常多，因为它并不能完全保证读取数据的正确性。其主要有以下的一些特点：  
1、适合场景读多写少  
2、不能保证读取数据一定是正确 的，因为get时是不加锁的  
3、add、remove会加锁再来操作

下面来看看源码：  
包含的数据结构

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    /** 重入锁*/
    transient final ReentrantLock lock = new ReentrantLock();
    /** 真正存放数据的结构*/
    private volatile transient Object[] array;

其实它的数据结构非常简单，就是一个数组和一个重入锁。

构造函数有三个：

/**
    * 构造函数,创建一个空数组
    */
    public CopyOnWriteArrayList() {
    setArray(new Object[0]);
    }
    
    /**
    * 构造函数,从集合中来初始化列表
    */
    public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements = c.toArray();
    if (elements.getClass() != Object[].class)
    elements = Arrays.copyOf(elements, elements.length, Object[].class);//将elements数组内容都转换成Object类型
    setArray(elements);
    }
    
    /**
    * 构造函数,从数组来初始化列表
    */
    public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));//注意，都向上转型为Object类型
    }

主要方法：  
  
1、add时加锁

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);//将当前elements复制到一个长度加1的数组中
       newElements[len] = e;//设置最后一个元素为e
       setArray(newElements);//设置当前元素数组，在这里如果执行get时就有可能会出错
       return true;
    } finally {
       lock.unlock();//释放锁
    }

这里在注意这个方法：

addIfAbsent这个方法CopyOnWriteArraySet会用到（其实CopyOnWriteArraySet就是封装了一个CopyOnWriteArrayList，下文会说到）

//如果已存在就不放入
     public boolean addIfAbsent(E e) {
    	final ReentrantLock lock = this.lock;
    	lock.lock();//取得锁
    	try {
    	    Object[] elements = getArray();
    	    int len = elements.length;
    	    Object[] newElements = new Object[len + 1];
    	    for (int i = 0; i < len; ++i) { //一个一个元素取出来进行对比
    		if (eq(e, elements[i]))
    		    return false; // 跳出,list中已存在此元素
    		else
    		    newElements[i] = elements[i]; //一个一个拷贝到新数组
    	    }
    	    newElements[len] = e;
    	    setArray(newElements);//设置新数组
    	    return true;//加入成功
    	} finally {
    	    lock.unlock();//释放锁
    	}
        }

2、删除时在加锁  
删除方法一

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;
       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 (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) {
    		int newlen = len - 1;
    		Object[] newElements = new Object[newlen];//设置新数组大小
    
    		for (int i = 0; i < newlen; ++i) {
    		    if (eq(o, elements[i])) {
    			// found one;  copy remaining and exit
    			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();
    	}
        }

3、get时不加锁

public E get(int index) {
    return (E)(getArray()[index]);//直接取得数组对应的索引上的数据就返回了，这里在取得有可能原数组在取完成后就发生改变
    }
    
    final Object[] getArray() {
    return array;
    }

4、contains时不加锁

public boolean contains(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length) >= 0;
    }
    
    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;
    }
    return -1;
    }

# 二、CopyOnWriteArraySet源码分析 #

CopyOnWriteArraySet的原理场景和CopyOnWriteArrayList一样，只不过是不能有重复的元素放入，它里面包含一个CopyOnWriteArrayList，真正调用的方法都 是CopyOnWriteArrayList的方法

数据结构：

public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable {
    private static final long serialVersionUID = 5457747651344034263L;
    
    private final CopyOnWriteArrayList<E> al; //只包含有一个CopyOnWriteArrayList
    。。
    }

可以看到就只有一个CopyOnWriteArrayList一个成员变量

其主要方法：

1、add方法

public boolean add(E e) {
    return al.addIfAbsent(e); //调用CopyOnWriteArrayList的addIfAbsent方法，如果数据重复返回false，不加入
    }

2、remove方法

public boolean remove(Object o) {
    return al.remove(o); //调用CopyOnWriteArrayList 的remove方法
    }

3、CopyOnWriteArraySet没有get方法，只能通过Iterator来依次取

public Iterator<E> iterator() {
    return al.iterator();//调用CopyOnWriteArrayList的iterator（）方法
    }

而CopyOnWriteArrayList的iterator（）方法如下：

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
    }

其中COWIterator是CopyOnWriteArrayList的一个内部类，其主要数据结构如下：

private static class COWIterator<E> implements ListIterator<E> {
    //数组
    private final Object[] snapshot;
    //当前指针指向数组地址
    private int cursor;
    
    private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    snapshot = elements;
    }
    。。。。。
    }

[http_blog.csdn.net_evankaka]: http://blog.csdn.net/evankaka