Java高并发18-并发列表CopyOnWriteArrayList源码解析

时间:2021-01-09 23:44:00 来源:互联网 作者: 神秘的大神 字体:

一、CopyOnWriteArrayList

  • 概览:该List是一个JUC包中的唯一并发List,它是线程安全的,底层是一个数组,我们所有的操作都是使用了写时复制的策略,下面这张图片就是该类的一个类图 18.1

1.类图基本解释

  • 有一个独占锁ReentrantLock用于锁定线程,同一时间只能由一个线程进行修改。

2.初始化

  • 首先看无参构造函数,创建一个大小为0的数组
    private transient volatile Object[] array;

 public CopyOnWriteArrayListAnalysis() {
  setArray(new Object[0]);
 }
 
    final void setArray(Object[] a) {
        array = a;
    }
  • 然后看一下有参数的构造方法,传入一个数组,就是一个该数组的副本的List数据结构
    public CopyOnWriteArrayListAnalysis(E[] toCopyIn) {
     //工具函数Arrays.copyOf表示复制一个第二参数的长度,内容为第一个参数的数组,并且返回的数组类型是第三个参数
     setArray(Arrays.copyOf(toCopyIn, toCopyIn.length,Object[].class));
    }
  • 下面是如果传入是一个Collection的情况,我们可以看到有参的构造方法,无论传入什么类型都会将其转化为Object[].class类型
    public CopyOnWriteArrayListAnalysis(Collection<? extends E> c) {
     Object[] elements;
     if(c.getClass() == CopyOnWriteArrayListAnalysis.class{
      elements = ((CopyOnWriteArrayListAnanlysis)c).getArray();
     }else {
      elements = c.toArray();
      //下面这条语句是用来判断如果没有返回一个Object[].class的情况
      if(elements.getClass() != Object[].class{
       elements = Arrays.copyOf(elements,elements.length,Object[].class);
      }
     }
    }
    
    final Object[] getArray() {
        return array;
    }

3.添加元素

  • 该类中有四种添加元素的方法,分别是add(E element),addIfAbsent(E element),add(int index,E element),addAllAbsent(Collection<? extends E> element)
  • 函数的释义基本和List一致,只是底层的实现方式不同,下面我们就add(E elelment)方法为例进行讲解
    public boolean add(E element) {
     final ReentrantLock lock = this.lock; // 获取该实例的独占锁
     lock.lock();
     try {
      Object[] elements = getArray(); // 获取内部存储的数组,注意这时候还是原来的数组,
      // 只不过是使用一个新的引用来指向它的地址
      int len = elements.length; // 获取数组的长度
      Object[] newElements = Arrays.copyOf(elements,len+1);
      // 使用Arrays工具类,创建一个新的数组,将前面的元素全都复制进去,并且留出一个位置
      newElements[len] = element;
      // 使用这个新数组来代替原来的数组
      setArray(newElements);
     }finally {
      lock.unlock();
     }
    }

注意点:(1)由于使用了独占锁,所以同一时间只能由一个线程来进行add操作,保证了原子性;(2)add操作是创建一个新的数组,不是在原来的数组上进行操作的 ,并且该List输一个无界List

4.获取指定位置的元素

    public E get(int index) {
     return get(getArray(),index);
    }
    
    public E get(Object[] a,int index) {
     return (E)a[index];
    }
  • 获取某一个索引的值,由于没有进行加锁操作,所以如果有删除动作的同时,获取某一个位置的元素,会出现“弱一致性问题”,我们从下文也可以看出,由于删除一个元素,也不是在原数组上进行,先有一个副本,然后删除使底层数组变更为新数组,而get操作则还是在老数组的基础上进行的,所以会有不一致的问题。

5.修改指定元素

    public E set(int index ,E element) {
     final ReentrantLock lock = this.lock;
     lock.lock();
     try {
      Object[] a = getArray();
      E oldValue = a[index];
      if(oldValue != element) {
       int len = a.length;
       Object[] newElements = Arrays.copyOf(a, len);
       newElements[index] = element;
       setArray(newElements);
      }else {
       setArray(a);
      }
      
     }finally{
      lock.unlock();
     }
    }
  • 基本逻辑还是很清晰的有一点需要强调的是如果新的元素没有变动的化,仍然会调用setArray()方法进行设置一下,这个是为了保证volatile的语义。

6.删除元素

  • 删除元素的方法有boolean remove(int index),boolean remove(Object o)和boolean remove(Object o,Object[] snapshot,int index)等,它们的基本原理都是类似,下面我们讲解一下第一个函数
    public E remove(int index) {
     final ReentrantLock lock = this.lock;
     lock.lock();
     try {
      Object[] elements = getArray();
      int len = elements.length;
      int removeRemain = len - (index + 1); // 这个整数代表要迁移的剩余元素个数
      if(removeRemain == 0) {
       setArray(Arrays.copyOf(elements, len-1));//除了最后一个全部都copy过去
      }else {
       Object[] newElements = new Object[len-1];
       System.arraycopy(elements,0,newElements,0,index);
       System.arraycopy(elements,index+1,newElements,index,removeRemain);
       // 这里我们学习一个函数System.arraycopy
       // 第一个参数代表从哪里复制,第二个参数代表从第几个索引开始
       // 第三个参数代表复制到哪个数组中,从第几个开始,复制几个到新数组
       setArray(newElements);
      }
     }finally {
      lock.unlock();
     }
    }

7.迭代器

    public Iterator<E> iterator(){
     return new COWIteratro<E>(getArray(),0);
    }
    
    static final class COWIterator<Eimplements ListIterator<E{
     // array的快照版本
     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 E next() {
      if(!hasNext()) {
       throw new NoSuchElementException();
      }
      return <E>snapshot[cursor++];
     } 
    }  
  • 从上面的代码可以看出,迭代器虽然是引用传递,用的数组还是底层数组,但是我们别忘记删除,添加等操作都是重新指向一个新的数组,因此这种迭代器是弱一致性,同时查询和编辑是线程不安全的。

二、源码:

  • 所在包:com.ruigege.ConcurrentListSouceCodeAnalysis5
  • https://github.com/ruigege66/ConcurrentJava
  • CSDN: https://blog.csdn.net/weixin_44630050
  • 博客园:https://www.cnblogs.com/ruigege0000/
  • 欢迎关注微信公众号:傅里叶变换,个人账号,仅用于技术交流 1000