面試官扎心一問：知道 CopyOnWriteArrayList 嗎？

點擊上方“Java專欄”，選擇“置頂或者星標”

寫入時復制（CopyOnWrite，簡稱COW）思想是計算機程序設計領域中的一種優(yōu)化策略。其核心思想是，如果有多個調用者（Callers）同時要求相同的資源（如內(nèi)存或者是磁盤上的數(shù)據(jù)存儲），他們會共同獲取相同的指針指向相同的資源，直到某個調用者視圖修改資源內(nèi)容時，系統(tǒng)才會真正復制一份專用副本（private copy）給該調用者，而其他調用者所見到的最初的資源仍然保持不變。這過程對其他的調用者都是透明的（transparently）。此做法主要的優(yōu)點是如果調用者沒有修改資源，就不會有副本（private copy）被創(chuàng)建，因此多個調用者只是讀取操作時可以共享同一份資源。

CopyOnWriteArrayList的實現(xiàn)原理

在使用CopyOnWriteArrayList之前，我們先閱讀其源碼了解下它是如何實現(xiàn)的。以下代碼是向CopyOnWriteArrayList中add方法的實現(xiàn)（向CopyOnWriteArrayList里添加元素），可以發(fā)現(xiàn)在添加的時候是需要加鎖的，否則多線程寫的時候會Copy出N個副本出來。

/**
?????*?Appends?the?specified?element?to?the?end?of?this?list.
?????*
?????*?@param?e?element?to?be?appended?to?this?list
?????*?@return?true?(as?specified?by?{@link?Collection#add})
?????*/
????public?boolean?add(E?e)?{
????final?ReentrantLock?lock?=?this.lock;
????lock.lock();
????try?{
????????Object[]?elements?=?getArray();
????????int?len?=?elements.length;
????????Object[]?newElements?=?Arrays.copyOf(elements,?len?+?1);
????????newElements[len]?=?e;
????????setArray(newElements);
????????return?true;
????}?finally?{
????????lock.unlock();
????}
????}

讀的時候不需要加鎖，如果讀的時候有多個線程正在向CopyOnWriteArrayList添加數(shù)據(jù)，讀還是會讀到舊的數(shù)據(jù)，因為寫的時候不會鎖住舊的CopyOnWriteArrayList。

public?E?get(int?index)?{
????return?get(getArray(),?index);
}

JDK中并沒有提供CopyOnWriteMap，我們可以參考CopyOnWriteArrayList來實現(xiàn)一個，基本代碼如下：

import?java.util.Collection;
import?java.util.Map;
import?java.util.Set;
?
public?class?CopyOnWriteMap<K,?V>?implements?Map<K,?V>,?Cloneable?{
????private?volatile?Map?internalMap;
?
????public?CopyOnWriteMap()?{
????????internalMap?=?new?HashMap();
????}
?
????public?V?put(K?key,?V?value)?{
?
????????synchronized?(this)?{
????????????Map?newMap?=?new?HashMap(internalMap);
????????????V?val?=?newMap.put(key,?value);
????????????internalMap?=?newMap;
????????????return?val;
????????}
????}
?
????public?V?get(Object?key)?{
????????return?internalMap.get(key);
????}
?
????public?void?putAll(Map?newData)?{
????????synchronized?(this)?{
????????????Map?newMap?=?new?HashMap(internalMap);
????????????newMap.putAll(newData);
????????????internalMap?=?newMap;
????????}
????}
}

實現(xiàn)很簡單，只要了解了CopyOnWrite機制，我們可以實現(xiàn)各種CopyOnWrite容器，并且在不同的應用場景中使用。

幾個要點

• 實現(xiàn)了List接口
• 內(nèi)部持有一個ReentrantLock lock = new ReentrantLock();
• 底層是用volatile transient聲明的數(shù)組 array
• 讀寫分離，寫時復制出一個新的數(shù)組，完成插入、修改或者移除操作后將新數(shù)組賦值給array

** volatile （揮發(fā)物、易變的）** ：變量修飾符，只能用來修飾變量。volatile修飾的成員變量在每次被線程訪問時，都強迫從共享內(nèi)存中重讀該成員變量的值。而且，當成員變量發(fā)生變 化時，強迫線程將變化值回寫到共享內(nèi)存。這樣在任何時刻，兩個不同的線程總是看到某個成員變量的同一個值。

增刪改查

1）增

public?boolean?add(E?e)?{
????final?ReentrantLock?lock?=?this.lock;
????//獲得鎖
????lock.lock();
????try?{
????????Object[]?elements?=?getArray();
????????int?len?=?elements.length;
????????//復制一個新的數(shù)組
????????Object[]?newElements?=?Arrays.copyOf(elements,?len?+?1);
????????//插入新值
????????newElements[len]?=?e;
????????//將新的數(shù)組指向原來的引用
????????setArray(newElements);
????????return?true;
????}?finally?{
????????//釋放鎖
????????lock.unlock();
????}
}

???
public?void?add(int?index,?E?element)?{
????final?ReentrantLock?lock?=?this.lock;
????lock.lock();
????try?{
????????Object[]?elements?=?getArray();
????????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)
????????????newElements?=?Arrays.copyOf(elements,?len?+?1);
????????else?{
????????????newElements?=?new?Object[len?+?1];
????????????System.arraycopy(elements,?0,?newElements,?0,?index);
????????????System.arraycopy(elements,?index,?newElements,?index?+?1,
?????????????????????????????numMoved);
????????}
????????newElements[index]?=?element;
????????setArray(newElements);
????}?finally?{
????????lock.unlock();
????}
}

