Java高并發18-并發串列CopyOnWriteArrayList原始碼決議

一、CopyOnWriteArrayList

• 概覽：該List是一個JUC包中的唯一并發List，它是執行緒安全的，底層是一個陣列，我們所有的操作都是使用了寫時復制的策略，下面這張圖片就是該類的一個類圖

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<E> implements 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/
• 歡迎關注微信公眾號：傅里葉變換，個人賬號，僅用于技術交流