集合框架 List篇（2）---CopyOnWriteArrayList

List
-----------
1.ArrayList（jdk1.5以前版本中Vector）
2.LinkedList（jdk1.5以前版本中Stack）
3.CopyOnWriteArrayList

----------------------------------------CopyOnWriteArrayList----------------------------------------

CopyOnWriteArrayList 用在“读多，改少”的“并发”应用中。

不存在“扩容”的概念，每次写操作（add or remove）都要copy一个副本，在副本的基础上修改后改变array引用---所以称为“CopyOnWrite”，因此在写操作是加锁，并且对整个list的copy操作时相当耗时的，过多的写操作不推荐使用该存储结构。

CopyOnWriteArrayList的类层次结构

public class CopyOnWriteArrayList <E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable 

CopyOnWriteArrayList的全局变量

 transient final ReentrantLock lock = new ReentrantLock();//全局锁

 private volatile transient Object[] array;//volatile（修改可见）类型的数组array

//内部的实现中仅通过array的get和set方法对其进行操作

 final Object[] getArray() {
        return array;
  }

  final void setArray(Object[] a) {
        array = a;
  }

CopyOnWriteArrayList的构造方法

   /**
     * 创建一个空的list，默认容量为0，这个和ArraList中的默认10不同，主要是因为在对CopyOnWriteArrayList的修改操作时都是先copy

     *一个数组（容量+1或容量-1），处理后再把引用赋给array的，不存在扩容的情况，所以当初始化时就没必要指定长度了。

     */
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

 //通过已有集合构建CopyOnWriteArrayList

 public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements = c.toArray();
     if (elements.getClass() != Object[].class)
           elements = Arrays.copyOf(elements, elements.length, Object[].class);//copy一个数组
    setArray(elements);//把array引用指向新的数组
  }

  //通过给定的数组创建List

 public CopyOnWriteArrayList(E[] toCopyIn) {
     setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
 }

CopyOnWriteArrayList的get方法

//get操作 ，不加锁

public E get(int index) {
      //直接定位到数组的index下标处，没有加锁操作

      //（array是volatile类型的，volatile的 happen-before原则就是所有的“写操作”都在“读操作”前发生，保证了数据的一致性） 

        return (E)(getArray()[index]);

 } 

CopyOnWriteArrayList的set方法

//set 修改元素操作，加锁

public E set(int index, E element) {//在指定的位置index处设置element
 final ReentrantLock lock = this.lock;
 lock.lock();//加锁
 try {
     Object[] elements = getArray();
     Object oldValue = elements[index];//获得数组中index坐标下的值

     if (oldValue != element) {//如果传入的element和目前坐标index处的值不同
         int len = elements.length;
         Object[] newElements = Arrays.copyOf(elements, len);//copy一个数组副本
         newElements[index] = element;//并把指定index处的值进行替换
         setArray(newElements);//array引用指向新的数组
     } else {
        // Not quite a no-op; ensures volatile write semantics
       setArray(elements);//保证volatile的happen-before原则
    }
   return (E)oldValue;
 } finally {
     lock.unlock();//解锁
 }
}

CopyOnWriteArrayList的add方法

//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;//在新数组的最后一个位置加入e元素
          setArray(newElements);
          return true;
       } finally {
         lock.unlock();//解锁
      }
    }

 //在指定的index处加入元素element，加锁

 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;
        if (numMoved == 0)//刚好在末端加入的情况
                 newElements = Arrays.copyOf(elements, len + 1);
        else {//在中间的情况
                newElements = new Object[len + 1];
               System.arraycopy(elements, 0, newElements, 0, index);//index前的元素
               System.arraycopy(elements, index, newElements, index + 1, numMoved);//index后的元素
        }
     newElements[index] = element;
     setArray(newElements);
 } finally {
     lock.unlock();//解锁
 }
}

CopyOnWriteArrayList的remove方法

//remove 删除操作，加锁

public E remove(int index) {
     final ReentrantLock lock = this.lock;
     lock.lock();//加锁
     try {
         Object[] elements = getArray();
         int len = elements.length;
         Object oldValue = elements[index];
         int numMoved = len - index - 1;
         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 (E)oldValue;
    } finally {
        lock.unlock();//解锁
    }
  }

//remove参数是元素对象，需要遍历比较，加锁

public boolean remove(Object o) {
     final ReentrantLock lock = this.lock;
     lock.lock();//加锁
     try {
         Object[] elements = getArray();
         int len = elements.length;
         if (len != 0) {
                // Copy while searching for element to remove
                // This wins in the normal case of element being present
               int newlen = len - 1;
              Object[] newElements = new Object[newlen];//创建一个length-1的数组

              for (int i = 0; i < newlen; ++i) {
                      if (eq(o, elements[i])) {
                         // 如果找到了该元素，就把其后继拷贝到新数组中

                         for (int k = i + 1; k < len; ++k)
                                newElements[k-1] = elements[k];
                         setArray(newElements);
                         return true;
                       } else

                         //把其前面的节点一一设置到新数组中去
                         newElements[i] = elements[i];
                       }

                     // 特殊的判断：和最和一个元素比较（如果刚好是最后一个，就大大减少比较）

                     if (eq(o, elements[newlen])) {
                           setArray(newElements);
                           return true;
                      }
            }
        return false;
   } finally {
       lock.unlock();//解锁
   }

}