Java concurrency集合之 CopyOnWriteArrayList_动力节点Java学院整理

copyonwritearraylist介绍

它相当于线程安全的arraylist。和arraylist一样，它是个可变数组；但是和arraylist不同的时，它具有以下特性：

1. 它最适合于具有以下特征的应用程序：list 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。

2. 它是线程安全的。

3. 因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove() 等等）的开销很大。

4. 迭代器支持hasnext(), next()等不可变操作，但不支持可变 remove()等操作。

5. 使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。 

copyonwritearraylist原理和数据结构

copyonwritearraylist的数据结构，如下图所示：

说明：

1. copyonwritearraylist实现了list接口，因此它是一个队列。

2. copyonwritearraylist包含了成员lock。每一个copyonwritearraylist都和一个互斥锁lock绑定，通过lock，实现了对copyonwritearraylist的互斥访问。

3. copyonwritearraylist包含了成员array数组，这说明copyonwritearraylist本质上通过数组实现的。

下面从“动态数组”和“线程安全”两个方面进一步对copyonwritearraylist的原理进行说明。

1. copyonwritearraylist的“动态数组”机制 -- 它内部有个“volatile数组”(array)来保持数据。在“添加/修改/删除”数据时，都会新建一个数组，并将更新后的数据拷贝到新建的数组中，最后再将该数组赋值给“volatile数组”。这就是它叫做copyonwritearraylist的原因！copyonwritearraylist就是通过这种方式实现的动态数组；不过正由于它在“添加/修改/删除”数据时，都会新建数组，所以涉及到修改数据的操作，copyonwritearraylist效率很
低；但是单单只是进行遍历查找的话，效率比较高。

2. copyonwritearraylist的“线程安全”机制 -- 是通过volatile和互斥锁来实现的。(01) copyonwritearraylist是通过“volatile数组”来保存数据的。一个线程读取volatile数组时，总能看到其它线程对该volatile变量最后的写入；就这样，通过volatile提供了“读取到的数据总是最新的”这个机制的

保证。(02) copyonwritearraylist通过互斥锁来保护数据。在“添加/修改/删除”数据时，会先“获取互斥锁”，再修改完毕之后，先将数据更新到“volatile数组”中，然后再“释放互斥锁”；这样，就达到了保护数据的目的。 

copyonwritearraylist函数列表

// 创建一个空列表。
copyonwritearraylist()
// 创建一个按 collection 的迭代器返回元素的顺序包含指定 collection 元素的列表。
copyonwritearraylist(collection<? extends e> c)
// copyonwritearraylist(e[] tocopyin)

创建一个保存给定数组的副本的列表。

// 将指定元素添加到此列表的尾部。
boolean add(e e)
// 在此列表的指定位置上插入指定元素。
void add(int index, e element)
// 按照指定 collection 的迭代器返回元素的顺序，将指定 collection 中的所有元素添加此列表的尾部。
boolean addall(collection<? extends e> c)
// 从指定位置开始，将指定 collection 的所有元素插入此列表。
boolean addall(int index, collection<? extends e> c)
// 按照指定 collection 的迭代器返回元素的顺序，将指定 collection 中尚未包含在此列表中的所有元素添加列表的尾部。
int addallabsent(collection<? extends e> c)
// 添加元素（如果不存在）。
boolean addifabsent(e e)
// 从此列表移除所有元素。
void clear()
// 返回此列表的浅表副本。
object clone()
// 如果此列表包含指定的元素，则返回 true。
boolean contains(object o)
// 如果此列表包含指定 collection 的所有元素，则返回 true。
boolean containsall(collection<?> c)
// 比较指定对象与此列表的相等性。
boolean equals(object o)
// 返回列表中指定位置的元素。
e get(int index)
// 返回此列表的哈希码值。
int hashcode()
// 返回第一次出现的指定元素在此列表中的索引，从 index 开始向前搜索，如果没有找到该元素，则返回 -1。
int indexof(e e, int index)
// 返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1。
int indexof(object o)
// 如果此列表不包含任何元素，则返回 true。
boolean isempty()
// 返回以恰当顺序在此列表元素上进行迭代的迭代器。
iterator<e> iterator()
// 返回最后一次出现的指定元素在此列表中的索引，从 index 开始向后搜索，如果没有找到该元素，则返回 -1。
int lastindexof(e e, int index)
// 返回此列表中最后出现的指定元素的索引；如果列表不包含此元素，则返回 -1。
int lastindexof(object o)
// 返回此列表元素的列表迭代器（按适当顺序）。
listiterator<e> listiterator()
// 返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始。
listiterator<e> listiterator(int index)
// 移除此列表指定位置上的元素。
e remove(int index)
// 从此列表移除第一次出现的指定元素（如果存在）。
boolean remove(object o)
// 从此列表移除所有包含在指定 collection 中的元素。
boolean removeall(collection<?> c)
// 只保留此列表中包含在指定 collection 中的元素。
boolean retainall(collection<?> c)
// 用指定的元素替代此列表指定位置上的元素。
e set(int index, e element)
// 返回此列表中的元素数。
int size()
// 返回此列表中 fromindex（包括）和 toindex（不包括）之间部分的视图。
list<e> sublist(int fromindex, int toindex)
// 返回一个按恰当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组。
object[] toarray()
// 返回以恰当顺序（从第一个元素到最后一个元素）包含列表所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。
<t> t[] toarray(t[] a)
// 返回此列表的字符串表示形式。
string tostring() 

