ConcurrentLinkedQueue

無(wú)界非阻塞隊(duì)列，它是一個(gè)基于鏈表的無(wú)界線程安全隊(duì)列歌粥。該隊(duì)列的元素 遵循先進(jìn)先出的原則塌忽。頭是最先加入的，尾是最近加入的失驶。插入元素是追加到尾上土居。提取一個(gè)元素是從頭提取。

大家可以看成是 LinkedList 的并發(fā)版本嬉探，常用方法：

concurrentLinkedQueue.add(“c”);

concurrentLinkedQueue.offer(“d”);//將指定元素插入到此隊(duì)列的尾部擦耀。

concurrentLinkedQueue.peek();//檢索并不移除此隊(duì)列的頭，如果此隊(duì)列為空涩堤，則返回null埂奈。?

concurrentLinkedQueue.poll();//檢索并移除此隊(duì)列的頭，如果此隊(duì)列為空定躏， 則返回null账磺。

寫(xiě)時(shí)復(fù)制容器

什么是寫(xiě)時(shí)復(fù)制容器

CopyOnWriteArrayList 和 CopyOnWriteArraySet

CopyOnWrite 容器即寫(xiě)時(shí)復(fù)制的容器。通俗的理解是當(dāng)我們往一個(gè)容器添加 元素的時(shí)候痊远，不直接往當(dāng)前容器添加垮抗，而是先將當(dāng)前容器進(jìn)行Copy，復(fù)制出一 個(gè)新的容器碧聪，然后新的容器里添加元素冒版，添加完元素之后，再將原容器的引用指 向新的容器逞姿。這樣做的好處是我們可以對(duì) CopyOnWrite 容器進(jìn)行并發(fā)的讀辞嗡，而不需要加鎖， 因?yàn)楫?dāng)前容器不會(huì)添加任何元素滞造。所以CopyOnWrite 容器也是一種讀寫(xiě)分離的思 想续室，讀和寫(xiě)不同的容器。如果讀的時(shí)候有多個(gè)線程正在向CopyOnWriteArrayList 添加數(shù)據(jù)谒养，讀還是會(huì)讀到舊的數(shù)據(jù)挺狰，因?yàn)閷?xiě)的時(shí)候不會(huì)鎖住舊的CopyOnWriteArrayList。CopyOnWrite 并發(fā)容器用于對(duì)于絕大部分訪問(wèn)都是讀买窟，且只是偶爾寫(xiě)的并發(fā)場(chǎng)景丰泊。比如白名單，黑名單始绍，商品類(lèi)目的訪問(wèn)和更新場(chǎng)景瞳购，假如我們有一個(gè)搜索網(wǎng)站，用戶在這個(gè)網(wǎng)站的搜索框中亏推，輸入關(guān)鍵字搜索內(nèi)容学赛，但是某些關(guān)鍵字不允許被搜索年堆。這些不能被搜索的關(guān)鍵字會(huì)被放在一個(gè)黑名單當(dāng)中，黑名單每天晚上更新一次罢屈。當(dāng)用戶搜索時(shí)，會(huì)檢查當(dāng)前關(guān)鍵字在不在黑名單當(dāng)中篇亭，如果在缠捌，則提示不能搜索。

使用 CopyOnWriteMap 需要注意兩件事情：

減少擴(kuò)容開(kāi)銷(xiāo)译蒂。根據(jù)實(shí)際需要曼月，初始化 CopyOnWriteMap 的大小， 避免寫(xiě)時(shí) CopyOnWriteMap 擴(kuò)容的開(kāi)銷(xiāo)柔昼。

使用批量添加哑芹。因?yàn)槊看翁砑樱萜髅看味紩?huì)進(jìn)行復(fù)制捕透，所以減少添加 次數(shù)聪姿，可以減少容器的復(fù)制次數(shù)。

寫(xiě)時(shí)復(fù)制容器的問(wèn)題

性能問(wèn)題

每次修改都創(chuàng)建一個(gè)新數(shù)組乙嘀，然后復(fù)制所有內(nèi)容末购，如果數(shù)組比較大，修改操 作又比較頻繁虎谢，可以想象盟榴，性能是很低的，而且內(nèi)存開(kāi)銷(xiāo)會(huì)很大婴噩。

