Java中的集合和線程安全
通過Java指南我們知道Java集合架構（Collection Framework）如何為并發服務，我們應該如何在單線程和多線程中使用集合（Collection）。
1. 為什麼大多數的集合類不是線程安全的？
所有的集合類比如：ArrayList, LinkedList, HashMap, HashSet, TreeMap, TreeSet等等。（除了Vector和HashTable以外）在java.util包中都不是線程安全的，隻遺留了兩個實作類（Vector和HashTable）是線程安全的為什麼？
原因是：線程安全消耗十分昂貴！
你應該知道，Vector和HashTable在Java曆史中，很早就出現了，最初的時候他們是為線程安全設計的。（如果你看了源碼，你會發現這些實作類的方法都被synchronized修飾）而且很快的他們在多線程中性能表現的非常差。如你所知的，同步就需要鎖，有鎖就需要時間來監控，是以就降低了性能。
這就是為什麼新的集合類沒有提供并發控制，為了保證在單線程中提供最大的性能。
下面測試的程式驗證了Vector和ArrayList的性能，兩個相似的集合類（Vector是線程安全，ArrayList非線程安全）
import java.util.*;
public class CollectionTest {
public static void main(String[] args) {
/**
* Vector線程安全，但是性能消耗很大
*/
CollectionTest collectionTest = new CollectionTest();
collectionTest.testVoucher();
collectionTest.testArrayList();
}
public void testVoucher(){
long startTime = System.currentTimeMillis();
Vector<Object> vector = new Vector<>();
for (int i =0;i<10000000;i++){
vector.addElement(i);
}
long endTime = System.currentTimeMillis();
System.out.println("Test Voucher:"+(startTime - endTime)+"ms");
}
public void testArrayList(){
long startTime = System.currentTimeMillis();
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i =0;i<10000000;i++){
arrayList.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("Test ArrayList:"+(startTime - endTime)+"ms");
}
}
通過為每個集合添加1000萬個元素來測試性能，結果如下：
Test Voucher:-2159ms
Test ArrayList:-596ms
如你所看到的，在相當大的資料操作下，ArrayList速度差不多是Vector的2倍。你也拷貝上述代碼自己感受下。
2.快速失敗疊代器（Fail-Fast Iterators）
在使用集合的時候，你也要了解到疊代器的并發政策：Fail-Fast Iterators
看下以後代碼片段，周遊一個String類型的集合：
List<String> listNames = Arrays.asList("Tom", "Joe", "Bill", "Dave", "John");
Iterator<String> iterator = listNames.iterator();
while (iterator.hasNext()) {
String nextName = iterator.next();
System.out.println(nextName);
}
這裡我們使用了Iterator來周遊list中的元素，試想下listNames被兩個線程共享：一個線程執行周遊操作，在還沒有周遊完成的時候，第二線程進行修改集合操作（添加或者删除元素），你猜測下這時候會發生什麼？
周遊集合的線程會立刻抛出異常“ConcurrentModificationException”
為什麼疊代器會如此迅速的抛出異常？
因為當一個線程在周遊集合的時候，另一個在修改周遊集合的資料會非常的危險：集合可能在修改後，有更多元素了，或者減少了元素又或者一個元素都沒有了。是以在考慮結果的時候，選擇抛出異常。
下面這段代碼示範了抛出：ConcurrentModificationException
import java.util.*;
/**
* This test program illustrates how a collection's iterator fails fast
* and throw ConcurrentModificationException
* @author www.codejava.net
*
*/
public class IteratorFailFastTest {
private List<Integer> list = new ArrayList<>();
public IteratorFailFastTest() {
for (int i = 0; i < 10_000; i++) {
list.add(i);
}
}
public void runUpdateThread() {
Thread thread1 = new Thread(new Runnable() {
public void run() {
for (int i = 10_000; i < 20_000; i++) {
list.add(i);
}
}
});
thread1.start();
}
public void runIteratorThread() {
Thread thread2 = new Thread(new Runnable() {
public void run() {
ListIterator<Integer> iterator = list.listIterator();
while (iterator.hasNext()) {
Integer number = iterator.next();
System.out.println(number);
}
}
});
thread2.start();
}
public static void main(String[] args) {
IteratorFailFastTest tester = new IteratorFailFastTest();
tester.runIteratorThread();
tester.runUpdateThread();
}
}
如你所見，在thread1周遊list的時候，thread2執行了添加元素的操作，這時候異常被抛出。
需要注意的是，使用iterator周遊list，快速失敗的行為是為了讓我更早的定位問題所在。我們不應該依賴這個來捕獲異常，因為快速失敗的行為是沒有保障的。這意味着如果抛出異常了，程式應該立刻終止行為而不是繼續執行。
現在你應該了解到了ConcurrentModificationException是如何工作的，而且最好是避免它。
同步封裝器
至此我們明白了，為了確定在單線程環境下的性能最大化，是以基礎的集合實作類都沒有保證線程安全。那麼如果我們在多線程環境下如何使用集合呢？
當然我們不能使用線程不安全的集合在多線程環境下，這樣做會導緻出現我們期望的結果。我們可以手動自己添加synchronized代碼塊來確定安全，但是使用自動線程安全的線程比我們手動更為明智。
你應該已經知道，Java集合架構提供了工廠方法建立線程安全的集合，這些方法的格式如下：
這個工廠方法封裝了指定的集合并傳回了一個線程安全的集合。XXX可以是Collection、List、Map、Set、SortedMap和SortedSet的實作類。比如下面這段代碼建立了一個線程安全的清單：
如果我們已經擁有了一個線程不安全的集合，我們可以通過以下方法來封裝成線程安全的集合：
Map<Integer, String> unsafeMap = new HashMap<>();
Map<Integer, String> safeMap = Collections.synchronizedMap(unsafeMap);
如你鎖看到的，工廠方法封裝指定的集合，傳回一個線程安全的結合。事實上接口基本都一直，隻是實作上添加了synchronized來實作。是以被稱之為：同步封裝器。後面集合的工作都是由這個封裝類來實作。
提示：
在我們使用iterator來周遊線程安全的集合對象的時候，我們還是需要添加synchronized字段來確定線程安全，因為Iterator本身并不是線程安全的，請看代碼如下：
List<String> safeList = Collections.synchronizedList(new ArrayList<>());
// adds some elements to the list
Iterator<String> iterator = safeList.iterator();
while (iterator.hasNext()) {
String next = iterator.next();
System.out.println(next);
}
事實上我們應該這樣來操作：
synchronized (safeList) {
while (iterator.hasNext()) {
String next = iterator.next();
System.out.println(next);
}
}
同時提醒下，Iterators也是支援快速失敗的。
盡管經過類的封裝可保證線程安全，但是他們依然有着自己的缺點，具體見下面部分。
并發集合
一個關于同步集合的缺點是，用集合的本身作為鎖的對象。這意味着，在你周遊對象的時候，這個對象的其他方法已經被鎖住，導緻其他的線程必須等待。其他的線程無法操作目前這個被鎖的集合，隻有當執行的線程釋放了鎖。這會導緻開銷和性能較低。
這就是為什麼jdk1.5+以後提供了并發集合的原因，因為這樣的集合性能更高。并發集合類并放在java.util.concurrent包下，根據三種安全機制被放在三個組中。
第一種為：寫時複制集合：這種集合将資料放在一成不變的數組中；任何資料的改變，都會重新建立一個新的數組來記錄值。這種集合被設計用在，讀的操作遠遠大于寫操作的情景下。有兩個如下的實作類：CopyOnWriteArrayList 和 CopyOnWriteArraySet.
需要注意的是，寫時複制集合不會抛出ConcurrentModificationException異常。因為這些集合是由不可變數組支援的，Iterator周遊值是從不可變數組中出來的，不用擔心被其他線程修改了資料。
第二種為：比對交換集合也稱之為CAS（Compare-And-Swap）集合：這組線程安全的集合是通過CAS算法實作的。CAS的算法可以這樣了解：
為了執行計算和更新變量，在本地拷貝一份變量，然後不通過擷取通路來執行計算。當準備好去更新變量的時候，他會跟他之前的開始的值進行比較，如果一樣，則更新值。
如果不一樣，則說明應該有其他的線程已經修改了資料。在這種情況下，CAS線程可以重新執行下計算的值，更新或者放棄。使用CAS算法的集合有：ConcurrentLinkedQueue and ConcurrentSkipListMap.
需要注意的是，CAS集合具有不連貫的iterators，這意味着自他們建立之後并不是所有的改變都是從新的數組中來。同時他也不會抛出ConcurrentModificationException異常。
第三種為：這種集合采用了特殊的對象鎖（java.util.concurrent.lock.Lock）：這種機制相對于傳統的來說更為靈活，可以如下了解：
這種鎖和經典鎖一樣具有基本的功能，但還可以再特殊的情況下擷取：如果目前沒有被鎖、逾時、線程沒有被打斷。
不同于synchronization的代碼,當方法在執行，Lock鎖一直會被持有，直到調用unlock方法。有些實作通過這種機制把集合分為好幾個部分來提供并發性能。比如：LinkedBlockingQueue，在隊列的開後和結尾，是以在添加和删除的時候可以同時進行。
其他使用了這種機制的集合有：ConcurrentHashMap 和絕多數實作了BlockingQueue的實作類
同樣的這一類的集合也具有不連貫的iterators，也不會抛出ConcurrentModificationException異常。
我們來總結下今天我們所學到的幾個點：
1. 大部分在java.util包下的實作類都沒有保證線程安全為了保證性能的優越，除了Vector和Hashtable以外。
2. 通過Collection可以建立線程安全類，但是他們的性能都比較差。
3. 同步集合既保證線程安全也在給予不同的算法上保證了性能，他們都在java.util.concurrent包中。
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)