集合源码-CopyOnWriteArrayList

1、简介

CopyOnWriteArrayList是ArrayList的线程安全版本，内部也是通过数组实现，每次对数组的修改都完全拷贝一份新的数组来修改，修改完了再替换掉老数组，这样保证了只阻塞写操作，不阻塞读操作，实现读写分离。

2、继承体系

CopyOnWriteArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable等接口。

3、源码解析

3.1 属性

// lock锁 final transient ReentrantLock lock = new ReentrantLock(); // volatile 多线程可见 private transient volatile Object[] array; // 没有size // 在插入时拷贝一份，插入完还没有赋值给array， size就是旧值

3.2 构造方法

public CopyOnWriteArrayList() { setArray(new Object[0]); } final void setArray(Object[] a) { array = a; } public CopyOnWriteArrayList(Collection<? extends E> c) { Object[] elements; // 如果c是CopyOnWriteArrayList类型，直接把它的数组赋值给当前list的数组， // 注意这里是浅拷贝，两个集合共用同一个数组。 if (c.getClass() == CopyOnWriteArrayList.class) elements = ((CopyOnWriteArrayList<?>)c).getArray(); else { // 如果c不是CopyOnWriteArrayList类型，则进行拷贝把c的元素全部拷贝到当前list的数组中。 // 这里c.toArray()返回的不一定是Object[]类型 elements = c.toArray(); 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)); }

3.3 添加元素

尾部添加 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(); } } 插入元素 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; // 拷贝数组 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 addIfAbsent(E e) { Object[] snapshot = getArray(); // 不存在则插入 return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : addIfAbsent(e, snapshot); } // 判断是否存在当前快照 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; }

3.4 获取元素

public E get(int index) { return get(getArray(), index); } // 这里是没有做越界检查的, 因为数组本身会做越界检查 private E get(Object[] a, int index) { return (E) a[index]; }

3.5 删除元素

// 同理，加锁拷贝删除 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(); } }

4、总结

CopyOnWriteArrayList使用ReentrantLock重入锁加锁，保证线程安全；CopyOnWriteArrayList的写操作都要先拷贝一份新数组，在新数组中做修改，修改完了再用新数组替换老数组，所以空间复杂度是O(n)，性能比较低下；CopyOnWriteArrayList采用读写分离的思想，读操作不加锁，写操作加锁，且写操作占用较大内存空间，所以适用于读多写少的场合；CopyOnWriteArrayList只保证最终一致性，不保证实时一致性；