CopyOnWriteArrayList详解

因为我们java的util包下的常用集合类java.util.ArrayList、java.util.HashMap都是非线程安全的，虽然Vector和Hashtable是线程安全的，但是因为大部分方法都是通过synchronized关键字修饰，性能太低。

于是，从jdk1.5开始，java开发者提供了性能更高的线程安全类ConcurrentHashMap和CopyOnWriteArrayList。

目录

CopyOnWriteArrayList

静态方法

indexOf

 lastIndexOf

实例方法

contains

indexOf

lastIndexOf

toArray()

get

set

add

remove

removeRange

addIfAbsent

containsAll

addAllAbsent

clear

addAll

forEach

removeIf

replaceAll

sort

---

CopyOnWriteArrayList

CopyOnWriteArrayList是jdk1.5推出的一个能保证线程安全的List接口实现类，底层也基于动态数组实现的。其设计思想是写时复制（Copy On Write），在修改操作中，会复制一份原来的数组，在新的数组上修改，不会直接修改原来的数组，所以对读操作没有影响。

CopyOnWriteArrayList内部使用了ReentrantLock保证修改操作线程安全。

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8673264195747942595L; final transient ReentrantLock lock = new ReentrantLock(); // volatile修饰，保证setArray(arr)方法执行后，array的修改对其他线程立即可见 private transient volatile Object[] array; final Object[] getArray() { return array; } final void setArray(Object[] a) { array = a; } public CopyOnWriteArrayList() { // 无参构造方法，初始化一个空数组 setArray(new Object[0]); } public CopyOnWriteArrayList(Collection<? extends E> c) { Object[] elements; // 如果参数是CopyOnWriteArrayList类型的，直接把当前CopyOnWriteArrayList对象的array设置成c.getArray() if (c.getClass() == CopyOnWriteArrayList.class) { elements = ((CopyOnWriteArrayList<?>)c).getArray(); } else { // 不同类型，调用list.toArray()把集合转成数组 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)); } public int size() { return getArray().length; } public boolean isEmpty() { return size() == 0; } private static boolean eq(Object o1, Object o2) { return (o1 == null) ? o2 == null : o1.equals(o2); } }

上面是一些基础的方法，接下来介绍CopyOnWriteArrayList的其他方法：

静态方法

如果你第一次看CopyOnWriteArrayList的源码，你可能会和我一样觉得这两个方法不应该出现在这里，这就是数组相关的方法，接着往下看，你会发现，这两个方法就是提供后面的方法内部调用的。

indexOf

静态方法，获取指定元素在数组中下标从index到fence中有没有出现过，如果出现过，返回第一次出现的位置，如果找不到就返回-1。

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; }

 lastIndexOf

静态方法，获取指定元素在数组中最后一次出现的位置，如果找不到就返回-1。

从数组的末尾元素往前遍历，找到的第一个匹配的元素的下标就是所需的结果。

private static int lastIndexOf(Object o, Object[] elements, int index) { if (o == null) { for (int i = index; i >= 0; i--) if (elements[i] == null) return i; } else { for (int i = index; i >= 0; i--) if (o.equals(elements[i])) return i; } return -1; }

实例方法 contains

判断当前list中是否包含指定的元素，通过调用静态方法indexOf()，根据是否返回-1来判断，返回-1则表示数组中没有匹配到该元素，所以就是返回false，否则返回true。

public boolean contains(Object o) { Object[] elements = getArray(); return indexOf(o, elements, 0, elements.length) >= 0; }

indexOf

获取指定元素在当前list中第一次出现的位置

public int indexOf(Object o) { Object[] elements = getArray(); return indexOf(o, elements, 0, elements.length); }

获取指定元素在当前list中从下标index开始，第一次出现的位置

public int indexOf(E e, int index) { Object[] elements = getArray(); return indexOf(e, elements, index, elements.length); }

lastIndexOf

获取指定元素在当前list中最后一次出现的位置，如果找不到就返回-1。

public int lastIndexOf(Object o) { Object[] elements = getArray(); return lastIndexOf(o, elements, elements.length - 1); }

 获取指定元素在当前list中最后一次出现的位置，从数组下标index位置开始匹配

