java-并發-并發容器（4）

對應的非并發容器：HashSet

目标：代替synchronizedSet

原理：基于CopyOnWriteArrayList實作，其唯一的不同是在add時調用的是CopyOnWriteArrayList的addIfAbsent方法，其周遊目前Object數組，如Object數組中已有了目前元素，則直接傳回，如果沒有則放入Object數組的尾部，并傳回。

基于CopyOnWriteArrayList實作，其唯一的不同是在add時調用的是CopyOnWriteArrayList的addIfAbsent方法，其周遊目前Object數組，如Object數組中已有了目前元素，則直接傳回，如果沒有則放入Object數組的尾部，并傳回。

Copy-On-Write簡稱COW，是一種用于程式設計中的優化政策。其基本思路是，從一開始大家都在共享同一個内容，當某個人想要修改這個内容的時候，才會真正把内容Copy出去形成一個新的内容然後再改，這是一種延時懶惰政策。從JDK1.5開始Java并發包裡提供了兩個使用CopyOnWrite機制實作的并發容器,它們是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器非常有用，可以在非常多的并發場景中使用到。

什麼是CopyOnWrite容器

CopyOnWrite容器即寫時複制的容器。通俗的了解是當我們往一個容器添加元素的時候，不直接往目前容器添加，而是先将目前容器進行Copy，複制出一個新的容器，然後新的容器裡添加元素，添加完元素之後，再将原容器的引用指向新的容器。這樣做的好處是我們可以對CopyOnWrite容器進行并發的讀，而不需要加鎖，因為目前容器不會添加任何元素。是以CopyOnWrite容器也是一種讀寫分離的思想，讀和寫不同的容器。

它是線程安全的無序的集合，可以将它了解成線程安全的HashSet。 有意思的是，CopyOnWriteArraySet和HashSet雖然都繼承于共同的父類AbstractSet；但是，HashSet是通過“散清單(HashMap)”實作的，而CopyOnWriteArraySet則是通過“ 動态數組(CopyOnWriteArrayList) ”實作的，并不是散清單。

和CopyOnWriteArrayList類似，CopyOnWriteArraySet具有以下特性：

1. 它最适合于具有以下特征的應用程式：Set 大小通常保持很小，隻讀操作遠多于可變操作，需要在周遊期間防止線程間的沖突。

2. 它是線程安全的。

3. 因為通常需要複制整個基礎數組，是以可變操作（add()、set() 和 remove() 等等）的開銷很大。

4. 疊代器支援hasNext(), next()等不可變操作，但不支援可變 remove()等 操作。

5. 使用疊代器進行周遊的速度很快，并且不會與其他線程發生沖突。在構造疊代器時，疊代器依賴于不變的數組快照。

CopyOnWriteArraySet繼承于AbstractSet，這就意味着它是一個集合。

2. CopyOnWriteArraySet包含CopyOnWriteArrayList對象，它是通過CopyOnWriteArrayList實作的。而CopyOnWriteArrayList本質是個動态數組隊列，

是以CopyOnWriteArraySet相當于通過通過動态數組實作的“集合”！ CopyOnWriteArrayList中允許有重複的元素；但是，CopyOnWriteArraySet是一個集合，是以它不能有重複集合。是以，CopyOnWriteArrayList額外提供了addIfAbsent()和addAllAbsent()這兩個添加元素的API，通過這些API來添加元素時，隻有當元素不存在時才執行添加操作！ 至于CopyOnWriteArraySet的“線程安全”機制，和CopyOnWriteArrayList一樣，是通過volatile和互斥鎖來實作的。這個在前一章節介紹CopyOnWriteArrayList時資料結構時，已經進行了說明，這裡就不再重複叙述了。

由于set是集合對象，是以它不會包含重複的元素。

如果将源碼中的set改成HashSet對象時，程式會産生ConcurrentModificationException異常。

Java中的隊列接口就是Queue，它有會抛出異常的add、remove方法，在隊尾插入元素以及對頭移除元素，還有不會抛出異常的，對應的offer、poll方法。

2.1 LinkedList

List實作了deque接口以及List接口，可以将它看做是這兩種的任何一種。

Queue queue=new LinkedList();

queue.offer(“testone”);

queue.offer(“testtwo”);

queue.offer(“testthree”);

queue.offer(“testfour”);

System.out.println(queue.poll()); //testone

2.2 PriorityQueue

一個基于優先級堆（簡單的使用連結清單的話，可能插入的效率會比較低O(N)）的無界優先級隊列。優先級隊列的元素按照其自然順序進行排序，或者根據構造隊列時提供的 Comparator 進行排序，具體取決于所使用的構造方法。優先級隊列不允許使用 null 元素。依靠自然順序的優先級隊列還不允許插入不可比較的對象。

queue=new PriorityQueue();

