集合框架 List篇(2)—CopyOnWriteArrayList

  categories:资料  author:

来源:互联网

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();//解锁
   }

}

 

http://hi.baidu.com/yao1111yao/item/5c2f7f0984f3bb36a2332a6d



快乐成长 每天进步一点点      京ICP备18032580号-1