15 CopyOnWriteArrayList 源碼解析和設計思路 · 面試官系統精講Java源碼及大廠真題

## 15 CopyOnWriteArrayList 源碼解析和設計思路 ## 引導語在 ArrayList 的類注釋上，JDK 就提醒了我們，如果要把 ArrayList 作為共享變量的話，是線程不安全的，推薦我們自己加鎖或者使用 Collections.synchronizedList 方法，其實 JDK 還提供了另外一種線程安全的 List，叫做 CopyOnWriteArrayList，這個 List 具有以下特征： 1. 線程安全的，多線程環境下可以直接使用，無需加鎖； 2. 通過鎖 + 數組拷貝 + volatile 關鍵字保證了線程安全； 3. 每次數組操作，都會把數組拷貝一份出來，在新數組上進行操作，操作成功之后再賦值回去。 ### 1 整體架構從整體架構上來說，CopyOnWriteArrayList 數據結構和 ArrayList 是一致的，底層是個數組，只不過 CopyOnWriteArrayList 在對數組進行操作的時候，基本會分四步走： 1. 加鎖； 2. 從原數組中拷貝出新數組； 3. 在新數組上進行操作，并把新數組賦值給數組容器； 4. 解鎖。除了加鎖之外，CopyOnWriteArrayList 的底層數組還被 volatile 關鍵字修飾，意思是一旦數組被修改，其它線程立馬能夠感知到，代碼如下： private transient volatile Object[] array; 整體上來說，CopyOnWriteArrayList 就是利用鎖 + 數組拷貝 + volatile 關鍵字保證了 List 的線程安全。 #### 1.1 類注釋我們看看從 CopyOnWriteArrayList 的類注釋上能得到哪些信息： 1. 所有的操作都是線程安全的，因為操作都是在新拷貝數組上進行的； 2. 數組的拷貝雖然有一定的成本，但往往比一般的替代方案效率高； 3. 迭代過程中，不會影響到原來的數組，也不會拋出 ConcurrentModificationException 異常。接著我們來看下 CopyOnWriteArrayList 的核心方法源碼。 ### 2 新增新增有很多種情況，比如說：新增到數組尾部、新增到數組某一個索引位置、批量新增等等，操作的思路還是我們開頭說的四步，我們拿新增到數組尾部的方法舉例，來看看底層源碼的實現： ``` // 添加元素到數組尾部 public boolean add(E e) { final ReentrantLock lock = this.lock; // 加鎖 lock.lock(); try { // 得到所有的原數組 Object[] elements = getArray(); int len = elements.length; // 拷貝到新數組里面，新數組的長度是 + 1 的，因為新增會多一個元素 Object[] newElements = Arrays.copyOf(elements, len + 1); // 在新數組中進行賦值，新元素直接放在數組的尾部 newElements[len] = e; // 替換掉原來的數組 setArray(newElements); return true; // finally 里面釋放鎖，保證即使 try 發生了異常，仍然能夠釋放鎖 } finally { lock.unlock(); } } ``` 從源碼中，我們發現整個 add 過程都是在持有鎖的狀態下進行的，通過加鎖，來保證同一時刻只能有一個線程能夠對同一個數組進行 add 操作。除了加鎖之外，還會從老數組中創建出一個新數組，然后把老數組的值拷貝到新數組上，這時候就有一個問題：都已經加鎖了，為什么需要拷貝數組，而不是在原來數組上面進行操作呢，原因主要為： 1. volatile 關鍵字修飾的是數組，如果我們簡單的在原來數組上修改其中某幾個元素的值，是無法觸發可見性的，我們必須通過修改數組的內存地址才行，也就說要對數組進行重新賦值才行。 2. 在新的數組上進行拷貝，對老數組沒有任何影響，只有新數組完全拷貝完成之后，外部才能訪問到，降低了在賦值過程中，老數組數據變動的影響。簡單 add 操作是直接添加到數組的尾部，接著我們來看下指定位置添加元素的關鍵源碼（部分源碼）： ``` // len：數組的長度、index：插入的位置 int numMoved = len - index; // 如果要插入的位置正好等于數組的末尾，直接拷貝數組即可 if (numMoved == 0) newElements = Arrays.copyOf(elements, len + 1); else { // 如果要插入的位置在數組的中間，就需要拷貝 2 次 // 第一次從 0 拷貝到 index。 // 第二次從 index+1 拷貝到末尾。 newElements = new Object[len + 1]; System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index, newElements, index + 1, numMoved); } // index 索引位置的值是空的，直接賦值即可。 newElements[index] = element; // 把新數組的值賦值給數組的容器中 setArray(newElements); ``` 從源碼中可以看到，當插入的位置正好處于末尾時，只需要拷貝一次，當插入的位置處于中間時，此時我們會把原數組一分為二，進行兩次拷貝操作。最后還有個批量新增操作，源碼我們就不貼了，底層也是拷貝數組的操作。 #### 2.1 小結從 add 系列方法可以看出，CopyOnWriteArrayList 通過加鎖 + 數組拷貝+ volatile 來保證了線程安全，每一個要素都有著其獨特的含義： 1. 加鎖：保證同一時刻數組只能被一個線程操作； 2. 數組拷貝：保證數組的內存地址被修改，修改后觸發 volatile 的可見性，其它線程可以立馬知道數組已經被修改； 3. volatile：值被修改后，其它線程能夠立馬感知最新值。三個要素缺一不可，比如說我們只使用 1 和 3 ，去掉 2，這樣當我們修改數組中某個值時，并不會觸發 volatile 的可見特性的，只有當數組內存地址被修改后，才能觸發把最新值通知給其他線程的特性。 ### 3 刪除接著我們來看下指定數組索引位置刪除的源碼： ``` // 刪除某個索引位置的數據 public E remove(int index) { final ReentrantLock lock = this.lock; // 加鎖 lock.lock(); try { Object[] elements = getArray(); int len = elements.length; // 先得到老值 E oldValue = get(elements, index); int numMoved = len - index - 1; // 如果要刪除的數據正好是數組的尾部，直接刪除 if (numMoved == 0) setArray(Arrays.copyOf(elements, len - 1)); else { // 如果刪除的數據在數組的中間，分三步走 // 1. 設置新數組的長度減一，因為是減少一個元素 // 2. 從 0 拷貝到數組新位置 // 3. 從新位置拷貝到數組尾部 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(); } } ``` 步驟分為三步： 1. 加鎖； 2. 判斷刪除索引的位置，從而進行不同策略的拷貝； 3. 解鎖。代碼整體的結構風格也比較統一：鎖 + try finally +數組拷貝，鎖被 final 修飾的，保證了在加鎖過程中，鎖的內存地址肯定不會被修改，finally 保證鎖一定能夠被釋放，數組拷貝是為了刪除其中某個位置的元素。 ### 4 批量刪除數組的批量刪除很有意思，接下來我們來看下 CopyOnWriteArrayList 的批量刪除的實現過程： ``` // 批量刪除包含在 c 中的元素 public boolean removeAll(Collection<?> c) { if (c == null) throw new NullPointerException(); final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; // 說明數組有值，數組無值直接返回 false if (len != 0) { // newlen 表示新數組的索引位置，新數組中存在不包含在 c 中的元素 int newlen = 0; Object[] temp = new Object[len]; // 循環，把不包含在 c 里面的元素，放到新數組中 for (int i = 0; i < len; ++i) { Object element = elements[i]; // 不包含在 c 中的元素，從 0 開始放到新數組中 if (!c.contains(element)) temp[newlen++] = element; } // 拷貝新數組，變相的刪除了不包含在 c 中的元素 if (newlen != len) { setArray(Arrays.copyOf(temp, newlen)); return true; } } return false; } finally { lock.unlock(); } } ``` 從源碼中，我們可以看到，我們并不會直接對數組中的元素進行挨個刪除，而是先對數組中的值進行循環判斷，把我們不需要刪除的數據放到臨時數組中，最后臨時數組中的數據就是我們不需要刪除的數據。不知道大家有木有似曾相識的感覺，ArrayList 的批量刪除的思想也是和這個類似的，所以我們在需要刪除多個元素的時候，最好都使用這種批量刪除的思想，而不是采用在 for 循環中使用單個刪除的方法，單個刪除的話，在每次刪除的時候都會進行一次數組拷貝(刪除最后一個元素時不會拷貝)，很消耗性能，也耗時，會導致加鎖時間太長，并發大的情況下，會造成大量請求在等待鎖，這也會占用一定的內存。 ### 5 其它方法 #### 5.1 indexOf indexOf 方法的主要用處是查找元素在數組中的下標位置，如果元素存在就返回元素的下標位置，元素不存在的話返回 -1，不但支持 null 值的搜索，還支持正向和反向的查找，我們以正向查找為例，通過源碼來說明一下其底層的實現方式： ``` // o：我們需要搜索的元素 // elements：我們搜索的目標數組 // index：搜索的開始位置 // fence：搜索的結束位置 private static int indexOf(Object o, Object[] elements, int index, int fence) { // 支持對 null 的搜索 if (o == null) { for (int i = index; i < fence; i++) // 找到第一個 null 值，返回下標索引的位置 if (elements[i] == null) return i; } else { // 通過 equals 方法來判斷元素是否相等 // 如果相等，返回元素的下標位置 for (int i = index; i < fence; i++) if (o.equals(elements[i])) return i; } return -1; } ``` indexOf 方法在 CopyOnWriteArrayList 內部使用也比較廣泛，比如在判斷元素是否存在時（contains），在刪除元素方法中校驗元素是否存在時，都會使用到 indexOf 方法，indexOf 方法通過一次 for 循環來查找元素，我們在調用此方法時，需要注意如果找不到元素時，返回的是 -1，所以有可能我們會對這個特殊值進行判斷。 #### 5.2 迭代在 CopyOnWriteArrayList 類注釋中，明確說明了，在其迭代過程中，即使數組的原值被改變，也不會拋出 ConcurrentModificationException 異常，其根源在于數組的每次變動，都會生成新的數組，不會影響老數組，這樣的話，迭代過程中，根本就不會發生迭代數組的變動，我們截幾個圖說明一下： 1. 迭代是直接持有原有數組的引用，也就是說迭代過程中，一旦原有數組的值內存地址發生變化，必然會影響到迭代過程，下圖源碼演示的是 CopyOnWriteArrayList 的迭代方法，我們可以看到迭代器是直接持有原數組的引用： ![](https://img.kancloud.cn/39/66/3966d47d33cf0aceaeadf8e393d91e77_1144x591.jpg) 2. 我們寫了一個 demo，在 CopyOnWriteArrayList 迭代之后，往 CopyOnWriteArrayList 里面新增值，從下圖中可以看到在 CopyOnWriteArrayList 迭代之前，數組的內存地址是 962，請記住這個數字： ![](https://img.kancloud.cn/bf/f0/bff051de1bf8c9f43404b2c25009b6aa_1400x698.jpg) 3. CopyOnWriteArrayList 迭代之后，我們使用 add(“50”) 代碼給數組新增一個數據后，數組內存地址發生了變化，內存地址從原來的 962 變成了 968，這是因為 CopyOnWriteArrayList 的 add 操作，會生成新的數組，所以數組的內存地址發生了變化： ![](https://img.kancloud.cn/39/2f/392f9090c1808c1c561327d14b602532_1394x549.jpg) 4. 迭代繼續進行時，我們發現迭代器中的地址仍然是迭代之前引用的地址，是 962，而不是新的數組的內存地址： ![](https://img.kancloud.cn/03/85/03853c5132949bbd06ada25d584ea042_1575x739.jpg) 從上面 4 張截圖，我們可以得到迭代過程中，即使 CopyOnWriteArrayList 的結構發生變動了，也不會拋出 ConcurrentModificationException 異常的原因：CopyOnWriteArrayList 迭代持有的是老數組的引用，而 CopyOnWriteArrayList 每次的數據變動，都會產生新的數組，對老數組的值不會產生影響，所以迭代也可以正常進行。 ### 6 總結當我們需要在線程不安全場景下使用 List 時，建議使用 CopyOnWriteArrayList，CopyOnWriteArrayList 通過鎖 + 數組拷貝 + volatile 之間的相互配合，實現了 List 的線程安全，我們拋棄 Java 的這種實現，如果讓我們自己實現，你又將如何實現呢？