System.out.println(queue.poll()); //testfour

2.3 ConcurrentLinkedQueue

基于鍊節點的，線程安全的隊列。并發通路不需要同步。在隊列的尾部添加元素，并在頭部删除他們。是以隻要不需要知道隊列的大小，并發隊列就是比較好的選擇

生産者和消費者模式，生産者不需要知道消費者的身份或者數量，甚至根本沒有消費者，他們隻負責把資料放入隊列。類似地，消費者也不需要知道生産者是誰，以及是誰給他們安排的工作。

而Java知道大家清楚這個模式的并發複雜性，于是乎提供了阻塞隊列（BlockingQueue）來滿足這個模式的需求。阻塞隊列說起來很簡單，就是當隊滿的時候寫線程會等待，直到隊列不滿的時候；當隊空的時候讀線程會等待，直到隊不空的時候。實作這種模式的方法很多，其差別也就在于誰的消耗更低和等待的政策更優。

撇開其鎖的具體實作，其流程就是我們在作業系統課上學習到的标準生産者模式，看來那些枯燥的理論還是有用武之地的。其中，最核心的還是Java的鎖實作，有興趣的朋友可以再進一步深究一下。

阻塞隊列Blocking queue，提供了可阻塞的put和take方法，他們與可定時的offer和poll方法是等價。Put方法簡化了處理，如果是有界隊列，那麼當隊列滿的時候，生成者就會阻塞，進而改消費者更多的追趕速度。

ArrayBlockingQueue和LinkedBlockingQueue

FIFO的隊列，與LinkedList(由鍊節點支援，無界)和ArrayList（由數組支援，有界）相似（Linked有更好的插入和移除性能，Array有更好的查找性能，考慮到阻塞隊列的特性，移除頭部，加入尾部，兩個都差別不大），但是卻擁有比同步List更好的并發性能。

另外，LinkedList永遠不會等待，因為他是無界的

PriorityBlockingQueue

一個按優先級堆支援的無界優先級隊列隊列，如果不希望按照FIFO的順序進行處理，它非常有用。它可以比較元素本身的自然順序，也可以使用一個Comparator排序。

DelayQueue

一個優先級堆支援的，基于時間的排程隊列。加入到隊列中的元素必須實作新的Delayed接口（隻有一個方法，Long getDelay(java.util.concurrent.TimeUnit unit)），添加可以理立即傳回，但是在延遲時間過去之前，不能從隊列中取出元素，如果多個元素的延遲時間已到，那麼最早失效連結/失效時間最長的元素将第一個取出。

SynchronousQueue

不是一個真正的隊列，因為它不會為隊列元素維護任何存儲空間，不過它維護一個排隊的線程清單，這些線程等待把元素加入（enqueue）隊列或者移出（dequeue）隊列。也就是說，它非常直接的移交工作，減少了生産者和消費者之間移動資料的延遲時間，另外，也可以更快的知道回報資訊，當移交被接受時，它就知道消費者已經得到了任務。

因為SynChronousQueue沒有存儲的能力，是以除非另一個線程已經做好準備，否則put和take會一直阻止。它隻有在消費者比較充足的時候比較合适。

雙端隊列（Deque）

JAVA6中新增了兩個容器Deque和BlockingDeque，他們分别擴充了Queue和BlockingQueue。Deque它是一個雙端隊列，允許高效的在頭和尾分别進行插入和删除，它的實作分别是ArrayDeque和LinkedBlockingQueue。

雙端隊列使得他們能夠工作在一種稱為“竊取工作”的模式上面。

同步的（synchronized）+HashMap，如果不存在，則計算，然後加入，該方法需要同步。

用ConcurrentHashMap代替HashMap+同步.，這樣的在get和set的時候也基本能保證原子性。但是會帶來重複計算的問題.

采用FutureTask代替直接存儲值，這樣可以在一開始建立的時候就将Task加入

上面還有檢查再運作的缺陷，在高并發的情況下啊，雙方都沒發現FutureTask，并且都放入Map（後一個被前一個替代），都開始了計算。

這裡的解決方案在于，當他們都要放入Map的時候，如果可以有原子方法，那麼已經有了以後，後一個FutureTask就加入，并且啟動。

上面的程式上來看已經完美了，不過可能帶來緩存污染的可能性。如果一個計算被取消或者失敗，那麼這個鍵以後的值永遠都是失敗了；一種解決方案是，發現取消或者失敗的task，就移除它，如果有Exception，也移除。另外，如果考慮緩存過期的問題，可以為每個結果關聯一個過去時間，并周期性的掃描，清除過期的緩存。（過期時間可以用Delayed接口實作，參考DelayQueue，給他一個大于目前時間XXX的時間，，并且不斷減去目前時間，直到傳回負數，說明延遲時間已到了。