面試：知道 CopyOnWriteArrayList 嗎？

寫入時(shí)復(fù)制（CopyOnWrite）思想

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

CopyOnWriteArrayList的實(shí)現(xiàn)原理

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

/**
?????*?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();
????}
????}

讀的時(shí)候不需要加鎖，如果讀的時(shí)候有多個(gè)線程正在向CopyOnWriteArrayList添加數(shù)據(jù)，讀還是會(huì)讀到舊的數(shù)據(jù)，因?yàn)閷懙臅r(shí)候不會(huì)鎖住舊的CopyOnWriteArrayList。

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

JDK中并沒(méi)有提供CopyOnWriteMap，我們可以參考CopyOnWriteArrayList來(lái)實(shí)現(xiàn)一個(gè)，基本代碼如下：

import?java.util.Collection;
import?java.util.Map;
import?java.util.Set;
?
public?class?CopyOnWriteMap?implements?Map,?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;
????????}
????}
}

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

幾個(gè)要點(diǎn)

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

「注：」

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

增刪改查

1）增

public?boolean?add(E?e)?{
????final?ReentrantLock?lock?=?this.lock;
????//獲得鎖
????lock.lock();
????try?{
????????Object[]?elements?=?getArray();
????????int?len?=?elements.length;
????????//復(fù)制一個(gè)新的數(shù)組
????????Object[]?newElements?=?Arrays.copyOf(elements,?len?+?1);
????????//插入新值
????????newElements[len]?=?e;
????????//將新的數(shù)組指向原來(lái)的引用
????????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?????????????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)
????????????//如果刪除的元素是最后一個(gè)，直接復(fù)制該元素前的所有元素到新的數(shù)組
????????????setArray(Arrays.copyOf(elements,?len?-?1));
????????else?{
????????????//創(chuàng)建新的數(shù)組
????????????Object[]?newElements?=?new?Object[len?-?1];
????????????//將index+1至最后一個(gè)元素向前移動(dòng)一格
????????????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ù)組指向原來(lái)的引用
????????????setArray(newElements);
????????}?else?{
????????????//?Not?quite?a?no-op;?ensures?volatile?write?semantics
????????????setArray(elements);
????????}
????????return?oldValue;
????}?finally?{
????????//釋放鎖
????????lock.unlock();
????}
}

4）查

//直接獲取index對(duì)應(yīng)的元素
public?E?get(int?index)?{return?get(getArray(),?index);}
private?E?get(Object[]?a,?int?index)?{return?(E)?a[index];}

CopyOnWrite的應(yīng)用場(chǎng)景

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

import?java.util.Map;
?
import?com.ifeve.book.forkjoin.CopyOnWriteMap;
?
/**
?*?黑名單服務(wù)
?*
?*?@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);
????}
?
}

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

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

2. 使用批量添加。因?yàn)槊看翁砑?，容器每次都?huì)進(jìn)行復(fù)制，所以減少添加次數(shù)，可以減少容器的復(fù)制次數(shù)。如使用上面代碼里的addBlackList方法。

CopyOnWrite的缺點(diǎn)

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

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

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

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

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

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