摘要：同步容器及其注意事項中的容器主要可以分為四個大類，分別是和，但并不是所有的容器都是線程安全的。并發(fā)容器及其注意事項在版本之前所謂的線程安全的容器，主要指的就是同步容器，當(dāng)然因為所有方法都用來保證互斥，串行度太高了，性能太差了。

Java 并發(fā)包有很大一部分內(nèi)容都是關(guān)于并發(fā)容器的，因此學(xué)習(xí)和搞懂這部分的內(nèi)容很有必要。

Java 1.5 之前提供的同步容器雖然也能保證線程安全，但是性能很差，而 Java 1.5 版本之后提供的并發(fā)容器在性能方面則做了很多優(yōu)化，并且容器的類型也更加豐富了。下面我們就對比二者來學(xué)習(xí)這部分的內(nèi)容。

Java 中的容器主要可以分為四個大類，分別是 List、Map、Set 和 Queue，但并不是所有的 Java 容器都是線程安全的。例如，我們常用的 ArrayList、HashMap 就不是線程安全的。在介紹線程安全的容器之前，我們先思考這樣一個問題：如何將非線程安全的容器變成線程安全的容器？

之前我們討論果，只要把非線程安全的容器封裝在對象內(nèi)部，然后控制好訪問路徑就可以了。

下面我們就以 ArrayList 為例，看看如何將它變成線程安全的。在下面的代碼中，SafeArrayList 內(nèi)部持有一個 ArrayList 的實(shí)例 c，所有訪問 c 的方法我們都增加了 synchronized 關(guān)鍵字，需要注意的是我們還增加了一個 addIfNotExist() 方法，這個方法也是用 synchronized 來保證原子性的。

SafeArrayList{
  // 封裝 ArrayList
  List c = new ArrayList<>();
  // 控制訪問路徑
  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;
  }
}

看到這里，你可能會舉一反三，然后想到：所有非線程安全的類是不是都可以用這種包裝的方式來實(shí)現(xiàn)線程安全呢？其實(shí)在Java SDK就提供了這類功能，在 Collections 這個類中還提供了一套完備的包裝類，比如下面的示例代碼中，分別把 ArrayList、HashSet 和 HashMap 包裝成了線程安全的 List、Set 和 Map。

List list = Collections.
  synchronizedList(new ArrayList());
Set set = Collections.
  synchronizedSet(new HashSet());
Map map = Collections.
  synchronizedMap(new HashMap());

之前說過的組合操作需要注意競態(tài)條件問題，例如上面提到的 addIfNotExist() 方法就包含組合操作。組合操作往往隱藏著競態(tài)條件問題，即便每個操作都能保證原子性，也并不能保證組合操作的原子性，這個一定要注意。

在容器領(lǐng)域一個容易被忽視的“坑”是用迭代器遍歷容器，例如在下面的代碼中，通過迭代器遍歷容器 list，對每個元素調(diào)用 foo() 方法，這就存在并發(fā)問題，這些組合的操作不具備原子性。

List list = Collections.
  synchronizedList(new ArrayList());
Iterator i = list.iterator(); 
while (i.hasNext())
  foo(i.next());

而正確做法是下面這樣，鎖住 list 之后再執(zhí)行遍歷操作, 所以鎖住 list 絕對是線程安全的。

List list = Collections.
  synchronizedList(new ArrayList());
synchronized (list) {  
  Iterator i = list.iterator(); 
  while (i.hasNext())
    foo(i.next());
}    

上面我們提到的這些經(jīng)過包裝后線程安全容器，都是基于 synchronized 這個同步關(guān)鍵字實(shí)現(xiàn)的，所以也被稱為同步容器。Java 提供的同步容器還有 Vector、Stack 和 Hashtable，這三個容器不是基于包裝類實(shí)現(xiàn)的，但同樣是基于 synchronized 實(shí)現(xiàn)的，對這三個容器的遍歷，同樣要加鎖保證互斥。

Java 在 1.5 版本之前所謂的線程安全的容器，主要指的就是同步容器，當(dāng)然因為所有方法都用 synchronized 來保證互斥，串行度太高了，性能太差了。因此 Java 在 1.5 及之后版本提供了性能更高的容器，我們一般稱為并發(fā)容器。

并發(fā)容器雖然數(shù)量非常多，但依然是前面我們提到的四大類：List、Map、Set 和 Queue。

并發(fā)容器關(guān)系圖

這里只是把關(guān)鍵點(diǎn)介紹一下。

List 里面只有一個實(shí)現(xiàn)類就是 CopyOnWriteArrayList。CopyOnWrite，顧名思義就是寫的時候會將共享變量新復(fù)制一份出來，這樣做的好處是讀操作完全無鎖。

CopyOnWriteArrayList 內(nèi)部維護(hù)了一個數(shù)組，成員變量 array 就指向這個內(nèi)部數(shù)組，所有的讀操作都是基于 array 進(jìn)行的，如下圖所示，迭代器 Iterator 遍歷的就是 array 數(shù)組。

