CopyOnWriteArrayList 的实现原理和适用场景（源码）

CopyOnWriteArrayList的实现原理

核心源码解读

（1）数据结构：采用数组

volatile 保证内存可见性

java">private transient volatile Object[] array;

（2）初始化

java">// 默认创建空数组
public CopyOnWriteArrayList() {setArray(new Object[0]);
}// 可以传入集合进行初始化
public CopyOnWriteArrayList(Collection<? extends E> c) {Object[] elements;if (c.getClass() == CopyOnWriteArrayList.class)elements = ((CopyOnWriteArrayList<?>)c).getArray();else {elements = c.toArray();if (c.getClass() != ArrayList.class)elements = Arrays.copyOf(elements, elements.length, Object[].class);}setArray(elements);
}// 可以传入数组进行初始化
public CopyOnWriteArrayList(E[] toCopyIn) {setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

数组复制使用 Arrays.copyOf 。

（3）add 操作

加锁确保写操作的原子性。

java">final transient ReentrantLock lock = new ReentrantLock();

复制原数组，追加新元素

java">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();}
}

（4）get操作

直接访问数组下标，无锁操作

java">public E get(int index) {return get(getArray(), index);
}private E get(Object[] a, int index) {return (E) a[index];
}final Object[] getArray() {return array;
}

（5）remove操作

主要流程：

先根据当前数组快照，查询是否包含目标元素，若不包含直接返回false；
找到目标元素，加锁，再次获取当前最新数组，遍历快照与当前数组的公共前缀 prefix ，若有更早的匹配项，更新要删除的下标索引index ；
否则判断index是否大于新的长度len，若是，返回false；
否则判断若当前数组在 index 处仍匹配元素，无需更新索引；
否则重新搜索当前数组中该元素的位置index，若不存在, 返回false ;
跳过要删除的元素位置index，复制新数组；

java">public boolean remove(Object o) {// 获取当前数组快照（volatile读，保证可见性）Object[] snapshot = getArray();int index = indexOf(o, snapshot, 0, snapshot.length);return (index < 0) ? false : remove(o, snapshot, index);
}private boolean remove(Object o, Object[] snapshot, int index) {final ReentrantLock lock = this.lock;lock.lock();try {// 再次获取当前最新数组Object[] current = getArray();int len = current.length;// 检查快照 snapshot 是否过时（其他线程写操作可能已修改数组）if (snapshot != current) findIndex: {// 遍历快照与当前数组的公共前缀 prefix，避免全数组扫描，提升性能int prefix = Math.min(index, len);for (int i = 0; i < prefix; i++) {// 若发现当前数组中有对位不等的更早的匹配项（删除或替换了原index前的元素），更新下标index，退出循环if (current[i] != snapshot[i] && eq(o, current[i])) {index = i;break findIndex;}}// 若原下标index已超出当前数组长度，直接返回失败if (index >= len)return false;// 若当前数组在 index 处仍匹配元素，无需更新索引if (current[index] == o)break findIndex;// 否则重新搜索当前数组中该元素的位置index = indexOf(o, current, index, len);if (index < 0)return false;}Object[] newElements = new Object[len - 1];// 复制 index 前的元素System.arraycopy(current, 0, newElements, 0, index);// 复制 index 后的元素（跳过要删除的元素）System.arraycopy(current, index + 1,newElements, index,len - index - 1);// 更新数组引用（volatile写，保证可见性）setArray(newElements);return true;} finally {lock.unlock();}
}

根据下标删除，直接加锁，跳过要删除的下标，复制新数组。

java">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);// 确认要跳过的下标 indexint 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();}
}

（6）计数size

直接访问数组长度

java">public int size() {return getArray().length;
}

（7）遍历操作

迭代器基于 快照数组 实现，确保遍历过程中数据的一致性，但无法反映遍历期间其他线程对列表的修改。

迭代器无法直接修改原数据，直接抛出异常。

java">public Iterator<E> iterator() {return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {/** Snapshot of the array */private final Object[] snapshot; // 快照数组private int cursor; // 遍历下标位置// 构造函数：绑定快照数组 和 初始位置 0 private COWIterator(Object[] elements, int initialCursor) {cursor = initialCursor;snapshot = elements;}// 直接比较下标和快照数组长度public boolean hasNext() {return cursor < snapshot.length;}// 返回当前元素后下标自增@SuppressWarnings("unchecked")public E next() {if (! hasNext())throw new NoSuchElementException();return (E) snapshot[cursor++];}public boolean hasPrevious() {return cursor > 0;}@SuppressWarnings("unchecked")public E previous() {if (! hasPrevious())throw new NoSuchElementException();return (E) snapshot[--cursor];}public int nextIndex() {return cursor;}public int previousIndex() {return cursor-1;}// 不支持修改public void remove() {throw new UnsupportedOperationException();}public void set(E e) {throw new UnsupportedOperationException();}public void add(E e) {throw new UnsupportedOperationException();}@Overridepublic void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);Object[] elements = snapshot;final int size = elements.length;for (int i = cursor; i < size; i++) {@SuppressWarnings("unchecked") E e = (E) elements[i];action.accept(e);}cursor = size;}
}