下面我们从“创建，添加，删除，获取，遍历”这5个方面去分析copyonwritearraylist的原理。

1. 创建

copyonwritearraylist共3个构造函数。它们的源码如下：

public copyonwritearraylist() {
 setarray(new object[0]);
}
public copyonwritearraylist(collection<? extends e> c) {
 object[] 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));
}
说明：这3个构造函数都调用了setarray()，setarray()的源码如下：
private volatile transient object[] array;
final object[] getarray() {
 return array;
}
final void setarray(object[] a) {
 array = a;
}

说明：setarray()的作用是给array赋值；其中，array是volatile transient object[]类型，即array是“volatile数组”。

关于volatile关键字，我们知道“volatile能让变量变得可见”，即对一个volatile变量的读，总是能看到（任意线程）对这个volatile变量最后的写入。正在由于这种特性，每次更新了“volatile数组”之后，其它线程都能看到对它所做的更新。

关于transient关键字，它是在序列化中才起作用，transient变量不会被自动序列化。transient不是本文关注的重点，了解即可。

2. 添加

以add(e e)为例，来对“copyonwritearraylist的添加操作”进行说明。下面是add(e e)的代码：

public boolean add(e e) {
 final reentrantlock lock = this.lock;
 // 获取“锁”
 lock.lock();
 try {
  // 获取原始”volatile数组“中的数据和数据长度。
  object[] elements = getarray();
  int len = elements.length;
  // 新建一个数组newelements，并将原始数据拷贝到newelements中；
  // newelements数组的长度=“原始数组的长度”+1
  object[] newelements = arrays.copyof(elements, len + 1);
  // 将“新增加的元素”保存到newelements中。
  newelements[len] = e;
  // 将newelements赋值给”volatile数组“。
  setarray(newelements);
  return true;
 } finally {
  // 释放“锁”
  lock.unlock();
 }
}

说明：add(e e)的作用就是将数据e添加到”volatile数组“中。它的实现方式是，新建一个数组，接着将原始的”volatile数组“的数据拷贝到新数组中，然后将新增数据也添加到新数组中；最后，将新数组赋值给”volatile数组“。
在add(e e)中有两点需要关注。

        第一，在”添加操作“开始前，获取独占锁(lock)，若此时有需要线程要获取锁，则必须等待；在操作完毕后，释放独占锁(lock)，此时其它线程才能获取锁。通过独占锁，来防止多线程同时修改数据！lock的定义如下：
transient final reentrantlock lock = new reentrantlock();

        第二，操作完毕时，会通过setarray()来更新”volatile数组“。而且，前面我们提过”即对一个volatile变量的读，总是能看到（任意线程）对这个volatile变量最后的写入“；这样，每次添加元素之后，其它线程都能看到新添加的元素。 

3. 获取

以get(int index)为例，来对“copyonwritearraylist的删除操作”进行说明。下面是get(int index)的代码：

public e get(int index) {
 return get(getarray(), index);
}
private e get(object[] a, int index) {
 return (e) a[index];
}

说明：get(int index)的实现很简单，就是返回”volatile数组“中的第index个元素。 

4. 删除

以remove(int index)为例，来对“copyonwritearraylist的删除操作”进行说明。下面是remove(int index)的代码：

