java集合之CopyOnWriteArrayList源碼解析

更新時間：2023年12月21日 08:55:02 作者：Colins~

這篇文章主要介紹了java集合之CopyOnWriteArrayList源碼解析,容器array是volatile修飾的,即set和get方法都是線程安全的,整個添加過程上了鎖,所以整體是通過volatile和lock來保證的線程安全,需要的朋友可以參考下

一、基礎(chǔ)常量和結(jié)構(gòu)

// 鎖
final transient ReentrantLock lock = new ReentrantLock();
// 空數(shù)組
private transient volatile Object[] array;

可以看到底層依舊還是數(shù)組，但是沒了默認大小和容量大小的變量了，而且數(shù)組容器被volatile關(guān)鍵字修飾，同時還多了一把鎖，這同時說明了CopyOnWriteArrayList是線程安全的設(shè)計

為什么沒有默認大小了呢？難道不需要判斷擴容了？接著往下看

二、構(gòu)造方法

public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}
final void setArray(Object[] a) {
    array = a;
}
// 帶參構(gòu)造
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

兩個構(gòu)造方法：

默認的：直接創(chuàng)建了個空數(shù)組然后賦值給了容器數(shù)組
帶參的：把傳參的數(shù)組數(shù)據(jù)賦值到了一個新數(shù)組上面然后把新數(shù)組給了容器數(shù)組（對Arrays.copyOf不熟的可以看看上篇ArrayList介紹）

為什么帶參的方法要搞一個新的數(shù)組出來然后在賦值給容器數(shù)組呢？

因為數(shù)組賦值，不是值傳遞，傳遞后依舊會受原數(shù)組的影響，如下：（不清楚的了解一下值傳遞和地址傳遞）

Object[] aa=new Object[]{1,2};
Object[] aa1=aa;
System.out.println("改變前："+aa1[0]);
aa[0]=3;
System.out.println("改變后："+aa1[0]);

//結(jié)果如下：
改變前：1
改變后：3
ps：改的是aa數(shù)組

三、add操作

默認添加

整個過程邏輯很簡單：

加鎖，獲取容器數(shù)組
創(chuàng)建一個長度+1 的新數(shù)組，并把之前數(shù)組的數(shù)據(jù)復(fù)制過去
然后新數(shù)組尾部賦值，并把新數(shù)組重新賦值給容器數(shù)組

因為每次添加都會創(chuàng)建一個長度+1的新數(shù)組，所以并不需要擴容了

線程安全方面： 容器array是volatile修飾的，即set和get方法都是線程安全的，整個添加過程上了鎖，所以整體是通過volatile和lock來保證的線程安全

性能方面： 可以看到舍棄了擴容操作，但每次添加都會創(chuàng)建個新的數(shù)組并復(fù)制數(shù)據(jù)過去，這個過程是非常耗時的，所以并不合適頻繁寫入的場景

源代碼如下：

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 加鎖
    lock.lock();
    try {
        // 獲取容器數(shù)組
        Object[] elements = getArray();
        // 獲取容器數(shù)組長度
        int len = elements.length;
        // 創(chuàng)建一個長度+1的新數(shù)組 并把之前的數(shù)據(jù)復(fù)制到新數(shù)組
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 新數(shù)組尾部賦值
        newElements[len] = e;
        // 把新數(shù)組重新賦值給容器數(shù)組
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

指定位置插入

同樣也可以指定位置插入,流程跟上述差不多一致，但是有個雙Copy操作：

加鎖，獲取容器數(shù)組
下標校驗
如果正好是尾部插入：創(chuàng)建一個長度+1 的新數(shù)組，并把之前數(shù)組的數(shù)據(jù)復(fù)制過去
不是尾部：需要復(fù)制兩次，總的來說就是下標前的數(shù)據(jù)照舊復(fù)制，但下標后的數(shù)據(jù)復(fù)制后，整體位置往后移一位
然后新數(shù)組尾部賦值，并把新數(shù)組重新賦值給容器數(shù)組

源代碼如下：

public void add(int index, E element) {
      final ReentrantLock lock = this.lock;
      // 加鎖
      lock.lock();
      try {
          // 獲取容器數(shù)組
          Object[] elements = getArray();
          // 獲取容器數(shù)組長度
          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)
              // 如果正好是尾部 則照舊創(chuàng)建并復(fù)制
              newElements = Arrays.copyOf(elements, len + 1);
          else {
              // 不是尾部則創(chuàng)建一個長度+1 的新數(shù)組
              newElements = new Object[len + 1];
              // 依舊是復(fù)制 但這里復(fù)制了兩次 
              // 0-index的元素復(fù)制一次 位置不變
              System.arraycopy(elements, 0, newElements, 0, index);
              // index-尾部的元素復(fù)制一次 整體位置都后移一位
              System.arraycopy(elements, index, newElements, index + 1,
                               numMoved);
          }
          // 指定位置賦值
          newElements[index] = element;
          // 把新數(shù)組重新賦值給容器數(shù)組
          setArray(newElements);
      } finally {
          lock.unlock();
      }
  }

四、get操作

很簡單先獲取容器數(shù)組，然后根據(jù)數(shù)組下標取值就好

容器數(shù)組是volatile修飾的，所以本身get就是線程安全的，始終獲取的最新值

源代碼如下：