數(shù)據(jù)一致性問(wèn)題

CopyOnWrite 容器只能保證數(shù)據(jù)的最終一致性擎场，不能保證數(shù)據(jù)的實(shí)時(shí)一致性。 所以如果你希望寫(xiě)入的的數(shù)據(jù)几莽，馬上能讀到迅办，不要使用 CopyOnWrite 容器。

阻塞隊(duì)列BlockingQueue

隊(duì)列

隊(duì)列是一種特殊的線性表章蚣，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作礼饱，而在表的后端（rear）進(jìn)行插入操作，和棧一樣究驴，隊(duì)列是一種操作受限制的線性表镊绪。進(jìn)行插入操作的端稱(chēng)為隊(duì)尾，進(jìn)行刪除操作的端稱(chēng)為隊(duì)頭洒忧。

在隊(duì)列中插入一個(gè)隊(duì)列元素稱(chēng)為入隊(duì)蝴韭，從隊(duì)列中刪除一個(gè)隊(duì)列元素稱(chēng)為出隊(duì)。 因?yàn)殛?duì)列只允許在一端插入熙侍，在另一端刪除榄鉴，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除履磨，故隊(duì)列又稱(chēng)為先進(jìn)先出（FIFO—firstinfirstout）線性表。

什么是阻塞隊(duì)列

1）支持阻塞的插入方法：意思是當(dāng)隊(duì)列滿時(shí)庆尘，隊(duì)列會(huì)阻塞插入元素的線程剃诅， 直到隊(duì)列不滿。

2）支持阻塞的移除方法：意思是在隊(duì)列為空時(shí)驶忌，獲取元素的線程會(huì)等待隊(duì) 列變?yōu)榉强铡?/p>

在并發(fā)編程中使用生產(chǎn)者和消費(fèi)者模式能夠解決絕大多數(shù)并發(fā)問(wèn)題矛辕。該模式 通過(guò)平衡生產(chǎn)線程和消費(fèi)線程的工作能力來(lái)提高程序整體處理數(shù)據(jù)的速度。

在線程世界里付魔，生產(chǎn)者就是生產(chǎn)數(shù)據(jù)的線程聊品，消費(fèi)者就是消費(fèi)數(shù)據(jù)的線程。 在多線程開(kāi)發(fā)中几苍，如果生產(chǎn)者處理速度很快翻屈，而消費(fèi)者處理速度很慢，那么生產(chǎn) 者就必須等待消費(fèi)者處理完妻坝，才能繼續(xù)生產(chǎn)數(shù)據(jù)伸眶。同樣的道理，如果消費(fèi)者的處 理能力大于生產(chǎn)者刽宪，那么消費(fèi)者就必須等待生產(chǎn)者赚抡。

為了解決這種生產(chǎn)消費(fèi)能力不均衡的問(wèn)題，便有了生產(chǎn)者和消費(fèi)者模式纠屋。生 產(chǎn)者和消費(fèi)者模式是通過(guò)一個(gè)容器來(lái)解決生產(chǎn)者和消費(fèi)者的強(qiáng)耦合問(wèn)題涂臣。生產(chǎn)者 和消費(fèi)者彼此之間不直接通信，而是通過(guò)阻塞隊(duì)列來(lái)進(jìn)行通信售担，所以生產(chǎn)者生產(chǎn) 完數(shù)據(jù)之后不用等待消費(fèi)者處理赁遗，直接扔給阻塞隊(duì)列，消費(fèi)者不找生產(chǎn)者要數(shù)據(jù)族铆， 而是直接從阻塞隊(duì)列里取岩四，阻塞隊(duì)列就相當(dāng)于一個(gè)緩沖區(qū)，平衡了生產(chǎn)者和消費(fèi) 者的處理能力哥攘。