public e remove(int index) {
 final reentrantlock lock = this.lock;
 // 获取“锁”
 lock.lock();
 try {
  // 获取原始”volatile数组“中的数据和数据长度。
  object[] elements = getarray();
  int len = elements.length;
  // 获取elements数组中的第index个数据。
  e oldvalue = get(elements, index);
  int nummoved = len - index - 1;
  // 如果被删除的是最后一个元素，则直接通过arrays.copyof()进行处理，而不需要新建数组。
  // 否则，新建数组，然后将”volatile数组中被删除元素之外的其它元素“拷贝到新数组中；最后，将新数组赋值给”volatile数组“。
  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();
 }
}

说明：remove(int index)的作用就是将”volatile数组“中第index个元素删除。它的实现方式是，如果被删除的是最后一个元素，则直接通过arrays.copyof()进行处理，而不需要新建数组。否则，新建数组，然后将”volatile数组中被删除元素之外的其它元素“拷贝到新数组中；最后，将新数组赋值给”volatile数组“。

         和add(e e)一样，remove(int index)也是”在操作之前，获取独占锁；操作完成之后，释放独占是“；并且”在操作完成时，会通过将数据更新到volatile数组中“。 

5. 遍历

以iterator()为例，来对“copyonwritearraylist的遍历操作”进行说明。下面是iterator()的代码：

public iterator<e> iterator() {
 return new cowiterator<e>(getarray(), 0);
}

说明：iterator()会返回cowiterator对象。

cowiterator实现额listiterator接口，它的源码如下：

private static class cowiterator<e> implements listiterator<e> {
 private final object[] snapshot;
 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++];
 }
 // 获取上一个元素
 @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();
 }
}

说明：cowiterator不支持修改元素的操作。例如，对于remove(),set(),add()等操作，cowiterator都会抛出异常！
另外，需要提到的一点是，copyonwritearraylist返回迭代器不会抛出concurrentmodificationexception异常，即它不是fail-fast机制的！ 

copyonwritearraylist示例

下面，我们通过一个例子去对比arraylist和copyonwritearraylist。 

import java.util.*;
 import java.util.concurrent.*;
 /*
 * copyonwritearraylist是“线程安全”的动态数组，而arraylist是非线程安全的。
 *
 * 下面是“多个线程同时操作并且遍历list”的示例
 * (01) 当list是copyonwritearraylist对象时，程序能正常运行。
 * (02) 当list是arraylist对象时，程序会产生concurrentmodificationexception异常。
 *
 * 
 */
 public class copyonwritearraylisttest1 {
  // todo: list是arraylist对象时，程序会出错。
  //private static list<string> list = new arraylist<string>();
  private static list<string> list = new copyonwritearraylist<string>();
  public static void main(string[] args) {
   // 同时启动两个线程对list进行操作！
   new mythread("ta").start();
   new mythread("tb").start();
  }
  private static void printall() {
   string value = null;
   iterator iter = list.iterator();
   while(iter.hasnext()) {
    value = (string)iter.next();
    system.out.print(value+", ");
   }
   system.out.println();
  }
  private static class mythread extends thread {
   mythread(string name) {
    super(name);
   }
   @override
   public void run() {
     int i = 0;
    while (i++ < 6) {
     // “线程名” + "-" + "序号"
     string val = thread.currentthread().getname()+"-"+i;
     list.add(val);
     // 通过“iterator”遍历list。
     printall();
    }
   }
  }
 }

(某一次)运行结果：

ta-1, tb-1, ta-1, 
tb-1, 
ta-1, ta-1, tb-1, tb-1, tb-2, 
tb-2, ta-1, ta-2, 
tb-1, ta-1, tb-2, tb-1, ta-2, tb-2, tb-3, 
ta-2, ta-1, tb-3, tb-1, ta-3, 
tb-2, ta-1, ta-2, tb-1, tb-3, tb-2, ta-3, ta-2, tb-4, 
tb-3, ta-1, ta-3, tb-1, tb-4, tb-2, ta-4, 
ta-2, ta-1, tb-3, tb-1, ta-3, tb-2, tb-4, ta-2, ta-4, tb-3, tb-5, 
ta-3, ta-1, tb-4, tb-1, ta-4, tb-2, tb-5, ta-2, ta-5, 
tb-3, ta-1, ta-3, tb-1, tb-4, tb-2, ta-4, ta-2, tb-5, tb-3, ta-5, ta-3, tb-6, 
tb-4, ta-4, tb-5, ta-5, tb-6, ta-6,

结果说明：如果将源码中的list改成arraylist对象时，程序会产生concurrentmodificationexception异常。