public E get(int index) {
    return get(getArray(), index);
}
final Object[] getArray() {
  return array;
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

五、set操作

這個我在ArrayList里面沒有介紹，因為很簡單就是替換數(shù)組下標原本的值即可

這里提一下是因為此操作也是線程安全的上了鎖：

加鎖，獲取下標對應(yīng)的舊值
對比新值和舊值，值一樣則不作任何操作
值不一樣則創(chuàng)建個新的數(shù)組，然后再修改下標的值，再把新數(shù)組回寫

源代碼如下：

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 獲取容器數(shù)組
        Object[] elements = getArray();
        // 獲取原本的舊值
        E oldValue = get(elements, index);
        // 對比新值和舊值
        if (oldValue != element) {
            int len = elements.length;
            // 值不一致 則創(chuàng)建個新數(shù)組，把數(shù)據(jù)復(fù)制過去
            Object[] newElements = Arrays.copyOf(elements, len);
            // 修改新數(shù)組對應(yīng)下標下的值
            newElements[index] = element;
            // 把新數(shù)組寫回
            setArray(newElements);
        } else {
            // 新值舊值一樣 就不做任何操作 ，把數(shù)組寫回去就好了
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

六、remove操作

根據(jù)值remove

先遍歷查找元素下標所在
然后加鎖，判斷下標是否有效，無效需要重新找一次下標，沒找到直接返回false
找到了下標然后創(chuàng)建長度-1的新數(shù)組，雙copy，然后回寫到容器數(shù)組

總的邏輯不復(fù)雜，跟常規(guī)的list一樣，先查再移除，但由于第一次查找的時候并沒有加鎖，所以第一次找到的下標到移除的過程中數(shù)組可能已經(jīng)發(fā)生了修改，下標會失效，所以在真正移除的時候加鎖之后又判斷了一次下標的有效性

為什么不直接加鎖然后在查找下標后移除呢？

當然也可以，但是加鎖會阻塞其他的操作，等于是在遍歷查找的時候其他操作就全被阻塞了，但是現(xiàn)在這樣假設(shè)數(shù)組沒被修改，則直接雙copy移除了，相比更優(yōu)，假設(shè)數(shù)組被修改，無非就是再重新遍歷一次，從效率上來講多遍歷了一次，效率低了，從阻塞上來看都一樣是遍歷+雙copy，所以綜合來說這種設(shè)計側(cè)重于使用場景

源代碼如下：

public boolean remove(Object o) {
    // 獲取容器數(shù)組
    Object[] snapshot = getArray();
    // 遍歷查找元素所在的下標索引
    int index = indexOf(o, snapshot, 0, snapshot.length);
    // 根據(jù)索引移除
    return (index < 0) ? false : remove(o, snapshot, index);
}
private boolean remove(Object o, Object[] snapshot, int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            // 獲取當前最新的容器數(shù)組
            Object[] current = getArray();
            int len = current.length;
            // 判斷傳入的數(shù)組是否與當前數(shù)組相同  如果不相同則需要判斷傳入index下標的有效性
            if (snapshot != current) findIndex: {
                //得到遍歷范圍最小值，這個范圍不一定能找到元素，當元素被后移時
                //注意index是索引，len是數(shù)組大小。
                int prefix = Math.min(index, len);
                for (int i = 0; i < prefix; i++) {
                    //嚴格的判斷。只有當兩個數(shù)組相同索引位置的元素不是同一個元素；
                    //且current索引元素和參數(shù)o 是相等的時候 則重新獲取賦值index 退出分支
                    if (current[i] != snapshot[i] && eq(o, current[i])) {
                        index = i;
                        break findIndex;
                    }
                }
                // 下標已經(jīng)超過或等于長度 則下標已經(jīng)無效了 直接返回
                if (index >= len)
                    return false;
                // 下標依舊有效并且值相等則 退出分支
                if (current[index] == o)
                    break findIndex;
                // 上面都不滿足則重新查找一次下標
                index = indexOf(o, current, index, len);
                // 不存在了則直接返回
                if (index < 0)
                    return false;
            }
            // 經(jīng)過上面一頓操作 已經(jīng)找到了要移除元素的下標了，所以創(chuàng)建個長度-1的新數(shù)組
            Object[] newElements = new Object[len - 1];
            // 雙復(fù)制 與之前一樣 ，index后面的元素需要往前移
            System.arraycopy(current, 0, newElements, 0, index);
            System.arraycopy(current, index + 1, newElements, index, len - index - 1);
            // 新數(shù)組賦值給容器數(shù)組
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

根據(jù)下標remove

這個和根據(jù)下標add操作有點類似：

判斷下標是不是尾部，是尾部則直接Arrays.copyOf
不是尾部則雙arraycopy，index后的數(shù)據(jù)要整體前移一位

源代碼如下：

public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            // 獲取容器數(shù)組
            Object[] elements = getArray();
            int len = elements.length;
            // 獲取舊值
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                // 如果是尾部則直接創(chuàng)建長度-1的數(shù)組再復(fù)制過去 
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                // 不是尾部 則雙copy ，index后的數(shù)據(jù)整體前移一位
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

總結(jié)

從上面可以看出CopyOnWriteArrayList是線程安全的，是volatile和lock來保證的，但是也很明顯的可以看出弊端就是對修改的效率不高，每個修改都涉及到copy操作，甚至還有兩次copy的，而且每個修改都是在新的數(shù)組中進行的，這也應(yīng)對了CopyOnWrite這個命名；就因為寫的效率不高，所以這個更適合在讀多寫少的場景中使用

到此這篇關(guān)于java集合之CopyOnWriteArrayList源碼解析的文章就介紹到這了,更多相關(guān)CopyOnWriteArrayList源碼內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: