本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 提問。
前言
大家好，我是小彭。
在上一篇文章裡，我們聊到了ArrayList 的執行緒安全問題，其中提到了 CopyOnWriteArrayList 的解決方法。那麼 CopyOnWriteArrayList 是如何解決執行緒安全問題的，背後的設計思想是什麼，今天我們就圍繞這些問題展開。
本文原始碼基於 Java 8 CopyOnWriteArrayList。
小彭的 Android 交流群 02 群已經建立啦，歡迎加入~
思維導圖：
1。 回顧 ArrayList
ArrayList 是基於陣列實現的動態資料，是執行緒不安全的。例如，我們在遍歷 ArrayList 的時候，如果其他執行緒併發修改陣列（當然也不一定是被其他執行緒修改），在迭代器中就會觸發 fail-fast 機制，丟擲
ConcurrentModificationException
異常。
示例程式
List
要實現執行緒安全有 3 種方式：
方法 1 - 使用 Vector 容器：
Vector 是執行緒安全版本的陣列容器，它會在所有方法上增加 synchronized 關鍵字（過時，瞭解即可）；
方法 2 - 使用 Collections.synchronizedList 包裝類
方法 3 - 使用 CopyOnWriteArrayList 容器
Collections。synchronizedList 包裝類的原理很簡單，就是使用 synchronized 加鎖，原始碼摘要如下：
Collections。java
public static
如果我們將 ArrayList 替換為 CopyOnWriteArrayList，即使其他執行緒併發修改陣列，也不會丟擲
ConcurrentModificationException
異常，這是為什麼呢？
2。 CopyOnWriteArrayList 的特點
CopyOnWriteArrayList 和 ArrayList 都是基於陣列的動態陣列，封裝了運算元組時的搬運和擴容等邏輯。除此之外，CopyOnWriteArrayList 還是用了基於加鎖的 “讀寫分離” 和 “寫時複製” 的方案解決執行緒安全問題：
思想 1 - 讀寫分離（Read/Write Splitting）：
將對資源的讀取和寫入操作分離，使得讀取和寫入沒有依賴，在 “讀多寫少” 的場景中能有效減少資源競爭；
思想 2 - 寫時複製（CopyOnWrite，COW）：
在寫入資料時，不直接在原資料上修改，而是複製一份新資料後寫入到新資料，最後再替換到原資料的引用上。這個特性各有優缺點：
優點 1 - 延遲處理：
在沒有寫入操作時不會複製 / 分配資源，能夠避免瞬時的資源消耗。例如作業系統的 fork 操作也是一種寫時複製的思想；
優點 2 - 降低鎖顆粒度：
在寫的過程中，讀操作不會被影響，讀操作也不需要加鎖，鎖的顆粒度從整個列表降低為寫操作；
缺點 1 - 弱資料一致性：
在讀的過程中，如果資料被其他執行緒修改，是無法實時感知到最新的資料變化的；
缺點 2 - 有記憶體壓力：
在寫操作中需要複製原陣列，在複製的過程中記憶體會同時存在兩個陣列物件（只是引用，陣列元素的物件還是隻有一份），會帶來記憶體佔用和垃圾回收的壓力。如果是 “寫多讀少” 的場景，就不適合。
所以，使用 CopyOnWriteArrayList 的場景一定要保證是 “讀多寫少” 且資料量不大的場景，而且在寫入資料的時候，要做到批次操作。否則每個寫入操作都會觸發一次複製，想想就可怕。舉 2 個例子：
例如批次寫入一組資料，要使用 addAll 方法 批次寫入；
例如在做排序時，要先輸出為 ArrayList，在 ArrayList 上完成排序後再寫回 CopyOnWriteArrayList。
3。 CopyOnWriteArrayList 原始碼分析
這一節，我們來分析 CopyOnWriteArrayList 中主要流程的原始碼。
3。1 CopyOnWriteArrayList 的屬性
ArrayList 的屬性很好理解，底層是一個 Object 陣列，我要舉手提問 ♀️：
疑問 1：
為什麼 array 欄位要使用 volatile 關鍵字？
// 鎖final transient ReentrantLock lock = new ReentrantLock（）；// 在 Java 11 中，ReentrantLock 被替換為 synchronized 鎖// The lock protecting all mutators。 （We have a mild preference for builtin monitors over ReentrantLock when either will do。）final transient Object lock = new Object（）；// 底層陣列// 疑問 1：為什麼 array 要使用 volatile 關鍵字？private transient volatile Object［］ array；
這個問題我們在分析原始碼的過程中回答。有了 ArrayList 的分析基礎，疑問也變少了，CopyOnWriteArrayList 真香。
3。2 CopyOnWriteArrayList 的構造方法
構造器的原始碼不難，但小朋友總有太多的問號，舉手提問 ♀️：
疑問 2：為什麼 CopyOnWriteArrayList 不提供初始化容量的構造器？
這是因為 CopyOnWriteArrayList 建議我們使用批次操作寫入資料。如果提供了帶初始化容量的構造器，意味著開發者預期會一個個地寫入資料，這不符合 CopyOnWriteArrayList 的正確使用方法。所以，不提供這個構造器才是合理的。
疑問 3：為什麼要把 E[] 型別的入參轉化為 Object[] 型別？
如果不轉化陣列型別，那麼在 toArray（） 方法返回的陣列中插入 Object 型別物件時，會丟擲
ArrayStoreException
。
提示：
這個問題與 “奇怪” 分支的原因相同，具體分析可以看講 《Java 面試題：ArrayList 可以完全替代陣列嗎？》 的文章中，這裡不重複講了。
// 疑問 2：為什麼 CopyOnWriteArrayList 不提供預初始化容量的構造器？// 無參構造方法public CopyOnWriteArrayList（） { // 建立空陣列 setArray（new Object［0］）；}// 帶集合的構造方法public CopyOnWriteArrayList（Collection<？ extends E> c） { Object［］ elements； if （c。getClass（） == CopyOnWriteArrayList。class） elements = （（CopyOnWriteArrayList<？>）c）。getArray（）； else { elements = c。toArray（）； // 這個“奇怪”的分支在 ArrayList 文章中分析過，去看看 if （elements。getClass（） ！= Object［］。class） elements = Arrays。copyOf（elements， elements。length， Object［］。class）； } setArray（elements）；}// 帶陣列的構造方法public CopyOnWriteArrayList（E［］ toCopyIn） { // 疑問 3：為什麼要把 E［］ 型別的入參轉化為 Object［］ 型別 setArray（Arrays。copyOf（toCopyIn， toCopyIn。length， *Object［］*。class））；}final Object［］ getArray（） { return array；}final void setArray（Object［］ a） { array = a；}public Object［］ toArray（） { Object［］ elements = getArray（）； return Arrays。copyOf（elements， elements。length）；}
3。3 CopyOnWriteArrayList 的寫方法
我們將 CopyOnWriteArrayList 的新增、刪除和修改方法統一為 “寫方法”，三種寫方法的模板其實是一樣的：
1、在寫入之前先獲取物件的鎖；
2、複製新陣列；
3、在新陣列上完成寫入操作；
4、將新陣列設定為底層陣列；
5、釋放物件的鎖。
小朋友總是有太多問號，舉手提問 ♀️：
疑問 4：在新增方法中，為什麼擴容只增大 1 容量，而 ArrayList 會增大 1.5 倍？
這還是因為 CopyOnWriteArrayList 建議我們使用批次操作寫入資料。ArrayList 額外擴容 1。5 倍是為了避免每次 add 都擴容，而 CopyOnWriteArrayList 並不建議一個個地新增資料，而是建議批次操作寫入資料，例如 addAll 方法。所以，CopyOnWriteArrayList 不額外擴容才是合理的。
另外，網上有觀點看到 CopyOnWriteArrayList 沒有限制陣列最大容量，
就說 CopyOnWriteArrayList 是無界的，沒有容量限制
。這顯然太表面了。陣列的長度限制是被虛擬機器固化的，CopyOnWriteArrayList 沒有限制的原因是：它沒有做額外擴容，而且不適合大資料的場景，所以沒有限制的必要。
最後還剩下 1 個問題：
疑問 1：為什麼 array 欄位要使用 volatile 關鍵字？
volatile 變數是 Java 輕量級的執行緒同步原語，volatile 變數的讀取和寫入操作中會加入記憶體屏障，能夠保證變數寫入的記憶體可見性，保證一個執行緒的寫入能夠被另一個執行緒觀察到。
新增方法
// 在陣列尾部新增元素public boolean add（E e） { final ReentrantLock lock = this。lock； // 獲取鎖 lock。lock（）； // 複製新陣列 Object［］ elements = getArray（）； int len = elements。length； // 疑問 4：在新增方法中，為什麼擴容只增大 1 容量，而 ArrayList 會增大 1。5 倍？ Object［］ newElements = Arrays。copyOf（elements， len + 1 /* 容量 + 1*/）； // 在新陣列上新增元素 newElements［len］ = e； // 設定新陣列 setArray（newElements）； // 釋放鎖 lock。unlock（）； return true；}// 在陣列尾部新增元素public void add（int index， E element） { // 原理相同，省略 。。。}// 批次在陣列尾部新增元素public boolean addAll（Collection<？ extends E> c） { // 原理相同，省略 。。。}
修改方法
// 修改陣列元素public E set（int index， E element） { final ReentrantLock lock = this。lock； // 獲取鎖 lock。lock（）； // 舊元素 Object［］ elements = getArray（）； E oldValue = get（elements， index）； if （oldValue ！= element） { // 複製新陣列 int len = elements。length； Object［］ newElements = Arrays。copyOf（elements， len）； // 在新陣列上新增元素 newElements［index］ = element； // 設定新陣列 setArray（newElements）； } else { // Not quite a no-op； ensures volatile write semantics setArray（elements）； } // 釋放鎖 lock。unlock（）； // 返回舊資料 return oldValue；}
刪除方法
// 刪除陣列元素public E remove（int index） { final ReentrantLock lock = this。lock； // 獲取鎖 lock。lock（）； 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 { // 刪除中間元素 // 複製新陣列 Object［］ newElements = new Object［len - 1］； System。arraycopy（elements， 0， newElements， 0， index）； System。arraycopy（elements， index + 1， newElements， index， numMoved）； // 設定新陣列 setArray（newElements）； } // 釋放鎖 lock。unlock（）； // 返回舊資料 return oldValue；}
3。4 CopyOnWriteArrayList 的讀取方法
可以看到讀取方法並沒有加鎖。
private E get（Object［］ a， int index） { return （E） a［index］；}public E get（int index） { return get（getArray（）， index）；}public boolean contains（Object o） { Object［］ elements = getArray（）； return indexOf（o， elements， 0， elements。length） >= 0；}
3。5 CopyOnWriteArrayList 的迭代器
CopyOnWriteArrayList 的迭代器
COWIterator
是
“弱資料一致性的”
，所謂資料一致性問題討論的是同一份資料在多個副本之間的一致性問題，你也可以理解為多個副本的狀態一致性問題。例如記憶體與多核心 Cache 副本之間的一致性，或者資料在主從資料庫之間的一致性。
提示：
關於 “資料一致性和順序一致性” 的區別，在小彭的計算機組成原理專欄討論過 《已經有 MESI 協議，為什麼還需要 volatile 關鍵字？》，去看看。
為什麼是
“弱”
的呢？這是因為
COWIterator
迭代器會持有 CopyOnWriteArrayList
“底層陣列”
的引用，而 CopyOnWriteArrayList 的寫入操作是寫入到新陣列，因此
COWIterator
是無法感知到的，除非重新建立迭代器。
相較之下，ArrayList 的迭代器是透過持有
“外部類引用”
的方式訪問 ArrayList 的底層陣列，因此在 ArrayList 上的寫入操作會實時被迭代器觀察到。
CopyOnWriteArrayList。java
// 注意看：有 static 關鍵字，直接引用底層陣列static final class COWIterator
ArrayList。java
// 注意看：沒有 static 關鍵字，透過外部類引用來訪問底層陣列private class Itr implements Iterator
3。6 CopyOnWriteArraySet 的序列化過程
與 ArrayList 類似，CopyOnWriteArraySet 也重寫了 JDK 序列化的邏輯，只把 elements 陣列中有效元素的部分序列化，而不會序列化整個陣列。
同時，
ReentrantLock
物件是鎖物件，序列化沒有意義。在反序列化時，會透過
resetLock（）
設定一個新的
ReentrantLock
物件。
// 序列化過程private void writeObject（java。io。ObjectOutputStream s） throws java。io。IOException { s。defaultWriteObject（）； Object［］ elements = getArray（）； // 寫入陣列長度 s。writeInt（elements。length）； // 寫入有效元素 for （Object element ： elements） s。writeObject（element）；}// 反序列化過程private void readObject（java。io。ObjectInputStream s） throws java。io。IOException， ClassNotFoundException { s。defaultReadObject（）； // 設定 ReentrantLock 物件 resetLock（）； // 讀取陣列長度 int len = s。readInt（）； SharedSecrets。getJavaOISAccess（）。checkArray（s， Object［］。class， len）； // 建立底層陣列 Object［］ elements = new Object［len］； // 讀取陣列物件 for （int i = 0； i < len； i++） elements［i］ = s。readObject（）； // 設定新陣列 setArray（elements）；}// 疑問 5：resetLock（） 方法不好理解，解釋一下？private void resetLock（） { // 等價於帶 Volatile 語義的 this。lock = new ReentrantLock（） UNSAFE。putObjectVolatile（this， lockOffset， new ReentrantLock（））；}// Unsafe APIprivate static final sun。misc。Unsafe UNSAFE；// lock 欄位在物件例項資料中的偏移量private static final long lockOffset；static { // 這三行的作用：lock 欄位在物件例項資料中的偏移量 UNSAFE = sun。misc。Unsafe。getUnsafe（）； Class<？> k = CopyOnWriteArrayList。class； lockOffset = UNSAFE。objectFieldOffset（k。getDeclaredField（“lock”））；}
小朋友又是有太多問號，舉手提問 ♀️：
♀️
疑問 5：resetLock() 方法不好理解，解釋一下？
在 static 程式碼塊中，會使用 Unsafe API 獲取 CopyOnWriteArrayList 的
“lock 欄位在物件例項資料中的偏移量”
。由於欄位的偏移是全域性固定的，所以這個偏移量可以記錄在 static 欄位
lockOffset
中。
在
resetLock（）
中，透過 UnSafe API putObjectVolatile 將新建的 ReentrantLock 物件設定到 CopyOnWriteArrayList 的 lock 欄位中，等價於帶 volatile 語義的
this。lock = new ReentrantLock（）
，保證這個欄位的寫入具備記憶體可見性。
欄位的偏移量是什麼意思呢？簡單來說，普通物件和 Class 物件的例項資料區域是不同的：
1、普通物件：
包括當前類宣告的例項欄位以及父類宣告的例項欄位，不包括類的靜態欄位。UnSafe API objectFieldOffset（Filed） 就是獲取了引數 Filed 在例項資料中的偏移量，後續就可以透過這個偏移量為欄位賦值；
2、Class 物件：
包括當前類宣告的靜態欄位和方法表等。
物件記憶體佈局
提示：
關於欄位的偏移量，我們在 《物件的記憶體分為哪幾個部分？》 這篇文章裡討論過，去看看。
3。7 CopyOnWriteArraySet 的 clone（） 過程
CopyOnWriteArraySet 的 clone（） 很巧妙。按照正常的思維，CopyOnWriteArraySet 中的
array
陣列是引用型別，因此在 clone（） 中需要實現深複製，否則原物件與克隆物件就會相互影響。但事實上，
array
陣列並沒有被深複製，哇點解啊？
♀️
疑問 6：為什麼 array 陣列沒有深複製？
這就是因為 CopyOnWrite 啊！沒有 Write 為什麼要 Copy 呢？（我覺得已經提醒到位了，只要你仔細閱讀前文對 CopyOnWrite 的論證，你一定會懂的。要是是在不懂，私信我吧~）
public Object clone（） { try { @SuppressWarnings（“unchecked”） // 疑問 6：為什麼 array 陣列沒有深複製？ CopyOnWriteArrayList
4。 CopyOnWriteArraySet 原始碼分析
在 Java 標準庫中，還提供了一個使用 COW 思想的 Set 集合 —— CopyOnWriteArraySet。
CopyOnWriteArraySet 和 HashSet 都是繼承於 AbstractSet 的，但 CopyOnWriteArraySet 是基於 CopyOnWriteArrayList 動態陣列的，並沒有使用雜湊思想。而 HashSet 是基於 HashMap 散列表的，能夠實現 O（1） 查詢。
4。1 CopyOnWriteArraySet 的構造方法
看一下 CopyOnWriteArraySet 的構造方法，底層就是有一個 CopyOnWriteArrayList 動態陣列。
CopyOnWriteArraySet。java
public class CopyOnWriteArraySet
4。2 CopyOnWriteArraySet 的操作方法
CopyOnWriteArraySet 的方法基本上都是交給
CopyOnWriteArraySet
代理的，由於沒有使用雜湊思想，所以操作的時間複雜度是 O（n）。
CopyOnWriteArraySet。java
public boolean add（E e） { return al。addIfAbsent（e）；}public boolean contains（Object o） { return al。contains（o）；}
CopyOnWriteArrayList。java
public boolean addIfAbsent（E e） { Object［］ snapshot = getArray（）； return indexOf（e， snapshot， 0， snapshot。length） >= 0 ？ false ： addIfAbsent（e， snapshot）；}public boolean contains（Object o） { Object［］ elements = getArray（）； return indexOf（o， elements， 0， elements。length） >= 0；}// 透過線性掃描匹配元素位置，而不是計算雜湊匹配，時間複雜度是 O（n）private static int indexOf（Object o， Object［］ elements， int index， int fence） { if （o == null） { for （int i = index； i < fence； i++） if （elements［i］ == null） return i； } else { for （int i = index； i < fence； i++） if （o。equals（elements［i］）） return i； } return -1；}
5。 總結
1、CopyOnWriteArrayList 和 ArrayList 都是基於陣列的動態陣列，封裝了運算元組時的搬運和擴容等邏輯；
2、CopyOnWriteArrayList 還是 “讀寫分離” 和 “寫時複製” 的方案解決執行緒安全問題；
3、使用 CopyOnWriteArrayList 的場景一定要保證是 “讀多寫少” 且資料量不大的場景，而且在寫入資料的時候，要做到批次操作；
4、CopyOnWriteArrayList 的迭代器是 “弱資料一致性的” 的，迭代器會持有 “底層陣列” 的引用，而 CopyOnWriteArrayList 的寫入操作是寫入到新陣列，因此迭代器是無法感知到的；
5、CopyOnWriteArraySet 是基於 CopyOnWriteArrayList 動態陣列的，並沒有使用雜湊思想。
