5 Java并發(fā)集合
5.1 引言
在前幾章中，我們介紹了Java集合的內(nèi)容，具體包括ArrayList、HashSet、HashMap、ArrayQueue等實(shí)現(xiàn)類。
不知道各位有沒有發(fā)現(xiàn)，上述集合都有一個共同的特點(diǎn)，那就是線程不安全性，在并發(fā)情況下都不能保證數(shù)據(jù)的一致性。（當(dāng)然，這個集合必須是共享了，所以才會有數(shù)據(jù)不一致）
所以，當(dāng)我們在進(jìn)行并發(fā)任務(wù)時候，共享了一個不適用于并發(fā)的數(shù)據(jù)結(jié)構(gòu)，也就是將此數(shù)據(jù)結(jié)構(gòu)變成了程序中的成員變量，那么我們將會遇到數(shù)據(jù)的不一致，進(jìn)而影響到我們程序的運(yùn)行。
為了應(yīng)對并發(fā)場景的出現(xiàn)，Java在后續(xù)迭代過程中（具體應(yīng)該是JDK1.5版本），推出了java.util.concurrent包。該包的出現(xiàn)，讓Java并發(fā)編程變得更加輕松，幫助開發(fā)者編寫更加高效、易維護(hù)、結(jié)構(gòu)清晰的程序。
在java.util.concurrent包中，不但包含了我們本篇要說的線程安全的集合，還涉及到了多線程、CAS、線程鎖等相關(guān)內(nèi)容，可以說是完整覆蓋了Java并發(fā)的知識棧。
對于Java開發(fā)人員來說，學(xué)好java.util.concurrent包下的內(nèi)容，是一個必備的功課，也是逐漸提升自己的一個重要階段。
5.2 并發(fā)集合實(shí)現(xiàn)1
JDK1.5的出現(xiàn)，對于集合并發(fā)編程來說，java developer有了更多的選擇。不過，在JDK1.5之前，Java也還是提供了一些解決方案。
（1）最為簡單直接的就是在程序中我們自己對共享變量進(jìn)行加鎖。不過，缺點(diǎn)也顯而易見，手動實(shí)現(xiàn)線程安全間接增加了程序的復(fù)雜度，以及代碼出錯的概率---例如：線程死鎖的產(chǎn)生；
（2）我們還可以使用Java集合框架中的Vector、Hashtable實(shí)現(xiàn)類，這兩個類都是線程安全的。不過，Java已不提倡使用。
（3）此外，我們還可以使用集合工具類--Collections，通過調(diào)用其中的靜態(tài)方法，來得到線程安全的集合。具體方法，包括：Collections.synchronizedCollection(Collection<T> c)、Collections.synchronizedSet(Set<T> s)、Collections.synchronizedList(List<T>)、Collections.synchronizedMap(Map<K, V>)。
究其原理，他們都是通過在方法中加synchronized同步鎖來實(shí)現(xiàn)的。我們知道synchronized鎖的開銷較大，在程序中不建議使用。
雖然，這三種方式可以實(shí)現(xiàn)線程安全的集合，但是都有顯而易見的缺點(diǎn)，而且也不是我們今天所關(guān)注的重點(diǎn)。
接下來，就來具體看下java.util.concurrent包中的實(shí)現(xiàn)；
5.2 并發(fā)集合實(shí)現(xiàn)2
在java.util.concurrent包中，提供了兩種類型的并發(fā)集合：一種是阻塞式，另一種是非阻塞式。
阻塞式集合：當(dāng)集合已滿或?yàn)榭諘r，被調(diào)用的添加（滿）、移除（空）方法就不能立即被執(zhí)行，調(diào)用這個方法的線程將被阻塞，一直等到該方法可以被成功執(zhí)行。
非阻塞式集合：當(dāng)集合已滿或?yàn)榭諘r，被調(diào)用的添加（滿）、移除（空）方法就不能立即被執(zhí)行，調(diào)用這個方法的線程不會被阻塞，而是直接則返回null或拋出異常。
下面，就來看下concurrent包下，到底存在了哪些線程安全的集合：
Collection集合：
List：
CopyOnWriteArrayList
Set：
CopyOnWriteArraySet
ConcurrentSkipListSet
Queue：
BlockingQueue:
LinkedBlockingQueue
DelayQueue
PriorityBlockingQueue
ConcurrentLinkedQueue
TransferQueue:
LinkedTransferQueue
BlockingDeque:
LinkedBlockingDeque
ConcurrentLinkedDeque
Map集合：
Map:
ConcurrentMap:
ConcurrentHashMap
ConcurrentSkipListMap
ConcurrentNavigableMap
通過以上可以看出，java.util.concurrent包為每一類集合都提供了線程安全的實(shí)現(xiàn)。
接下來，我們做具體分析！
5.3 List并發(fā)集合（CopyOnWrite機(jī)制）
- CopyOnWrite機(jī)制
CopyOnWrite（簡稱COW），是計(jì)算機(jī)程序設(shè)計(jì)領(lǐng)域中的一種優(yōu)化策略，也是一種思想--即寫入時復(fù)制思想。
那么，什么是寫入時復(fù)制思想呢？就是當(dāng)有多個調(diào)用者同時去請求一個資源時(可以是內(nèi)存中的一個數(shù)據(jù))，當(dāng)其中一個調(diào)用者要對資源進(jìn)行修改，系統(tǒng)會copy一個副本給該調(diào)用者，讓其進(jìn)行修改；而其他調(diào)用者所擁有資源并不會由于該調(diào)用者對資源的改動而發(fā)生改變。這就是寫入時復(fù)制思想；
如果用代碼來描述的話，就是創(chuàng)建多個線程，在每個線程中如果修改共享變量，那么就將此變量進(jìn)行一次拷貝操作，每次的修改都是對副本進(jìn)行。
代碼如下：
public class CopyOnWriteThread implements Runnable {
private List<String> list = new ArrayList<String>();
public void run() {
List<String> newList = new ArrayList<String>();
newList.add("hello");
Collections.copy(newList,list);
}
//創(chuàng)建線程：
public static void main(String[] agrs){
Thread thread1 = new Thread(new CopyOnWriteThread());
thread1.start();
Thread thread2 = new Thread(new CopyOnWriteThread());
thread2.start();
}
}
從JDK1.5開始，java.util.concurrent包中提供了兩個CopyOnWrite機(jī)制容器，分別為CopyOnWriteArrayList和CopyOnWriteArraySet。
CopyOnWriteArrayList，直白翻譯過來就是“當(dāng)寫入時復(fù)制ArrayList集合”。
簡單的理解，就是當(dāng)我們往CopyOnWrite容器中添加元素時，不直接操作當(dāng)前容器，而是先將容器進(jìn)行Copy，然后對Copy出的新容器進(jìn)行修改，修改后，再將原容器的引用指向新的容器，即完成了整個修改操作；
- CopyOnWriteArrayList的實(shí)現(xiàn)原理
CopyOnWriteArrayList，線程安全的集合，這一點(diǎn)主要區(qū)別與ArrayList。
通常來說，線程安全都是通過加鎖實(shí)現(xiàn)的，那么CopyOnWriteArrayList是如何實(shí)現(xiàn)？
CopyOnWriteArrayList通過使用ReentrantLock鎖來實(shí)現(xiàn)線程安全：
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8673264195747942595L;
//ReentrantLock鎖，沒有使用Synchronized
transient final ReentrantLock lock = new ReentrantLock();
//集合底層數(shù)據(jù)結(jié)構(gòu)：數(shù)組（volatile修飾共享可見）
private volatile transient Object[] array;
}
CopyOnWriteArrayList在添加、獲取元素時，使用getArray（）獲取底層數(shù)組對象，獲取此時集合中的數(shù)組對象；使用setArray（）設(shè)置底層數(shù)組，將原有數(shù)組對象指針指向新的數(shù)組對象----實(shí)以此來實(shí)現(xiàn)CopyOnWrite副本概念：
//CopyOnWrite容器中重要方法：獲取底層數(shù)組。
final Object[] getArray() {
return array;
}
//CopyOnWrite容器中重要方法：設(shè)置底層數(shù)組
final void setArray(Object[] a) {
array = a;
}
CopyOnWriteArrayList添加元素：在添加元素之前進(jìn)行加鎖操作，保證數(shù)據(jù)的原子性。在添加過程中，進(jìn)行數(shù)組復(fù)制，修改操作，再將新生成的數(shù)組復(fù)制給集合中的array屬性。最后，釋放鎖；
由于array屬性被volatile修飾，所以當(dāng)添加完成后，其他線程就可以立刻查看到被修改的內(nèi)容。
public boolean add(E e) {
final ReentrantLock lock = this.lock;
//加鎖：
lock.lock();
try {
//獲取集合中的數(shù)組：
Object[] elements = getArray();
int len = elements.length;
//數(shù)組復(fù)制：將此線程與其他線程對集合的操作區(qū)分開來，無論底層結(jié)構(gòu)如何改變，本線程中的數(shù)據(jù)不受影響
Object[] newElements = Arrays.copyOf(elements, len + 1);
//對新的數(shù)組進(jìn)行操作：
newElements[len] = e;
//將原有數(shù)組指針指向新的數(shù)組對象：
setArray(newElements);
return true;
} finally {
//釋放鎖：
lock.unlock();
}
}
CopyOnWriteArrayList獲取元素：在獲取元素時，由于array屬性被volatile修飾，所以每當(dāng)獲取線程執(zhí)行時，都會拿到最新的數(shù)據(jù)。此外，添加線程在進(jìn)行添加元素時，會將新的數(shù)組賦值給array屬性，所以在獲取線程中并不會因?yàn)樵氐奶砑佣鴮?dǎo)致本線程的執(zhí)行異常。因?yàn)楂@取線程中的array和被添加后的array指向了不同的內(nèi)存區(qū)域。
//根據(jù)角標(biāo)，獲取對應(yīng)的數(shù)組元素:
public E get(int index) {
return get(getArray(), index);
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
看到這，不知道你是不是跟我一樣，突然有個疑惑，在add（）方法時已經(jīng)加了鎖，為什么還要進(jìn)行數(shù)組復(fù)制呢，難道不是多此一舉嗎？
其實(shí)不然，為了能讓get（）方法得到最大的性能，CopyOnWriteArrayList并沒有進(jìn)行加鎖處理，而且也不需要加鎖處理。
因?yàn)?，在add（）時候加了鎖，首先不會有多個線程同時進(jìn)到add中去，這一點(diǎn)保證了數(shù)組的安全。當(dāng)在一個線程執(zhí)行add時，又進(jìn)行了數(shù)組的復(fù)制操作，生成了一個新的數(shù)組對象，在add后又將新數(shù)組對象的指針指向了舊的數(shù)組對象指針，注意此時是指針的替換，原來舊的數(shù)組對象還存在。這樣就實(shí)現(xiàn)了，添加方法無論如何操作數(shù)組對象，獲取方法在獲取到集合后，都不會受到其他線程添加元素的影響。
這也就是在執(zhí)行add()時，為什么還要在加鎖的同時又copy了一分新的數(shù)組對象?。?！
模擬CopyOnWriteArrayList：
public class CopyOnWriteThread{
private static CopyOnWriteTestList copyOnWriteTestList = new CopyOnWriteTestList();
static class CopyOnWriteTestList{
private Object[] array;
public CopyOnWriteTestList(){
this.array=new Object[0];
}
//獲取底層數(shù)組：
public Object[] getArray(){
return array;
}
//設(shè)置底層數(shù)組：
public void setArray(Object[] array) {
this.array = array;
}
//添加元素：
public void add(String element){
int len = array.length;
Object[] newElements = Arrays.copyOf(array, len + 1);
newElements[len] = element;
setArray(newElements);
}
public void get(int index){
Object[] array = getArray();
get(array,index);
}
//此步驟，就是為了驗(yàn)證在獲取元素時，array是否會隨著元素的添加而改變；
public void get(Object[] array,int index){
for(;;){
System.out.println("獲取方法："+array.length);
}
}
}
//創(chuàng)建線程：
public static void main(String[] agrs) throws InterruptedException {
//啟動異步線程，一直添加元素
new ThreadPoolExecutor(10,10,10, TimeUnit.MINUTES,
new ArrayBlockingQueue(11),
new ThreadPoolExecutor.AbortPolicy()).execute(new Runnable() {
public void run() {
for(;;){
int x=0;;
copyOnWriteTestList.add("jiaboyan"+x);
++x;
}
}
});
Thread.sleep(1000);
System.out.println(copyOnWriteTestList.getArray().length);
//啟動線程：獲取元素
new Runnable() {
public void run() {
copyOnWriteTestList.get(0);
}
}.run();
}
}
- CopyOnWrite機(jī)制的優(yōu)缺點(diǎn)
CopyOnWriteArrayList保證了數(shù)據(jù)在多線程操作時的最終一致性。
缺點(diǎn)也同樣顯著，那就是內(nèi)存空間的浪費(fèi)：因?yàn)樵趯懖僮鲿r，進(jìn)行數(shù)組復(fù)制，在內(nèi)存中產(chǎn)生了兩份相同的數(shù)組。如果數(shù)組對象比較大，那么就會造成頻繁的GC操作，進(jìn)而影響到系統(tǒng)的性能；
剛才說了，CopyOnWriteArrayList只能保證最終的數(shù)據(jù)一致性，而不能保證實(shí)時的數(shù)據(jù)一致性。這一點(diǎn)也是我們在使用的過程中，必須要考慮到的因素。
仔細(xì)思考下，其實(shí)CopyOnWrite容器也是一種讀寫分離，讀和寫是不同的容器。
