CopyOnWriteArrayList

一、CopyOnWriteArrayList 出现之前

• ArrayList 和 LinkedList 作为 List 的数组和链表的实现
• 线程安全的 Vector 和 Collections.synchronizedList() 可以使用
• Vector 就是在方法上加 synchronized ，性能很差
• 这几种 List 在迭代期间不允许编辑
• 如果在迭代期间进行添加元素或删除元素等操作 则会抛出 ConcurrentModificationException 异常

二、适用场景

• 读操作可以尽可能地快，而写即使慢一些也没关系
  在很多应用场景中，读操作可能会远远多于写操作
• 读多写少
  黑名单是最典型的场景 不能被搜索的关键字会被放在一个黑名单当中 当用户搜索时，会检查当前关键字在不在黑名单当中 如果在，则提示不能搜索

三、读写规则

• CopyOnWriteArrayList 读取是完全不用加锁的
• 可以在写入的同时进行读取

四、特点

• 当容器需要被修改的时候，不直接修改当前容器
  1. 先将当前容器进行 Copy，复制出一个新的容器
  2. 然后修改新的容器
  3. 完成修改之后，再将原容器的引用指向新的容器
• 优点
  1. CopyOnWriteArrayList 利用“不变性”原理保证旧容器线程安全
  2. 可以对 CopyOnWrite 容器进行并发的读，而不需要加锁
  3. CopyOnWrite 容器是一种读写分离的思想体现
• 迭代期间允许修改集合内容
  1. ArrayList 迭代期间不允许修改集合内容，在 ArrayList 源码里的 ListItr 的 next 方法中有一个 checkForComodification 方法

  final void checkForComodification() { 
      if (modCount != expectedModCount) 
          throw new ConcurrentModificationException(); 
  }
  

  迭代器创建之时，将当前的modCount赋值给expectedModCount，之后进行集合修改的时候都会修改modCount的值，但是expectedModCount并不会修改，所以一定会抛出ConcurrentModificationException异常。
  2. 要想能在迭代的时候不发生异常，就用迭代器的 remove
     • list.remove() 没有对 expectedModCount 重新赋值
     • iterator.remove() 对 expectedModCount 重新赋值
  3. CopyOnWriteArrayList 在修改的时候不会发生ConcurrentModificationException，它会复制一个新的数组进行修改操作，而读取的依旧是之前的老数组
  4. CopyOnWriteArrayList 的迭代器一旦被建立之后，如果往之前的 CopyOnWriteArrayList 对象中去新增元素，在迭代器中既不会显示出元素的变更情况 同时也不会报错
• 缺点
  1. 内存占用问题
     CopyOnWrite 的写时复制机制，在进行写操作的时候内存里会同时驻扎两个对象的内存，这一点会占用额外的内存
  2. 在元素较多或者复杂的情况下，复制的开销很大
     复制过程不仅会占用双倍内存，还需要消耗 CPU 等资源，会降低整体性能
  3. 数据一致性问题
     由于 CopyOnWrite 容器的修改对于其他线程来说 并不是实时能看到的，只有在修改完之后才能体现出来

五、源码分析

• 数据结构

/** 可重入锁对象 */ 
final transient ReentrantLock lock = new ReentrantLock(); 
/** CopyOnWriteArrayList底层由数组实现，volatile修饰，保证数组的可见性 */ 
private transient volatile Object[] array; 
/**
 * 得到数组 
 */ 
final Object[] getArray() { 
    return array; 
}
/**
 * 设置数组 
 */ 
final void setArray(Object[] a) { 
    array = a; 
}
/**
 * 初始化CopyOnWriteArrayList相当于初始化数组 
 */ 
public CopyOnWriteArrayList() { 
    setArray(new Object[0]); 
}

• add方法

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; 
        // 将volatile Object[] array 的指向替换成新数组 
        setArray(newElements); 
        return true; 
    } finally { 
        lock.unlock(); 
    } 
}

• 读操作

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