前言
Java并發包有很大一部分都是關于并發容器的。Java在5.0版本之前線程安全的容器稱之為同步容器。同步容器實作線程安全的方式：是将每個公有方法都使用
synchronized
修飾，保證每次隻有一個線程能通路容器的狀态。但是這樣的串行度太高，将嚴重降低并發性，當多個線程競争容器的鎖時，吞吐量将嚴重降低。是以，在Java 5.0版本時提供了性能更高的容器來改進之前的同步容器，我們稱其為并發容器。
下面我們先來介紹Java 5.0之前的同步容器，然後再來介紹Java 5.0之後的并發容器。
Java 5.0之前的同步容器
目前，Java中的容器主要可分為四大類，分别為
List
、
Map
Set
Queue
（Queue是Java5.0添加的新的容器類型），但是并不是所有的Java容器都是線程安全的。例如，我們常用的
ArrayList
和
HashMap
就不是線程安全的。線程安全的類為
Vector
Stack
HashTable
。
如何将非線程安全的類變為線程安全的類？
非線程安全的容器類可以由
Collections
類提供的
Collections.synchronizedXxx()
工廠方法将其包裝為線程安全的類。
// 分别将ArrayList、HashMap和HashSet包裝成線程安全的List 、Map和Set
List list = Collections.synchronizedList(new ArrayList());
Set set = Collections.synchronizedSet(new HashSet());
Map map = Collections.synchronizedMap(new HashMap());
這些類實作線程安全的方式是：将它們的狀态封裝起來，并對每個公有方法進行同步，使得每次隻有一個線程能通路容器的狀态。以ArrayList為例，可以使用如下的代碼來了解如何将非線程安全的容器包裝為線程安全的容器。
// 包裝 ArrayList
SafeArrayList<T>{
List<T> c = new ArrayList<>();
// 控制通路路徑，使用synchronized修飾保證線程互斥通路
synchronized T get(int idx){
return c.get(idx);
}
synchronized void add(int idx, T t) {
c.add(idx, t);
}
synchronized boolean addIfNotExist(T t){
if(!c.contains(t)) {
c.add(t);
return true;
}
return false;
}
}
被包裝出來的線程安全的類，都是基于synchronized同步關鍵字實作，于是被成為同步容器。而原本的線程安全的容器類
Vector
等，同樣也是基于synchronized關鍵字實作的。
同步容器在複合操作中的問題
同步容器類都是線程安全的，但是複合操作往往都會包含競态條件問題。這時就需要額外的用戶端加鎖來保證複合操作的原子性。
在下例\(^{[2]}\)中，定義了兩個方法
getLast()
deleteLast()
，它們都會執行“先檢查後執行再運作”操作。每個方法首先都獲得數組的大小，然後通過結果來擷取或删除最後一個元素。
public class UnsafeVectorHelpers {
public static Object getLast(Vector list) {
int lastIndex = list.size() - 1;
return list.get(lastIndex);
}
public static void deleteLast(Vector list) {
int lastIndex = list.size() - 1;
list.remove(lastIndex);
}
}
如果線程同時調用相同的方法，這将不會産生什麼問題。但是從調用者方向看，這将導緻非常嚴重的後果。如果線程A在包含10個元素的Vector上調用getLast，同時線程B在同一個Vector上調用deleteLast，這些操作的交替若如下所示，那麼getLast将抛出
ArrayIndexOutOfBoundsException
異常。
線程A在調用size()與getLast()這兩個操作之間，Vector變小了，是以在調用size時得到的索引值将不再有效。
于是我們便需要在用戶端加鎖實作新操作的原子性。那麼就需要考慮對哪個鎖對象進行加鎖。
同步容器類通過加鎖自身（this）來保護它的每個方法，于是在這裡我們鎖住list對象便可以保證getLast()和deleteLast()成為原子性操作。
public class SafeVectorHelpers {
public static Object getLast(Vector list) {
synchronized (list) {
int lastIndex = list.size() - 1;
return list.get(lastIndex);
}
}
public static void deleteLast(Vector list) {
synchronized (list) {
int lastIndex = list.size() - 1;
list.remove(lastIndex);
}
}
}
在對Vector中元素進行疊代\(^{[2]}\)時，調用size()和相應的get()之間Vector的大小可能發生變化的情況也會出現。
for(int i=0; i<vector.size(); i++){
doSomething(vector.get(i));
}
與getLast()一樣，如果在對Vector進行疊代時，另一個線程删除了一個元素，并且删除和通路這兩個操作交替執行，那麼上面的方法将抛出
ArrayIndexOutOfBoundsException
同樣，我們可以通過在用戶端加鎖來防止其他線程在疊代期間修改Vector。
synchronized(vector){
for(int i=0; i<vector.size(); i++){
doSomething(vector.get(i));
}
}
有得必有失，以上代碼将會導緻其他線程在疊代期間無法通路vector，是以也降低了并發性。
疊代器與ConcurrentModificationException
無論是使用for循環疊代，還是使用Java 5.0引入的
for-each
循環文法，對容器類進行疊代的标準方式都是使用Iterator。同樣，如果在使用疊代器通路容器期間，有線程并發地修改容器的大小，也是需要對疊代操作進行加鎖，即如下\({^{[1]}}\)。
List list = Collections.synchronizedList(new ArrayList());
synchronized (list) {
Iterator i = list.iterator();
while (i.hasNext())
foo(i.next());
}
在設計同步容器類的疊代器時沒有考慮到并發修改的問題，當出現如上情況時，它們表現出來的行為是“及時失敗”（fail-fast）的。當它們發現容器在疊代過程中被修改時，就會立即抛出一個
ConcurrentModificationException
這種fail-fast的疊代器并不是一種完備的處理機制，而隻是“善意地”捕獲并發錯誤，是以隻能作為并發問題的預警訓示器。這種機制的實作方式是：使用一個計數器
modCount
記錄容器大小改變的次數，在進行疊代期間，如果該計數器值與剛進入疊代時不一緻，那麼hasNext()或next()将抛出
ConcurrentModificationException
但是，對計數器的值的檢查時是沒有在同步情況下進行的，是以可能會看到失效的計數值，導緻疊代器沒有意識到容器已經發生了修改。這是一種設計上的權衡，進而降低并發修改操作的檢測代碼對程式性能帶來的影響。
更多的時候，我們是不希望在疊代期間對容器加鎖。如果容器規模很大，在加鎖疊代後，那麼在疊代期間其他線程都不能通路該容器。這将降低程式的可伸縮性以及引起激烈的鎖競争降低吞吐量和CPU使用率。
一種替代加鎖疊代的方法為“克隆”容器，并在副本上疊代。副本是線程封閉的，自然也就是安全的。但是克隆的過程也需要對容器加鎖，且也存在一定的開銷，需考慮使用。
隐藏的疊代器
容器的
hashCode()
equals()
等方法也會間接地執行疊代操作，當容器作為另一個容器的元素或鍵值時，就會出現這種情況。同樣，
containsAll()
removeAll()
retainAll()
等方法，以及把容器作為參數的構造函數，都會對容器進行疊代。所有這些間接疊代操作都可能抛出
ConcurrentModificationException
Java 5.0的并發容器
在Java 5.0版本時提供了性能更高的容器來改進之前的同步容器，我們稱之為并發容器。并發容器雖然多，但是總結下來依舊為四大類：
List
Map
Set
Queue
List
CopyOnWriteArrayList
是用于替代同步List的并發容器，在疊代期間不需要對容器進行加鎖或複制。寫時複制（CopyOnWrite）的線程安全性展現在，隻要正确地釋出一個事實不可變的對象，那麼在通路該對象時就不再需要進一步的同步。而在每次進行寫操作時，便會建立一個副本出來，進而實作可變性。“寫時複制”容器傳回的疊代器不會抛出ConcurrentModificationException，因為疊代器在疊代過程中，如果對象會被修改則會建立一個副本被修改，被疊代的對象依舊是原來的。
CopyOnWriteArrayList僅适用于寫操作非常少的場景，而且能夠容忍短暫的不一緻。CopyOnWriteArrayList疊代器是隻讀的，不支援增删改。因為疊代器周遊的僅僅是一個快照，而對快照進行增删改是沒有意義的。
Map
ConcurrentHashMap
ConcurrentSkipListMap
的差別為：ConcurrentHashMap的key是無序的，而ConcurrentSkipListMap的key是有序的。使用這兩者時，它們的key和value都不能為空，否則會抛出NullPointerException異常。
Map有關實作類對于key和value的要求：
| 集合類 | Key | Value | 是否線程安全 |
|---|---|---|---|
| HashMap | 允許為null | 否 | |
| TreeMap | 不允許為null | ||
| HashTable | 是 | ||
| ConcurrentHashMap | |||
| ConcurrentSkipListMap |
與HashMap一樣，ConcurrentHashMap也是一個基于散列的Map，它使用分段鎖實作了更大程度的共享。任意數量的讀取線程可以并發地通路Map，執行讀取的線程和執行寫入的線程可以并發地通路Map，并且一定數量的寫入線程可以并發地修改Map。ConcurrentHashMap在并發環境下可以實作更高的吞吐量，而在單線程環境中隻損失非常小的性能。
ConcurrentHashMap傳回的疊代器也不會抛出ConcurrentModificationException，是以不需要在疊代期間對容器加鎖。ConcurrentHashMap傳回的疊代器具有弱一緻性（Weakly Consistent）,而并非fail-fast的。弱一緻性的疊代器可以容忍并發的修改，當建立疊代器會周遊已有的元素，并可以（但是不保證）在疊代器被建構後将修改操作反映給容器。
ConcurrentHahsMap是對Map進行分段加鎖，沒有實作獨占。所有需要獨占通路功能的，應該使用其他并發容器。
ConcurrentSkipListMap裡面的
SkipList
本身就是一種資料結構，中文翻譯為“跳表”。跳表插入、删除、查詢操作平均時間複雜度為O(log n)。傳回的疊代器也是弱一緻性的，也不會抛出ConcurrentModificationException。
Set
Set接口下，兩個并發容器是
CopyOnWriteArraySet
ConcurrentSkipListSet
，可參考CopyOnWriteArrayList和ConcurrentSkipListMap了解。
Queue
Java并發包中Queue下的并發容器是最複雜的，可以從下面兩個次元來分類：
-
阻塞和非阻塞
阻塞隊列是指當隊列已滿時，入隊操作阻塞；當隊列為空時，出對操作阻塞。
-
單端和雙端
單端隊列指的是隻能從隊尾入隊，隊首出隊；雙端指的是隊首隊尾皆可出隊。
在Java并發包中，阻塞隊列都有Blocking辨別，單端隊列是用Queue辨別，而雙端隊列是Deque辨別。以上兩個次元可組合，于是分為四類并發容器：單端阻塞隊列、雙端阻塞隊列、單端非阻塞隊列、雙端非阻塞隊列。
在使用隊列時，需要格外注意隊列是否為有界隊列（内部的隊列是否容量有限），無界隊列在資料量大時，會導緻OOM即記憶體溢出。
在有Queue的具體實作的并發容器中，隻有ArrayBlockingQueue和LinkedBlockingQueue是支援有界的，其餘都是無界隊列。
小結
這篇文章從宏觀層面介紹了Java并發包中的并發工具類，對每個容器類僅做了簡單介紹，後續将附文介紹每一個容器類。
參考：
[1]極客時間專欄王寶令《Java并發程式設計實戰》
[2]Brian Goetz.Tim Peierls. et al.Java并發程式設計實戰[M].北京:機械工業出版社,2016
每天進步一點點，不要停止前進的腳步~