你的位置:首页 > Java教程

[Java教程]第三章 CopyOnWriteArrayList源码解析


注:在看这篇文章之前,如果对ArrayList底层不清楚的话,建议先去看看ArrayList源码解析。

http://www.cnblogs.com/java-zhao/p/5102342.html

1、对于CopyOnWriteArrayList需要掌握以下几点

  • 创建:CopyOnWriteArrayList()
  • 添加元素:即add(E)方法
  • 获取单个对象:即get(int)方法
  • 删除对象:即remove(E)方法
  • 遍历所有对象:即iterator(),在实际中更常用的是增强型的for循环去做遍历

注:CopyOnWriteArrayList是一个线程安全,读操作时无锁的ArrayList。

 

2、创建

public CopyOnWriteArrayList()

使用方法:

List<String> list = new CopyOnWriteArrayList<String>();

相关源代码:

  private volatile transient Object[] array;//底层数据结构  /**   * 获取array   */  final Object[] getArray() {    return array;  }  /**   * 设置Object[]   */  final void setArray(Object[] a) {    array = a;  }  /**   * 创建一个CopyOnWriteArrayList   * 注意:创建了一个0个元素的数组   */  public CopyOnWriteArrayList() {    setArray(new Object[0]);  }

View Code

注意点:

  • 设置一个容量为0的Object[];ArrayList会创造一个容量为10的Object[]

 

3、添加元素

public boolean add(E e)

使用方法:

list.add("hello");

源代码:

  /**   * 在数组末尾添加元素   * 1)获取锁   * 2)上锁   * 3)获取旧数组及其长度   * 4)创建新数组,容量为旧数组长度+1,将旧数组拷贝到新数组   * 5)将要增加的元素加入到新数组的末尾,设置全局array为新数组   */  public boolean add(E e) {    final ReentrantLock lock = this.lock;//这里为什么不直接用this.lock(即类中已经初始化好的锁)去上锁    lock.lock();//上锁    try {      Object[] elements = getArray();//获取当前的数组      int len = elements.length;//获取当前数组元素      /*       * Arrays.copyOf(elements, len + 1)的大致执行流程:       * 1)创建新数组,容量为len+1,       * 2)将旧数组elements拷贝到新数组,       * 3)返回新数组       */      Object[] newElements = Arrays.copyOf(elements, len + 1);      newElements[len] = e;//新数组的末尾元素设成e      setArray(newElements);//设置全局array为新数组      return true;    } finally {      lock.unlock();//解锁    }  }

View Code

注意点:

  • Arrays.copyOf(T[] original, int newLength)该方法在ArrayList中讲解过

疑问:

  • 在add(E)方法中,为什么要重新定义一个ReentrantLock,而不直接使用那个定义的类变量锁(全局锁)
    • 答:我们在add(E)中加锁,是为了不能让两个线程同时执行add(E)方法,所以给add加了锁;但是,我们可以同时有两个线程一个做add操作,一个做remove操作,如果使用全局锁的话,那么add与remove同一时刻就只能有一个执行了。原因是这样吗?("同时有两个线程一个做add操作,一个做remove操作"这个可以吗?如果可以的话,那么在假设在add操作刚刚获取完原数组的长度之后,remove操作整好将原数组长度减1了,这个时候,add之后实际创建出来的数组就比原数组大2了,那么下次add的时候就可以放下这个元素了,为什么还要扩容呢?)(懂这一块儿的哥们儿给指点一下)
  • 根据以上代码可知,每增加一个新元素,都要进行一次数组的复制消耗,那为什么每次不将数组的元素设大(比如说像ArrayList那样,设置为原来的1.5倍+1),这样就会大大减少因为数组元素复制所带来的消耗?

 

4、获取元素

public E get(int index)

使用方法:

list.get(0)

源代码:

  /**   * 根据下标获取元素   * 1)获取数组array   * 2)根据索引获取元素   */  public E get(int index) {    return (E) (getArray()[index]);  }

View Code

注意点:

  • 获取不需要加锁

疑问:读操作会发生脏读,为什么?

 

5、删除元素

public boolean remove(Object o)

使用方法:

list.remove("hello")

源代码:

  /**   * 删除list中的第一个o   * 1)获取锁、上锁   * 2)获取旧数组、旧数组的长度len   * 3)如果旧数组长度为0,返回false   * 4)如果旧数组有值,创建新数组,容量为len-1   * 5)从0开始遍历数组中除了最后一个元素的所有元素   * 5.1)将旧数组中将被删除元素之前的元素复制到新数组中,   * 5.2)将旧数组中将被删除元素之后的元素复制到新数组中   * 5.3)将新数组赋给全局array   * 6)如果是旧数组的最后一个元素要被删除,则   * 6.1)将旧数组中将被删除元素之前的元素复制到新数组中   * 6.2)将新数组赋给全局array   */  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;//新数组长度为原数组长度-1        Object[] newElements = new Object[newlen];//创建新数组        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);//将新数组赋给全局array            return true;          } else            newElements[i] = elements[i];//将旧数组中将被删除元素之前的元素复制到新数组中        }        if (eq(o, elements[newlen])) {//将要删除的元素时旧数组中的最后一个元素          setArray(newElements);          return true;        }      }      return false;    } finally {      lock.unlock();    }  }

View Code

判断两个对象是否相等:

  /**   * 判断o1与o2是否相等   */  private static boolean eq(Object o1, Object o2) {    return (o1 == null ? o2 == null : o1.equals(o2));  }

View Code

注意点:

  • 需要加锁
  • ArrayList的remove使用了System.arraycopy(这是一个native方法),而这里没使用,所以理论上这里的remove的性能要比ArrayList的remove要低

 

6、遍历所有元素

iterator()  hasNext()  next()

使用方法:

讲解用的:

    Iterator<String> itr = list.iterator();    while(itr.hasNext()){      System.out.println(itr.next());    }

View Code

实际中使用的:

    for(String str : list){      System.out.println(str);    }

View Code

源代码:

  public Iterator<E> iterator() {    return new COWIterator<E>(getArray(), 0);  }

View Code
  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;//0~snapshot.length-1    }        public E next() {      if (!hasNext())        throw new NoSuchElementException();      return (E) snapshot[cursor++];    }

View Code

说明:这一块儿代码非常简单,看看代码注释就好。

注意:

由于遍历的只是全局数组的一个副本,即使全局数组发生了增删改变化,副本也不会变化,所以不会发生并发异常。但是,可能在遍历的过程中读到一些刚刚被删除的对象。

注意点:

 

总结:

  • 线程安全,读操作时无锁的ArrayList
  • 底层数据结构是一个Object[],初始容量为0,之后每增加一个元素,容量+1,数组复制一遍
  • 增删改上锁、读不上锁
  • 遍历过程由于遍历的只是全局数组的一个副本,即使全局数组发生了增删改变化,副本也不会变化,所以不会发生并发异常
  • 读多写少且脏数据影响不大的并发情况下,选择CopyOnWriteArrayList

疑问:

  • 在add(E)方法中,为什么要重新定义一个ReentrantLock,而不直接使用那个定义的类变量锁(全局锁)
  • 每增加一个新元素,都要进行一次数组的复制消耗,那为什么每次不将数组的元素设大(比如说像ArrayList那样,设置为原来的1.5倍+1),这样就会大大减少因为数组元素复制所带来的消耗?
  • get(int)操作会发生脏读,为什么?