執(zhí)行迭代的內(nèi)部結(jié)構(gòu)圖

如果在遍歷 array 的同時，還有一個寫操作，例如增加元素。CopyOnWriteArrayList 會將 array 復(fù)制一份，然后在新復(fù)制處理的數(shù)組上執(zhí)行增加元素的操作，執(zhí)行完之后再將 array 指向這個新的數(shù)組。通過下圖你可以看到，讀寫是可以并行的，遍歷操作一直都是基于原 array 執(zhí)行，而寫操作則是基于新 array 進(jìn)行。

執(zhí)行增加元素的內(nèi)部結(jié)構(gòu)圖

使用 CopyOnWriteArrayList 需要注意的“坑”主要有兩個方面。一個是應(yīng)用場景，CopyOnWriteArrayList 僅適用于寫操作非常少的場景，而且能夠容忍讀寫的短暫不一致。例如上面的例子中，寫入的新元素并不能立刻被遍歷到。另一個需要注意的是，CopyOnWriteArrayList 迭代器是只讀的，不支持增刪改。因為迭代器遍歷的僅僅是一個快照，而對快照進(jìn)行增刪改是沒有意義的。

Map 接口的兩個實(shí)現(xiàn)是 ConcurrentHashMap 和 ConcurrentSkipListMap，它們從應(yīng)用的角度來看，主要區(qū)別在于ConcurrentHashMap 的 key 是無序的，而 ConcurrentSkipListMap 的 key 是有序的。所以如果你需要保證 key 的順序，就只能使用 ConcurrentSkipListMap。

使用 ConcurrentHashMap 和 ConcurrentSkipListMap 需要注意的地方是，它們的 key 和 value 都不能為空，否則會拋出NullPointerException這個運(yùn)行時異常。下面這個表格總結(jié)了 Map 相關(guān)的實(shí)現(xiàn)類對于 key 和 value 的要求。

ConcurrentSkipListMap 里面的 SkipList 本身就是一種數(shù)據(jù)結(jié)構(gòu)，中文一般都翻譯為“跳表”。跳表插入、刪除、查詢操作平均的時間復(fù)雜度是 O(log n)，理論上和并發(fā)線程數(shù)沒有關(guān)系，所以在并發(fā)度非常高的情況下，若你對 ConcurrentHashMap 的性能還不滿意，可以嘗試一下 ConcurrentSkipListMap。

Set 接口的兩個實(shí)現(xiàn)是 CopyOnWriteArraySet 和 ConcurrentSkipListSet，使用場景可以參考前面講述的 CopyOnWriteArrayList 和 ConcurrentSkipListMap，它們的原理都是一樣的，這里就不再贅述了。

Java 并發(fā)包里面 Queue 這類并發(fā)容器是最復(fù)雜的，你可以從以下兩個維度來分類。一個維度是阻塞與非阻塞，所謂阻塞指的是當(dāng)隊列已滿時，入隊操作阻塞；當(dāng)隊列已空時，出隊操作阻塞。另一個維度是單端與雙端，單端指的是只能隊尾入隊，隊首出隊；而雙端指的是隊首隊尾皆可入隊出隊。Java 并發(fā)包里阻塞隊列都用 Blocking 關(guān)鍵字標(biāo)識，單端隊列使用 Queue 標(biāo)識，雙端隊列使用 Deque 標(biāo)識。

這兩個維度組合后，可以將 Queue 細(xì)分為四大類，分別是：

：其實(shí)現(xiàn)有 ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、LinkedTransferQueue、PriorityBlockingQueue 和 DelayQueue。內(nèi)部一般會持有一個隊列，這個隊列可以是數(shù)組（其實(shí)現(xiàn)是 ArrayBlockingQueue）也可以是鏈表（其實(shí)現(xiàn)是 LinkedBlockingQueue）；甚至還可以不持有隊列（其實(shí)現(xiàn)是 SynchronousQueue），此時生產(chǎn)者線程的入隊操作必須等待消費(fèi)者線程的出隊操作。而 LinkedTransferQueue 融合 LinkedBlockingQueue 和 SynchronousQueue 的功能，性能比 LinkedBlockingQueue 更好；PriorityBlockingQueue 支持按照優(yōu)先級出隊；DelayQueue 支持延時出隊。

：其實(shí)現(xiàn)是 LinkedBlockingDeque。

：其實(shí)現(xiàn)是 ConcurrentLinkedQueue。

：其實(shí)現(xiàn)是 ConcurrentLinkedDeque。

另外，使用隊列時，需要格外注意隊列是否支持有界（所謂有界指的是內(nèi)部的隊列是否有容量限制）。實(shí)際工作中，一般都不建議使用無界的隊列，因為數(shù)據(jù)量大了之后很容易導(dǎo)致 OOM。上面我們提到的這些 Queue 中，只有 ArrayBlockingQueue 和 LinkedBlockingQueue 是支持有界的，所以在使用其他無界隊列時，一定要充分考慮是否存在導(dǎo)致 OOM 的隱患