【多線程與高并發】5-容器

自帶鎖，現基本不用

内部用了CAS，高并發，查詢效率高

高并發并且有序（代替TreeMap,因為TreeMap用了紅黑樹，較為複雜，是以沒有ConcurrentTreeMap）

樹的結構是由concurrent+CAS

跳表結構：

寫時複制容器

多線程環境下，寫時效率低（加鎖），讀時效率高（不加鎖），适合寫少讀多的環境。

插入元素時，拷貝原list并擴充，最後将原list引用指向新list。

offer 加，poll 取出來并remove , peek 取出來不remove（非阻塞，都會報異常但offer除外-它有傳回值）

特點：put 裝，take 取 （兩個都為阻塞，比如取不到一直等待，使用到了Condition，調用了await，底層用到了park，進入wait狀态）

Queue對線程友好的api：offer、peek、poll ，BlockingQueue在原基礎上添加了put、take（阻塞）

LinkedBlockingQueue（無界隊列）

ArrayBlockingQueue（有界隊列）

使用 ReentrantLock 和 Condition 實作一個阻塞隊列

DelayQueue

延遲隊列提供了在指定時間才能擷取隊列元素的功能，可用作任務排程。

SynchronousQueue（同步隊列）

實際上它不是一個真正的隊列，因為它不會為隊列中元素維護存儲空間。與其他隊列不同的是，它維護一組線程，這些線程在等待着把元素加入或移出隊列。（輕量級）可用來線上程間安全的交換單一進制素。

SynchronousQueue沒有存儲功能，是以put和take會一直阻塞，直到有另一個線程已經準備好參與到傳遞過程中。僅當有足夠多的消費者，并且總是有一個消費者準備好擷取傳遞的工作時，才适合使用同步隊列。

TransferQueue（LinkedTransferQueue無界阻塞隊列）

LinkedBolckingQueue 和 SynchronousQueue 和合體

相比較 SynchronousQueue 多了一個可以存儲的隊列，相比較LinkedBlockingQueue 多了直接傳遞元素，少了用鎖來同步。性能更高，用處更大。

當 put 時，如果有等待的線程，就直接将元素 “交給” 等待者， 否則直接進入隊列。put和 transfer 方法的差別是，put 是立即傳回的， transfer 是阻塞等待消費者拿到資料才傳回。transfer方法和 SynchronousQueue的 put 方法類似。

eg：顧客付錢完成後，才能回報。

PriorityQueue

基于優先級的無界優先級隊列。優先級隊列的元素按照其自然順序進行排序，或者根據構造隊列時提供的 Comparator 進行排序，具體取決于所使用的構造方法。該隊列不允許使用 null 元素也不允許插入不可比較的對象(沒有實作Comparable接口的對象)。

内部實作-2叉樹（堆排序）