《CopyOnWriteArrayList源码分析》

约定不等于承诺〃 2024-05-07 17:14 54阅读 0赞

### CopyOnWriteArrayList ###

CopyOnWriteArrayList是线程安全的ArrayList，可直接在多线程环境下使用，无需加锁。它通过**ReentrantLock锁+数组copy+volatile关键字**保证了线程安全。

1 .CopyOnWriteArrayList类的底层代码是由ReentrantLock加锁实现线程安全，并且它的底层数组通过volatile关键字修饰，数组一旦被修改，其他线程会立马感知到。

> // 使用ReentrantLock 可重入锁加锁  
> final transient ReentrantLock lock = new ReentrantLock();  
> // volatile 关键字保证数组可见性  
> private transient volatile Object\[\] array; // 内部用来存放数据的数组

### 2. 读取操作 ###

读取操作就是获取array数组，此操作不会对元素的值做出改变，因此不需要加锁，允许多个线程同时读取。  
CopyOnWriteArrayList 支持并发读，只有当写的时候才会加锁，所以在读多写少的场景下性能更好。

final Object[] getArray() {		
            return array;	// 返回array数组
        }
    
        final void setArray(Object[] a) {
            array = a;	// 当前数组指向参数数组
        }

首先CopyOnWriteArrayList会在无参构造方法中初始化一个长度为0的数组

// 无参构造方法
        public CopyOnWriteArrayList() {
            setArray(new Object[0]);		// 创建了一个个数为0的新数组
        }
    
    	// 有参构造方法
        public CopyOnWriteArrayList(Collection<? extends E> c) {      // 传入一个集合	
            Object[] elements;
    
    		// 判断当前集合对象是否属于CopyOnWriteArrayList类
            if (c.getClass() == CopyOnWriteArrayList.class)	
    			// 将传入的集合返回当前数组
                elements = ((CopyOnWriteArrayList<?>)c).getArray(); 
            else {
                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); // 返回新数组
        }

### **写入操作** ###

CopyOnWriteArrayList的添加，修改，替换都属于写入操作，在这些过程中都需要通过加锁来实现线程安全，保证了在这次写入操作时只有一个线程来获取当前锁对其进行改变。

### 1. 替换 ###

替换元素就是将原数组作为备份，创建长度不变的新数组，然后(在指定位置)替换元素，并且新数组替换原数组(此过程需要加锁)。

// 替换指定下标的数据
        public E set(int index, E element) {
            final ReentrantLock lock = this.lock; // 获取当前线程的锁
            lock.lock(); // 加锁
            try {
                Object[] elements = getArray(); // 获取array数组并赋给elements
    
    			// 获取原来指定下标位置的值
                E oldValue = get(elements, index); 
    
    			// 判断旧值与要修改的值是否相等
                if (oldValue != element) { // 否
                    int len = elements.length; 
                    Object[] newElements = Arrays.copyOf(elements, len); // 将数组复制到一个新数组(长度相等)
                    newElements[index] = element; // 修改新数组指定位置的值
                   
    			   // 指向新数组
    				setArray(newElements); 
                } else {
    				// 要修改的元素与旧值相等时，指向数组
                    // Not quite a no-op; ensures volatile write semantics
                    setArray(elements);
                }
                return oldValue;
            } finally {
                lock.unlock(); // 释放锁
            }
        }

### 2. 添加 ###

添加操作同样就是创建原数组容器的备份作为新数组容器，并且长度加一，然后(在指定位置)添加数据，添加完成后将新数组替换成旧数组(此过程需要加锁)。

// 添加
        public boolean add(E e) {
            final ReentrantLock lock = this.lock; // 使用ReentrantLock可重入锁同步线程
            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 {
    			// 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;
    			
    			// 如果插入的位置等于数组末尾位置,直接复制数组并且长度+1
                if (numMoved == 0)
                    newElements = Arrays.copyOf(elements, len + 1);
                else {
    				// 如果插入的位置在数组中间，将原数组分两部分复制到新数组
                    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();
            }
        }

// 指定位置添加集合
        public boolean addAll(int index, Collection<? extends E> c) {
    		// 将传入的集合转化为数组
            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);
    			// 如果传入的数组长度为0
                if (cs.length == 0)
                    return false;
                int numMoved = len - index; 
                Object[] newElements;
    
    			// 如果在原数组末尾添加
                if (numMoved == 0)
    				// 复制原数组到新数组并且长度+len
                    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();
            }
        }
    }

### 3. 删除 ###

删除操作首先也是创建一个新数组，但是其长度等于原数组长度-1，然后把原数组中除了要删除的元素都拷贝到新数组中，并且返回到新数组(此过程需要加锁)。

// 删除
        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 {
    				// 如果要删除的数据在数组中间
    				// 创建一个新数组，长度等于原数组长度+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();
            }
        }
    
    	// 批量删除
        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; // 要删除的数组长度
                
    			// 如果删除个数为0
    			if (numMoved == 0)
    				// 直接将原数组复制并返回
                    setArray(Arrays.copyOf(elements, newlen));
                else {
    				// 删除个数>0
    				// 创建新数组 
                    Object[] newElements = new Object[newlen];
    				
    				// 将起始位置之前，结束位置之后的数组内容分别复制到新数组 
                    System.arraycopy(elements, 0, newElements, 0, fromIndex);
                    System.arraycopy(elements, toIndex, newElements,
                                     fromIndex, numMoved);
    
    				// 将新数组返回
                    setArray(newElements);
                }
            } finally {
                lock.unlock();
            }
        }

### 4.清除 ###

清除操作就是将原来的数组的初始化为一个空数组，此过程也需要加锁。

// 清除
        public void clear() {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
    			// 将数组长度初始化为0
                setArray(new Object[0]);
            } finally {
                lock.unlock();
            }
        }

### 总结 ###

CopyOnWriteArrayList是线程安全的ArrayList,它的读操作作用在旧容器，写操作作用在新容器下(拷贝数组)，不会影响到原来的数组。  
**CopyOnWriteArrayList在对数组操作时会：  
加锁；  
将原数组拷贝到新数组；  
在新数组上进行操作，并返回(不会影响到原数组 安全！)；  
解锁。**

从写入操作(添加，修改，删除等)可以看出：它的线程安全是通过**加锁+拷贝数组+volatile**保证的。

> ReentrantLock加锁：保证同一时刻数组只能被一个线程操作  
> 数组拷贝：保证数组内存地址修改后会触发volatile的可见性，其他线程会立马知道该数组被修改  
> volitile：值被修改后，其他线程能够立马知道。

它具有读写分离的思想：读操作不加锁，写操作加锁，它支持并发读，所以CopyOnWriteArrayList在读多写少的环境下效率较高，只不过每次写入操作都会复制数组，比较消耗内存。