前言
CopyOnWrite，写复制容器，一种延时懒惰策略。
JDK5开始提供了两个写复制容器CopyOnWriteArrayList和CopyOnWriteArraySet。
CopyOnWrite即写复制容器。体现读写分离的思想，即add或者set元素的时候，copy一个容器用于写，以前的容器仍然可以读取，当添加完成元素之后，将复制的容器作为新的容器，废弃以前的容器GC掉。
1. CopyOnWriteArrayList源码解析
1.1 总体概览
/** @since 1.5 * @author Doug Lea * @param <E> the type of elements held in this collection */ public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8673264195747942595L; /** The lock protecting all mutators */ final transient ReentrantLock lock = new ReentrantLock(); /** The array, accessed only via getArray/setArray. */ private transient volatile Object[] array;可以看出CopyOnWriteArrayList其实就是Object数组array
使用了ReentrantLock锁机制
使用transient修饰，不能序列化 ，此处必定使用自定义序列化机制
/** * Saves this list to a stream (that is, serializes it). * * @param s the stream * @throws java.io.IOException if an I/O error occurs * @serialData The length of the array backing the list is emitted * (int), followed by all of its elements (each an Object) * in the proper order. */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { s.defaultWriteObject(); Object[] elements = getArray(); // Write out array length s.writeInt(elements.length); // Write out all elements in the proper order. for (Object element : elements) s.writeObject(element); } /** * Reconstitutes this list from a stream (that is, deserializes it). * @param s the stream * @throws ClassNotFoundException if the class of a serialized object * could not be found * @throws java.io.IOException if an I/O error occurs */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { s.defaultReadObject(); // bind to new lock resetLock(); // Read in array length and allocate array int len = s.readInt(); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, len); Object[] elements = new Object[len]; // Read in all elements in the proper order. for (int i = 0; i < len; i++) elements[i] = s.readObject(); setArray(elements); }writeObject跟默认序列化没有区别
但是readObject有句代码，重新设定了锁 resetLock();
UNSAFE原子操作，重新赋值lock常量为新的new ReentrantLock()。即序列化反序列化后使用新的锁，实现深度克隆
// Support for resetting lock while deserializing private void resetLock() { UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock()); } private static final sun.misc.Unsafe UNSAFE; private static final long lockOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); Class<?> k = CopyOnWriteArrayList.class; lockOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("lock")); } catch (Exception e) { throw new Error(e); } }1.2 构造函数和核心方法add和get方法
1.2.1 构造函数
public CopyOnWriteArrayList(Collection<? extends E> c) { Object[] elements; 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); }很简单，判断类型，直接使用或者数组的拷贝
1.2.2 add和get方法
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */ public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock(); try { //获取数组 Object[] elements = getArray(); int len = elements.length; //copy 得到新数组，len+1 Object[] newElements = Arrays.copyOf(elements, len + 1); //新数组add newElements[len] = e; //新数组替换旧数组，通过赋值的模式 setArray(newElements); return true; } finally { lock.unlock(); } } /** * {@inheritDoc} * * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { return get(getArray(), index); }使用get方法获取值，在写完后立即生效，使用迭代器，仍然迭代原来的数组值，因为迭代器缓存了原来时间点的数组
iterator()方法
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; /** Index of element to be returned by subsequent call to next. */ //迭代游标，从0开始 private int cursor; private COWIterator(Object[] elements, int initialCursor) { cursor = initialCursor; snapshot = elements; } public boolean hasNext() { return cursor < snapshot.length; } public boolean hasPrevious() { return cursor > 0; } @SuppressWarnings("unchecked") public E next() { if (! hasNext()) throw new NoSuchElementException(); return (E) snapshot[cursor++]; }2. CopyOnWriteArraySet
2.1 总体概览
/** @see CopyOnWriteArrayList * @since 1.5 * @author Doug Lea * @param <E> the type of elements held in this collection */ public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable { private static final long serialVersionUID = 5457747651344034263L; private final CopyOnWriteArrayList<E> al; /** * Creates an empty set. */ public CopyOnWriteArraySet() { al = new CopyOnWriteArrayList<E>(); }直接使用CopyOnWriteArrayList，那么Set是如何实现不会存在重复元素的呢？看构造函数和add方法
2.2 构造函数
public CopyOnWriteArraySet(Collection<? extends E> c) { if (c.getClass() == CopyOnWriteArraySet.class) { @SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc = (CopyOnWriteArraySet<E>)c; al = new CopyOnWriteArrayList<E>(cc.al); } else { al = new CopyOnWriteArrayList<E>(); al.addAllAbsent(c); } }去重addAll
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; } /** * Appends all of the elements in the specified collection that * are not already contained in this list, to the end of * this list, in the order that they are returned by the * specified collection's iterator. * * @param c collection containing elements to be added to this list * @return the number of elements added * @throws NullPointerException if the specified collection is null * @see #addIfAbsent(Object) */ 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; // uniquify and compact elements in cs for (int i = 0; i < cs.length; ++i) { Object e = cs[i]; //剔除重复元素 if (indexOf(e, elements, 0, len) < 0 && indexOf(e, cs, 0, added) < 0) cs[added++] = e; } if (added > 0) { //扩容 Object[] newElements = Arrays.copyOf(elements, len + added); //数据复制 System.arraycopy(cs, 0, newElements, len, added); setArray(newElements); } return added; } finally { lock.unlock(); } }2.3 add方法
/** @see CopyOnWriteArrayList * @since 1.5 * @author Doug Lea * @param <E> the type of elements held in this collection */ public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable { private static final long serialVersionUID = 5457747651344034263L; private final CopyOnWriteArrayList<E> al; public boolean add(E e) { return al.addIfAbsent(e); }注意：没有get方法
/** * Appends the element, if not present. * * @param e element to be added to this list, if absent * @return {@code true} if the element was added */ public boolean addIfAbsent(E e) { Object[] snapshot = getArray(); //indexOf检查元素是否存在 return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : addIfAbsent(e, snapshot); } /** * A version of addIfAbsent using the strong hint that given * recent snapshot does not contain e. */ private boolean addIfAbsent(E e, Object[] snapshot) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] current = getArray(); int len = current.length; //判断snapshot缓存是否修改 if (snapshot != current) { // Optimize for lost race to another addXXX operation int common = Math.min(snapshot.length, len); for (int i = 0; i < common; i++) //检查是否多线程修改 if (current[i] != snapshot[i] && eq(e, current[i])) return false; //元素已经存在，set不能重复 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(); } }
可以看出写操作是加锁的，写是互斥的，读没有加锁，可以并发读取。
这种思想非常重要，在写操作比较少的时候，比如充当缓存的作用。
缺陷：
1. 占用内存空间
在写操作的时候复制容器就多占用一份内存空间，占用的堆内存，会在写操作前分配初始化内存，写完后GC回收，可能会造成频繁的Minor GC、Full GC。
2. 一致性问题
延时懒惰策略，只能保证最终一致性。
