堵塞隊列

先了解一下生產者消費者模式：

生產者就是生產數據的一方，消費者就是消費數據的另一方。在多線程開發中，如果生產者處理速度很快，而消費者處理速度很慢，那么生產者就必須等待消費者處理完，才能繼續生產數據。如果消費者的處理能力大于生產者，那么消費者就必須等待生產者。為了解決這種生產消費能力不均衡的問題，便有了生產者和消費者模式。

生產者和消費者模式是通過一個容器來解決生產者和消費者的強耦合問題，即有了MQ（Message Queue）中間件。生產者和消費者彼此之間不直接通信，而是通過阻塞隊列來進行通信，所以生產者生產完數據之后不用等待消費者處理，直接推送給阻塞隊列，消費者直接從阻塞隊列里獲取數據。

基本概念：

1)、當隊列滿的時候，插入元素的線程被阻塞，直達隊列不滿。

2)、隊列為空的時候，獲取元素的線程被阻塞，直到隊列不空。

這種模式最常見的就是在MQ里面，即消息隊列（Message Queue）框架，這里就不多談了。

BlockQueue<T>

堵塞隊列都是基于這個接口實現的

基本接口定義，個人覺得如果用堵塞隊列的話就應該推薦使用堵塞方法，即put()以及take()

方法	拋出異常	帶有返回值	堵塞	超時退出
插入方法	add	offer	put	offer(Time)
刪除方法	remove	poll	take	poll(Time)
判斷是否存在	element	peek	N/A	N/A

1）、拋出異常：當隊列滿時，如果再往隊列里插入元素，會拋出IllegalStateException異常。當隊列空時，從隊列里獲取元素會拋出NoSuchElementException異常。

2）、返回特殊值：當往隊列插入元素時，會返回元素是否插入成功，成功返回true。如果是移除方法，則是從隊列里取出一個元素，如果沒有則返回null。

3）、一直阻塞：當阻塞隊列滿時，如果生產者線程往隊列里put元素，隊列會一直阻塞生產者線程，直到隊列可用或者響應中斷退出。當隊列空時，如果消費者線程從隊列里take元素，隊列會阻塞住消費者線程，直到隊列不為空。

4）、超時退出：當阻塞隊列滿時，如果生產者線程往隊列里插入元素，隊列會阻塞生產者線程一段時間，如果超過了指定的時間，生產者線程就會退出。

堵塞隊列分有界和無界隊列

有界：會有設定的隊列大小，不能無限制的創建隊列大小

無界：指理論上可以無限隊列的大小，但是實際情況，每個服務器都會有大小，只能說是理論上的，實際應用的時候會容易撐滿磁盤或內存，建議使用有界堵塞隊列

常用的堵塞隊列有一下幾種：

ArrayBlockingQueue：一個由數組組成的有界堵塞隊列，是一個FIFO隊列，不過要求創建對象的時候創建大小，內部是由ReentrantLock和Condition實現堵塞策略，單個鎖

    /** Main lock guarding all access */final ReentrantLock lock;/** Condition for waiting takes */private final Condition notEmpty;/** Condition for waiting puts */private final Condition notFull;

LinkedBlockingQueue：由鏈表結構組成的有界堵塞隊列，也是一個FIFO隊列，不要求創建對象是設置默認大小，不設置為Integer.MAX_VAUE；有兩個鎖，一個用于插入元素，另外一個用于獲取元素

    /** Lock held by take, poll, etc */private final ReentrantLock takeLock = new ReentrantLock();/** Wait queue for waiting takes */private final Condition notEmpty = takeLock.newCondition();/** Lock held by put, offer, etc */private final ReentrantLock putLock = new ReentrantLock();/** Wait queue for waiting puts */private final Condition notFull = putLock.newCondition();

PriorityBlockingQueue：一個支持優先級排序的無界阻塞隊列。默認情況下，按照自然順序，要么實現compareTo()方法，指定構造參數Comparator。

DelayQueue：一個使用優先級隊列實現的無界阻塞隊列。支持延時獲取的元素的阻塞隊列，即可以延時推送，元素必須要實現Delayed接口。

SynchronousQueue：一個不存儲元素的阻塞隊列，所以在執行速度上會比其他堵塞隊列要快，每一個put操作都要等待一個take操作；

LinkedBlockingDeque：一個由鏈表結構組成的雙向阻塞隊列。可以從隊列的頭和尾都可以插入和移除元素，實現工作密取，方法名帶了First對頭部操作，帶了last從尾部操作。

跳表（SkipList）

是一種加快查詢鏈表速度的一種方法，以空間換時間的一種方法，代表的類有ConcurrentSkipListMap和ConcurrentSkipListSet，也是一種隨機概率數據結構；

在原有的鏈表結構（鏈表是按順序排序的）上加上一層鏈表結構，但這個是隨機指定的，類似于數據庫的索引，可加多層索引鏈表查詢的時間復雜度為O(logn)，快跟上了紅黑樹的查詢速度，下面為圖解示例：

     ** Head nodes          Index nodes* +-+    right        +-+                      +-+* |2|---------------->| |--------------------->| |->null* +-+                 +-+                      +-+*  | down              |                        |*  v                   v                        v* +-+            +-+  +-+       +-+            +-+       +-+* |1|----------->| |->| |------>| |----------->| |------>| |->null* +-+            +-+  +-+       +-+            +-+       +-+*  v              |    |         |              |         |* Nodes  next     v    v         v              v         v* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null* +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+*

寫時復制容器

通俗的理解是當我們往一個容器添加元素的時候，不直接往當前容器添加，而是先將當前容器進行Copy，復制出一個新的容器，然后新的容器里添加元素，添加完元素之后，再將原容器的引用指向新的容器。這樣做的好處是我們可以對容器進行并發的讀，而不需要加鎖，因為當前容器不會添加任何元素。所以寫時復制容器也是一種讀寫分離的思想，讀和寫不同的容器。如果讀的時候有多個線程正在向容器添加數據，讀還是會讀到舊的數據，因為寫的時候不會鎖住舊的，只能保證最終一致性。

常見的有CopyOnWriteArrayList以及CopyOnWriteArraySet；

適用讀多寫少的并發場景，常見應用：白名單/黑名單， 商品類目的訪問和更新場景。

以下為圖解，在寫完后，原本的引用會重新指向新的數組對象，所以就會存在內存占用問題。