2）刪

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)
????????????//如果刪除的元素是最后一個，直接復制該元素前的所有元素到新的數(shù)組
????????????setArray(Arrays.copyOf(elements,?len?-?1));
????????else?{
????????????//創(chuàng)建新的數(shù)組
????????????Object[]?newElements?=?new?Object[len?-?1];
????????????//將index+1至最后一個元素向前移動一格
????????????System.arraycopy(elements,?0,?newElements,?0,?index);
????????????System.arraycopy(elements,?index?+?1,?newElements,?index,
?????????????????????????????numMoved);
????????????setArray(newElements);
????????}
????????return?oldValue;
????}?finally?{
????????lock.unlock();
????}
}

3）改

public?E?set(int?index,?E?element)?{
????final?ReentrantLock?lock?=?this.lock;
????//獲得鎖
????lock.lock();
????try?{
????????Object[]?elements?=?getArray();
????????E?oldValue?=?get(elements,?index);

????????if?(oldValue?!=?element)?{
????????????int?len?=?elements.length;
????????????//創(chuàng)建新數(shù)組
????????????Object[]?newElements?=?Arrays.copyOf(elements,?len);
????????????//替換元素
????????????newElements[index]?=?element;
????????????//將新數(shù)組指向原來的引用
????????????setArray(newElements);
????????}?else?{
????????????//?Not?quite?a?no-op;?ensures?volatile?write?semantics
????????????setArray(elements);
????????}
????????return?oldValue;
????}?finally?{
????????//釋放鎖
????????lock.unlock();
????}
}

4）查

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

CopyOnWrite的應用場景

CopyOnWrite并發(fā)容器用于讀多寫少的并發(fā)場景。比如白名單，黑名單，商品類目的訪問和更新場景，假如我們有一個搜索網(wǎng)站，用戶在這個網(wǎng)站的搜索框中，輸入關鍵字搜索內(nèi)容，但是某些關鍵字不允許被搜索。這些不能被搜索的關鍵字會被放在一個黑名單當中，黑名單每天晚上更新一次。當用戶搜索時，會檢查當前關鍵字在不在黑名單當中，如果在，則提示不能搜索。實現(xiàn)代碼如下：

import?java.util.Map;
?
import?com.ifeve.book.forkjoin.CopyOnWriteMap;
?
/**
?*?黑名單服務
?*
?*?@author?fangtengfei
?*
?*/
public?class?BlackListServiceImpl?{
?
????private?static?CopyOnWriteMap?blackListMap?=?new?CopyOnWriteMap(
????????????1000);
?
????public?static?boolean?isBlackList(String?id)?{
????????return?blackListMap.get(id)?==?null???false?:?true;
????}
?
????public?static?void?addBlackList(String?id)?{
????????blackListMap.put(id,?Boolean.TRUE);
????}
?
????/**
?????*?批量添加黑名單
?????*
?????*?@param?ids
?????*/
????public?static?void?addBlackList(Map?ids)?{
????????blackListMap.putAll(ids);
????}
?
}

代碼很簡單，但是使用CopyOnWriteMap需要注意兩件事情：

1. 減少擴容開銷。根據(jù)實際需要，初始化CopyOnWriteMap的大小，避免寫時CopyOnWriteMap擴容的開銷。

2. 使用批量添加。因為每次添加，容器每次都會進行復制，所以減少添加次數(shù)，可以減少容器的復制次數(shù)。如使用上面代碼里的addBlackList方法。

CopyOnWrite的缺點

CopyOnWrite容器有很多優(yōu)點，但是同時也存在兩個問題，即內(nèi)存占用問題和數(shù)據(jù)一致性問題。所以在開發(fā)的時候需要注意一下。

「內(nèi)存占用問題」。因為CopyOnWrite的寫時復制機制，所以在進行寫操作的時候，內(nèi)存里會同時駐扎兩個對象的內(nèi)存，舊的對象和新寫入的對象（注意:在復制的時候只是復制容器里的引用，只是在寫的時候會創(chuàng)建新對象添加到新容器里，而舊容器的對象還在使用，所以有兩份對象內(nèi)存）。如果這些對象占用的內(nèi)存比較大，比如說200M左右，那么再寫入100M數(shù)據(jù)進去，內(nèi)存就會占用300M，那么這個時候很有可能造成頻繁的Yong GC和Full GC。之前我們系統(tǒng)中使用了一個服務由于每晚使用CopyOnWrite機制更新大對象，造成了每晚15秒的Full GC，應用響應時間也隨之變長。

「針對內(nèi)存占用問題」，可以通過壓縮容器中的元素的方法來減少大對象的內(nèi)存消耗，比如，如果元素全是10進制的數(shù)字，可以考慮把它壓縮成36進制或64進制。或者不使用CopyOnWrite容器，而使用其他的并發(fā)容器，如ConcurrentHashMap。

「數(shù)據(jù)一致性問題」。CopyOnWrite容器只能保證數(shù)據(jù)的最終一致性，不能保證數(shù)據(jù)的實時一致性。所以如果你希望寫入的的數(shù)據(jù)，馬上能讀到，請不要使用CopyOnWrite容器。

CopyOnWriteArrayList為什么并發(fā)安全且性能比Vector好

我知道Vector是增刪改查方法都加了synchronized，保證同步，但是每個方法執(zhí)行的時候都要去獲得鎖，性能就會大大下降，而CopyOnWriteArrayList 只是在增刪改上加鎖，但是讀不加鎖，在讀方面的性能就好于Vector，CopyOnWriteArrayList支持讀多寫少的并發(fā)情況。