阻塞隊(duì)列常用于生產(chǎn)者和消費(fèi)者的場(chǎng)景剖煌，生產(chǎn)者是向隊(duì)列里添加元素的線程， 消費(fèi)者是從隊(duì)列里取元素的線程逝淹。阻塞隊(duì)列就是生產(chǎn)者用來(lái)存放元素耕姊、消費(fèi)者用 來(lái)獲取元素的容器。

拋出異常：當(dāng)隊(duì)列滿時(shí)栅葡，如果再往隊(duì)列里插入元素茉兰，會(huì)拋出 IllegalStateException（“Queuefull”）異常。當(dāng)隊(duì)列空時(shí)欣簇，從隊(duì)列里獲取元素會(huì)拋 出 NoSuchElementException 異常规脸。

返回特殊值：當(dāng)往隊(duì)列插入元素時(shí)坯约，會(huì)返回元素是否插入成功，成功返回 true莫鸭。如果是移除方法闹丐，則是從隊(duì)列里取出一個(gè)元素，如果沒(méi)有則返回 null被因。

一直阻塞：當(dāng)阻塞隊(duì)列滿時(shí)卿拴，如果生產(chǎn)者線程往隊(duì)列里 put 元素，隊(duì)列會(huì) 一直阻塞生產(chǎn)者線程氏身，直到隊(duì)列可用或者響應(yīng)中斷退出巍棱。當(dāng)隊(duì)列空時(shí)惑畴，如果消費(fèi) 者線程從隊(duì)列里 take 元素蛋欣，隊(duì)列會(huì)阻塞住消費(fèi)者線程，直到隊(duì)列不為空如贷。

超時(shí)退出：當(dāng)阻塞隊(duì)列滿時(shí)陷虎，如果生產(chǎn)者線程往隊(duì)列里插入元素，隊(duì)列會(huì) 阻塞生產(chǎn)者線程一段時(shí)間杠袱，如果超過(guò)了指定的時(shí)間尚猿，生產(chǎn)者線程就會(huì)退出。

常用阻塞隊(duì)列

ArrayBlockingQueue：一個(gè)由數(shù)組結(jié)構(gòu)組成的有界阻塞隊(duì)列楣富。

LinkedBlockingQueue：一個(gè)由鏈表結(jié)構(gòu)組成的有界阻塞隊(duì)列。

PriorityBlockingQueue：一個(gè)支持優(yōu)先級(jí)排序的無(wú)界阻塞隊(duì)列纹蝴。

DelayQueue：一個(gè)使用優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)的無(wú)界阻塞隊(duì)列庄萎。

SynchronousQueue：一個(gè)不存儲(chǔ)元素的阻塞隊(duì)列。

LinkedTransferQueue：一個(gè)由鏈表結(jié)構(gòu)組成的無(wú)界阻塞隊(duì)列塘安。

LinkedBlockingDeque：一個(gè)由鏈表結(jié)構(gòu)組成的雙向阻塞隊(duì)列糠涛。

有界無(wú)界 ？

有限隊(duì)列就是長(zhǎng)度有限兼犯，滿了以后生產(chǎn)者會(huì)阻塞忍捡，無(wú)界隊(duì)列就是里面能放 無(wú)數(shù)的東西而不會(huì)因?yàn)殛?duì)列長(zhǎng)度限制被阻塞，當(dāng)然空間限制來(lái)源于系統(tǒng)資源的限制切黔，如果處理不及時(shí)砸脊，導(dǎo)致隊(duì)列越來(lái)越大越來(lái)越大，超出一定的限制致使內(nèi)存超 限纬霞，操作系統(tǒng)或者 JVM 幫你解決煩惱脓规，直接把你 OOMkill省事了。

ArrayBlockingQueue

是一個(gè)用數(shù)組實(shí)現(xiàn)的有界阻塞隊(duì)列险领。此隊(duì)列按照先進(jìn)先出（FIFO）的原則對(duì)元素進(jìn)行排序侨舆。默認(rèn)情況下不保證線程公平的訪問(wèn)隊(duì)列秒紧，所謂公平訪問(wèn)隊(duì)列是指阻塞的線程，可以按照阻塞的先后順序訪問(wèn)隊(duì)列挨下，即先阻塞線程先訪問(wèn)隊(duì)列熔恢。非公平性是對(duì)先等待的線程是非公平的，當(dāng)隊(duì)列可用時(shí)臭笆，阻塞的線程都可以爭(zhēng)奪訪問(wèn)隊(duì)列的資格叙淌，有可能先阻塞的線程最后才訪問(wèn)隊(duì)列。初始化時(shí)有參數(shù)可以設(shè)置