public int lastIndexOf(E e, int index) { Object[] elements = getArray(); return lastIndexOf(e, elements, index); }

toArray()

返回当前list内部的数组的副本

public Object[] toArray() { Object[] elements = getArray(); return Arrays.copyOf(elements, elements.length); }

返回当前list内部的数组的副本，并将其转换为指定类型

public <T> T[] toArray(T a[]) { Object[] elements = getArray(); int len = elements.length; if (a.length < len) return (T[]) Arrays.copyOf(elements, len, a.getClass()); else { System.arraycopy(elements, 0, a, 0, len); // 这句代码似乎有点多余 if (a.length > len) a[len] = null; return a; } }

get

私有的方法，获取数组指定下标的元素，并将其转换为和list元素类型相同的数据类型。

private E get(Object[] a, int index) { return (E) a[index]; }

获取数组指定下标的元素，并将其转换为和list元素类型相同的数据类型。

public E get(int index) { return get(getArray(), index); }

set

修改list指定位置的元素，通过ReentrantLock保证写操作的线程安全

public E set(int index, E element) { final ReentrantLock lock = this.lock; lock.lock(); try { // 得到当前list内部的数组 Object[] elements = getArray(); // 获取指定下标的值 E oldValue = get(elements, index); // 当旧值和新值不相等时，修改副本 if (oldValue != element) { int len = elements.length; // 得到数组的副本 Object[] newElements = Arrays.copyOf(elements, len); newElements[index] = element; setArray(newElements); } else { setArray(elements); } return oldValue; } finally { lock.unlock(); } }

add

往list里添加元素，通过ReentrantLock保证写操作的线程安全

和set方法一样，对原数组的副本进行操作，先扩容，然后设置数组最后一个下标的值，修改完成后，把副本指向原来的数组。

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

往list指定下标处添加元素

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; // 插入位置和数组的长度相等，则等同于add(E element ) 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(); } }

remove

获取并删除指定位置的元素

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; // 如果指定下标+1=原数组长度，则是删除最后一个元素，只需要进行数组缩容 if (numMoved == 0) setArray(Arrays.copyOf(elements, len - 1)); else { // 创建一个原数组长度-1的数组，把除了index下标的元素复制到新数组 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(); } }

从list中删除指定元素

public boolean remove(Object o) { Object[] snapshot = getArray(); int index = indexOf(o, snapshot, 0, snapshot.length); return (index < 0) ? false : remove(o, snapshot, index); }

 私有的方法，删除list中指定的元素

private boolean remove(Object o, Object[] snapshot, int index) { final ReentrantLock lock = this.lock; lock.lock(); try { // 得到原数组 Object[] current = getArray(); int len = current.length; // 如果指定的数组和原数组不相等 if (snapshot != current) findIndex: { // 得到index和原数组长度之间的最小值 int prefix = Math.min(index, len); for (int i = 0; i < prefix; i++) { // current[i] != snapshot[i]说明array被修改过 // array被修改过,并且修改之后的元素和指定的元素相等 if (current[i] != snapshot[i] && eq(o, current[i])) { index = i; break findIndex; } } // 下标越界 if (index >= len) return false; // 再次检查原数组是否被修改过 if (current[index] == o) break findIndex; // 找不到指定元素，直接返回false index = indexOf(o, current, index, len); if (index < 0) return false; } // 分段复制到新数组，最后替换原来的array Object[] newElements = new Object[len - 1]; System.arraycopy(current, 0, newElements, 0, index); System.arraycopy(current, index + 1, newElements, index, len - index - 1); setArray(newElements); return true; } finally { lock.unlock(); } }

removeRange

从list中删除指定下标范围 [fromIndex, toIndex] 的元素

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; // 删除的是数组后半段 if (numMoved == 0) setArray(Arrays.copyOf(elements, newlen)); else { // 删除数组中间的部分，还是分两步复制到新数组中，最后修改array的引用 Object[] newElements = new Object[newlen]; System.arraycopy(elements, 0, newElements, 0, fromIndex); System.arraycopy(elements, toIndex, newElements, fromIndex, numMoved); setArray(newElements); } } finally { lock.unlock(); } }

addIfAbsent

如果指定元素不存在则添加

public boolean addIfAbsent(E e) { Object[] snapshot = getArray(); return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : addIfAbsent(e, snapshot); } private boolean addIfAbsent(E e, Object[] snapshot) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] current = getArray(); int len = current.length; if (snapshot != current) { int common = Math.min(snapshot.length, len); for (int i = 0; i < common; i++) { // 原数组array被修改过，并且修改之后的数组中存在指定元素 if (current[i] != snapshot[i] && eq(e, current[i])) { return false; } } // 元素已经存在 if (indexOf(e, current, common, len) >= 0) { return false; } } // 数组扩容，把当前元素设置到数组末尾 Object[] newElements = Arrays.copyOf(current, len + 1); newElements[len] = e; setArray(newElements); return true; } finally { lock.unlock(); } }

containsAll

判断当前list是否包含集合c内所有元素

public boolean containsAll(Collection<?> c) { Object[] elements = getArray(); int len = elements.length; for (Object e : c) { if (indexOf(e, elements, 0, len) < 0) { return false; } } return true; }

public boolean removeAll(Collection<?> c) { if (c == null) throw new NullPointerException(); final ReentrantLock lock = this.lock; lock.lock(); try { // 得到原数组及长度 Object[] elements = getArray(); int len = elements.length; if (len != 0) { // 创建一个变量保存删除元素后数组的长度 int newlen = 0; // 创建一个临时数组，指定初始长度和原元素的长度相同 Object[] temp = new Object[len]; // 遍历原数组， for (int i = 0; i < len; ++i) { Object element = elements[i]; // 如果元素没有包含在指定集合c中，把元素添加到临时数组，同时结果数组长度+1 if (!c.contains(element)) temp[newlen++] = element; } // 如果有匹配的元素，对临时数组缩容 if (newlen != len) { setArray(Arrays.copyOf(temp, newlen)); return true; } } return false; } finally { lock.unlock(); } }

addAllAbsent

往list中添加原数组和指定集合元素的差集，也就是集合c里的array里没有的元素。

public int addAllAbsent(Collection<? extends E> c) { // 指定集合转为数组 Object[] cs = c.toArray(); if (cs.length == 0) return 0; final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; // 保存最后添加成功的元素个数 int added = 0; // 遍历指定的集合c for (int i = 0; i < cs.length; ++i) { Object e = cs[i]; // 原数组中没有的元素放到cs中 // indexOf(e, cs, 0, added) < 0限制了不会往cs中添加重复的元素 if (indexOf(e, elements, 0, len) < 0 && indexOf(e, cs, 0, added) < 0) cs[added ++] = e; } /* 最后，如果有符合条件的元素，则从cs中复制元素 因为上面的操作中，把符合条件的元素放在了数组cs的0~added位置 */ if (added > 0) { Object[] newElements = Arrays.copyOf(elements, len + added); System.arraycopy(cs, 0, newElements, len, added); // 替换旧数组 setArray(newElements); } return added; } finally { lock.unlock(); } }

clear

清空集合，这个功能没什么好说的，直接设置array为空数组

public void clear() { final ReentrantLock lock = this.lock; lock.lock(); try { setArray(new Object[0]); } finally { lock.unlock(); } }

addAll

把集合c中的元素添加到当前list中

public boolean addAll(Collection<? extends E> c) { // 把集合c转为数组 Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ? ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray(); if (cs.length == 0) return false; final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; // 原数组为空数组，且指定集合c的元素类型为Object，直接把集合c转换得到的的数组指向array if (len == 0 && cs.getClass() == Object[].class) { setArray(cs); } else { // 先对原数组扩容，扩容后的长度=原数组长度 + 集合c的元素个数 Object[] newElements = Arrays.copyOf(elements, len + cs.length); // 从集合c的数组中复制元素 System.arraycopy(cs, 0, newElements, len, cs.length); // 修改array的引用 setArray(newElements); } return true; } finally { lock.unlock(); } }

把集合c中的元素添加到当前list中，新元素会替换原来的list中数组在[index, index + c.size()]的元素

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); if (cs.length == 0) return false; int numMoved = len - index; Object[] newElements; // index和原数组长度相等，则直接对数组进行扩容 if (numMoved == 0) newElements = Arrays.copyOf(elements, len + cs.length); else { // 分段复制，把原数组首尾的元素复制到数组newElements中 newElements = new Object[len + cs.length]; System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index, newElements, index + cs.length, numMoved); } // 把指定集合的元素复制到newElements中间[index, index + cs.length] System.arraycopy(cs, 0, newElements, index, cs.length); setArray(newElements); return true; } finally { lock.unlock(); } }

forEach

遍历集合，这个方法大家再熟悉不过了吧，Java集合的4种遍历方式之一（for foreach Iterater forEach方法）。

public void forEach(Consumer<? super E> action) { if (action == null) throw new NullPointerException(); Object[] elements = getArray(); int len = elements.length; for (int i = 0; i < len; ++i) { E e = (E) elements[i]; action.accept(e); } }

removeIf

条件删除集合中的元素，使用该方法可以防止快速失败，也是集合常用的方法，就不介绍了。

public boolean removeIf(Predicate<? super E> filter) { if (filter == null) throw new NullPointerException(); final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length； if (len != 0) { int newlen = 0; Object[] temp = new Object[len]; // 重点：把不符合条件的元素保存在临时数组temp中 for (int i = 0; i < len; ++i) { E e = (E) elements[i]; if (!filter.test(e)) temp[newlen++] = e; } // 新长度和原数组长度不相等，也就是删除了元素才进行数组缩容 if (newlen != len) { setArray(Arrays.copyOf(temp, newlen)); return true; } } return false; } finally { lock.unlock(); } }

replaceAll

替换全部元素，其实就是对集合进行批量操作

public void replaceAll(UnaryOperator<E> operator) { if (operator == null) throw new NullPointerException(); final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len); for (int i = 0; i < len; ++i) { E e = (E) elements[i]; newElements[i] = operator.apply(e); } setArray(newElements); } finally { lock.unlock(); } }

UnaryOperator是个函数式接口，继承了Function接口，表示一次简单的操作，在apply()方法中，可以对传入的参数做任何处理。

package java.util.function; @FunctionalInterface public interface UnaryOperator<T> extends Function<T, T> { static <T> UnaryOperator<T> identity() { return t -> t; } }

可以看到，UnaryOperator也没有实现Function的apply()方法，所以实例化的时候需要实现UnaryOperator继承自Function接口的apply()方法。

package java.util.function; import java.util.Objects; @FunctionalInterface public interface Function<T, R> { R apply(T t); default <V> Function<V, R> compose(Function<? super V, ? extends T> before) { Objects.requireNonNull(before); return (V v) -> apply(before.apply(v)); } default <V> Function<T, V> andThen(Function<? super R, ? extends V> after) { Objects.requireNonNull(after); return (T t) -> after.apply(apply(t)); } static <T> Function<T, T> identity() { return t -> t; } }

这个接口可以比较抽象，通过一个案例用一下就知道了。下面的代码在集合所有元素后面拼接了字符串"~"。

package juc; import java.util.concurrent.CopyOnWriteArrayList; import java.util.function.UnaryOperator; /** * @author heyunlin * @version 1.0 */ public class CopyOnWriteArrayListExample { public static void main(String[] args) { CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(); list.add("abc"); list.add("123"); System.out.println(list); list.replaceAll(new UnaryOperator<String>() { @Override public String apply(String s) { return s.concat("~"); } }); System.out.println(list); } }

sort

在集合的工具类Collections里就有一个排序的静态方法sort()，通过传入的比较器对象自定义排序规则，返回负数代表降序，返回正数代表升序

public void sort(Comparator<? super E> c) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); Object[] newElements = Arrays.copyOf(elements, elements.length); E[] es = (E[]) newElements; Arrays.sort(es, c); setArray(newElements); } finally { lock.unlock(); } }

好了，关于CopyOnWriteArrayList方法的详细介绍就到这里了，看完不要忘了点赞+收藏哦~