目录
1. 是什么
这个list借鉴的是读写分离的思想（弱一致性）
- 读的时候可以并发读，不加锁；
- 写的时候需要加锁，复制一份原有数据进行修改，改完后写回list
2. 如何使用
public class CopyOnWriteArrayListTest { public static void main(String[] args) { CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(); list.add("a"); list.add("b"); list.add("c"); list.remove("a"); System.out.println(list.contains("a"));//false System.out.println(list.get(0));//b list.set(0, "d"); System.out.println(list);//[d, c] System.out.println(Thread.currentThread().getName() + "读取list:" + list);//[d, c] new Thread(()->{ System.out.println(Thread.currentThread().getName() + "读取list:" + list);//[d, c] try { TimeUnit.SECONDS.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println(Thread.currentThread().getName() + "再次读取list:" + list);//[c] }).start(); new Thread(()->{ System.out.println(Thread.currentThread().getName() + "读取list:" + list);//[d, c] try { TimeUnit.SECONDS.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println(Thread.currentThread().getName() + "再次读取list:" + list);//[c] }).start(); try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { e.printStackTrace(); } list.remove(0); System.out.println(Thread.currentThread().getName() + "读取修改后的list:" + list);//[c] } } 3. 原理
3.1. 构造方法
public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { //用于写时加锁 final transient ReentrantLock lock = new ReentrantLock(); //底层通过object数组实现, 通过 getArray/setArray访问 //volatile修饰保证多线程能及时看到最新结果 private transient volatile Object[] array; public CopyOnWriteArrayList() { //初始化数组长度为0 setArray(new Object[0]); } //get set都没做什么同步措施 final void setArray(Object[] a) { array = a; } final Object[] getArray() { return array; } } -
可以看到底层是通过object数组实现,
- 通过 getArray/setArray访问，这两个方法都没做什么同步措施
- 使用volatile修饰保证多线程能及时看到最新结果
-
并且有一个ReentrantLock，保证写时加锁
3.2. add方法
public boolean add(E e) { //多个线程同时调用add方法保证只有一个能进入 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行：加锁。写的操作必须加锁
- 7-12行：copy原数组，扩容并修改
- 14行：写回原数组
下面具体说明：
3.2.1. 先加锁
//多个线程同时调用add方法保证只有一个能进入 final ReentrantLock lock = this.lock; lock.lock(); //。。。。。 } finally { lock.unlock(); } 3.2.2. 复制数组并在这份数组上操作
//获取原数组 Object[] elements = getArray(); int len = elements.length; //复制并扩容数组 Object[] newElements = Arrays.copyOf(elements, len + 1); //赋值 newElements[len] = e; 3.2.3. 将复制的数组set回属性
//写回数组 //array = a; //由于array是volatile修饰的，一旦改变之后其他线程会清空工作内存中的array，这样读取新值 setArray(newElements); 3.3. remove方法
- remove
public boolean remove(Object o) { //获取原数组 Object[] snapshot = getArray(); //从原数组的0-最后一个位置查找o是否存在并获取其下标 int index = indexOf(o, snapshot, 0, snapshot.length); //存在则删除 return (index < 0) ? false : remove(o, snapshot, index); } - 3-5行：找到数组中值o的位置index
- 7行：加锁删除数组中的index位置
下面具体说明：
3.3.1. 找到要删除元素的位置
- indexOf
private static int indexOf(Object o, Object[] elements, int index, int fence) { //要找的值为null if (o == null) { for (int i = index; i < fence; i++) if (elements[i] == null) return i; //不为null } else { for (int i = index; i < fence; i++) if (o.equals(elements[i])) return i; } return -1; } 这个方法没有加锁，只是把判断值是否为null分别进行处理
3.3.2. 加锁并把除了被删除之外的其他元素复制到新数组中，set回属性中
- remove
//再snapshot数组删除下标为index且值为o的元素 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: { //遍历原数组和改变后的数组0-index位置是否相同，相同则可以删除 //有一个位置不相同 且 改变后的数组这个位置xx的元素与要删除的元素相同，那么重新从0-xx比较 int prefix = Math.min(index, len); for (int i = 0; i < prefix; i++) { if (current[i] != snapshot[i] && eq(o, current[i])) { index = i; break findIndex; } } //改变后的数组长度比index短了，那么不可能删除了，返回false if (index >= len) return false; //改变后的数组index位置仍然是o if (current[index] == o) //退出findIndex这段代码，即执行34行 break findIndex; //在改变后的数组中index-len位置重新寻找值为o的元素 index = indexOf(o, current, index, len); //没找到，删除不了返回false if (index < 0) return false; } //创建原数组长度-1的新数组 Object[] newElements = new Object[len - 1]; //复制index左边的元素到新数组 System.arraycopy(current, 0, newElements, 0, index); //复制index右边的元素到新数组（等于删除了index位置的元素） System.arraycopy(current, index + 1, newElements, index, len - index - 1); //修改为新数组 setArray(newElements); return true; } finally { lock.unlock(); } } 3.4. get(index)方法
public E get(int index) { return get(getArray(), index); } get方法属于读取操作，所以不需要加锁，直接原数组上通过下标获取
3.4.1. 没加锁，通过数组[index]获取
- get
private E get(Object[] a, int index) { return (E) a[index]; } 3.5. contains
public boolean contains(Object o) { //获取原数组 Object[] elements = getArray(); //再查找下标 return indexOf(o, elements, 0, elements.length) >= 0; } - 3行：contains方法属于读方法，所以没加锁
- 5行：直接遍历数组查找
3.5.1. 不加锁遍历数据查询
- indexOf
private static int indexOf(Object o, Object[] elements, int index, int fence) { //要找的值为null if (o == null) { for (int i = index; i < fence; i++) if (elements[i] == null) return i; //要找的值不为null } else { for (int i = index; i < fence; i++) if (o.equals(elements[i])) return i; } return -1; } 3.6. set
//修改index位置的值为element public E set(int index, E element) { final ReentrantLock lock = this.lock; lock.lock(); try { //获取原数组 Object[] elements = getArray(); //获取原数组index位置的值 E oldValue = get(elements, index); //index位置不是element if (oldValue != element) { //复制原数组到新数组，修改index位置的值，set回array int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len); newElements[index] = element; setArray(newElements); //index位置已经是element了，那么直接set回array（保证volatile语义） } else { // Not quite a no-op; ensures volatile write semantics setArray(elements); } return oldValue; } finally { lock.unlock(); } } - 4行：set方法属于写方法，所以需要先加锁
- 7-9行：通过下标查找值
- 12-18行：第2步查找到的值跟现在数组中的值不同，说明有改变。那么copy原数组、修改、写回原数组
- 19-22 行：第2步查找到的值跟现在数组中的值相同，说明没有改变。虽然不做什么处理也行，但为了保证volatile语义，还是set回数组
下面详细说明：
3.6.1. 先加锁
final ReentrantLock lock = this.lock; lock.lock(); try { } finally { lock.unlock(); } 3.6.2. 从原数组中获取index位置的值
//获取原数组 Object[] elements = getArray(); //获取原数组index位置的值 E oldValue = get(elements, index); 3.6.3. 如果index位置不相等，那么复制新数组、修改并set回属性
//index位置不是element if (oldValue != element) { //复制原数组到新数组，修改index位置的值，set回array int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len); newElements[index] = element; setArray(newElements); } 3.6.4. 即使相等也要set回去保证volatile语义
//index位置已经是element了，那么直接set回array（保证volatile语义） else { // Not quite a no-op; ensures volatile write semantics setArray(elements); } 4. 总结
- 适合读多写少的场景
- 当调用add方法的时候加锁修改，内存中有两份数组，一份原始的，另一份是当前线程修改的数组
- 当调用get方法时不加锁，获取的是原有的数组