LinkedBlockingQueue

是一個(gè)用鏈表實(shí)現(xiàn)的有界阻塞隊(duì)列愁铺。此隊(duì)列的默認(rèn)和最大長(zhǎng)度為 Integer.MAX_VALUE鹰霍。此隊(duì)列按照先進(jìn)先出的原則對(duì)元素進(jìn)行排序。

Array實(shí)現(xiàn) 和 Linked實(shí)現(xiàn)的區(qū)別

隊(duì)列中鎖的實(shí)現(xiàn)不同

ArrayBlockingQueue 實(shí)現(xiàn)的隊(duì)列中的鎖是沒(méi)有分離的茵乱，即生產(chǎn)和消費(fèi)用的是同一個(gè)鎖茂洒；

LinkedBlockingQueue 實(shí)現(xiàn)的隊(duì)列中的鎖是分離的，即生產(chǎn)用的是 putLock瓶竭， 消費(fèi)是 takeLock

在生產(chǎn)或消費(fèi)時(shí)操作不同

ArrayBlockingQueue 實(shí)現(xiàn)的隊(duì)列中在生產(chǎn)和消費(fèi)的時(shí)候督勺，是直接將枚舉對(duì)象 插入或移除的；

LinkedBlockingQueue 實(shí)現(xiàn)的隊(duì)列中在生產(chǎn)和消費(fèi)的時(shí)候斤贰，需要把枚舉對(duì)象轉(zhuǎn) 換為 Node進(jìn)行插入或移除智哀，會(huì)影響性能

隊(duì)列大小初始化方式不同

ArrayBlockingQueue 實(shí)現(xiàn)的隊(duì)列中必須指定隊(duì)列的大小荧恍；

LinkedBlockingQueue 實(shí)現(xiàn)的隊(duì)列中可以不指定隊(duì)列的大小瓷叫，但是默認(rèn)是 Integer.MAX_VALUE

PriorityBlockingQueue

PriorityBlockingQueue 是一個(gè)支持優(yōu)先級(jí)的無(wú)界阻塞隊(duì)列。默認(rèn)情況下元素 采取自然順序升序排列送巡。也可以自定義類(lèi)實(shí)現(xiàn)compareTo()方法來(lái)指定元素排序 規(guī)則摹菠，或者初始化 PriorityBlockingQueue 時(shí)，指定構(gòu)造參數(shù)Comparator 來(lái)對(duì)元素 進(jìn)行排序授艰。需要注意的是不能保證同優(yōu)先級(jí)元素的順序辨嗽。

DelayQueue

是一個(gè)支持延時(shí)獲取元素的無(wú)界阻塞隊(duì)列。隊(duì)列使用 PriorityQueue 來(lái)實(shí)現(xiàn)淮腾。 隊(duì)列中的元素必須實(shí)現(xiàn) Delayed接口糟需，在創(chuàng)建元素時(shí)可以指定多久才能從隊(duì)列中 獲取當(dāng)前元素。只有在延遲期滿時(shí)才能從隊(duì)列中提取元素谷朝。

DelayQueue 非常有用洲押，可以將 DelayQueue 運(yùn)用在以下應(yīng)用場(chǎng)景。

緩存系統(tǒng)的設(shè)計(jì)：可以用 DelayQueue 保存緩存元素的有效期圆凰，使用一個(gè)線 程循環(huán)查詢 DelayQueue杈帐，一旦能從 DelayQueue 中獲取元素時(shí)，表示緩存有效期 到了。還有訂單到期挑童，限時(shí)支付等等

SynchronousQueue?

是一個(gè)不存儲(chǔ)元素的阻塞隊(duì)列累铅。每一個(gè) put 操作必須等待一個(gè) take 操作， 否則不能繼續(xù)添加元素站叼。SynchronousQueue可以看成是一個(gè)傳球手娃兽，負(fù)責(zé)把生 產(chǎn)者線程處理的數(shù)據(jù)直接傳遞給消費(fèi)者線程。隊(duì)列本身并不存儲(chǔ)任何元素尽楔，非常適合傳遞性場(chǎng)景投储。SynchronousQueue 的吞吐量高于 LinkedBlockingQueue 和ArrayBlockingQueue。

LinkedTransferQueue

多了 tryTransfer 和 transfer 方法;

(1)transfer 方法

如果當(dāng)前有消費(fèi)者正在等待接收元素（消費(fèi)者使用 take()方法或帶時(shí)間限制 的 poll()方法時(shí)）阔馋，transfer方法可以把生產(chǎn)者傳入的元素立刻 transfer（傳輸） 給消費(fèi)者玛荞。如果沒(méi)有消費(fèi)者在等待接收元素，transfer 方法會(huì)將元素存放在隊(duì)列 的 tail 節(jié)點(diǎn)呕寝，并等到該元素被消費(fèi)者消費(fèi)了才返回勋眯。

(2)tryTransfer 方法

tryTransfer 方法是用來(lái)試探生產(chǎn)者傳入的元素是否能直接傳給消費(fèi)者。如果 沒(méi)有消費(fèi)者等待接收元素壁涎，則返回 false凡恍。和transfer 方法的區(qū)別是 tryTransfer 方 法無(wú)論消費(fèi)者是否接收志秃，方法立即返回怔球，而 transfer方法是必須等到消費(fèi)者消費(fèi) 了才返回。

LinkedBlockingDeque

LinkedBlockingDeque 是一個(gè)由鏈表結(jié)構(gòu)組成的雙向阻塞隊(duì)列浮还。所謂雙向隊(duì)列指的是可以從隊(duì)列的兩端插入和移出元素竟坛。雙向隊(duì)列因?yàn)槎嗔艘粋€(gè)操作隊(duì)列的入 口，在多線程同時(shí)入隊(duì)時(shí)钧舌，也就減少了一半的競(jìng)爭(zhēng)担汤。

多了 addFirst、addLast洼冻、offerFirst崭歧、offerLast、peekFirst 和 peekLast 等方法撞牢， 以First 單詞結(jié)尾的方法率碾，表示插入、獲任荼搿（peek）或移除雙端隊(duì)列的第一個(gè)元 素所宰。以 Last 單詞結(jié)尾的方法，表示插入畜挥、獲取或移除雙端隊(duì)列的最后一個(gè)元素仔粥。 另外，插入方法 add 等同于 addLast，移除方法 remove 等效于 removeFirst躯泰。但 是take方法卻等同于 takeFirst谭羔， 不知道是不是JDK的 bug，使用時(shí)還是用帶有First 和 Last 后綴的方法更清楚麦向。在初始化 LinkedBlockingDeque 時(shí)可以設(shè)置容量防止其過(guò)度膨脹口糕。另外，雙向阻塞隊(duì)列可以運(yùn)用在“工作竊取”模式中磕蛇。

了解阻塞隊(duì)列的實(shí)現(xiàn)原理

使用了等待通知模式實(shí)現(xiàn)景描。所謂通知模式，就是當(dāng)生產(chǎn)者往滿的隊(duì)列里添加 元素時(shí)會(huì)阻塞住生產(chǎn)者秀撇，當(dāng)消費(fèi)者消費(fèi)了一個(gè)隊(duì)列中的元素后超棺，會(huì)通知生產(chǎn)者當(dāng)前隊(duì)列可用。通過(guò)查看 JDK 源碼發(fā)現(xiàn) ArrayBlockingQueue 使用了 Condition 來(lái)實(shí) 現(xiàn)呵燕。其余隊(duì)列的實(shí)現(xiàn)棠绘，大家可以自行查看，隊(duì)列的實(shí)現(xiàn)的代碼總體來(lái)說(shuō)再扭，并不復(fù)雜氧苍。