一映砖、同步容器

?? 在Java中，同步容器主要包括2類：

　　1）Vector灾挨、Stack邑退、HashTable

　　2）Collections類中提供的靜態(tài)工廠方法創(chuàng)建的類

　　Vector實(shí)現(xiàn)了List接口，Vector實(shí)際上就是一個(gè)數(shù)組劳澄，和ArrayList類似地技，但是Vector中的方法都是synchronized方法，即進(jìn)行了同步措施秒拔。

　　Stack也是一個(gè)同步容器莫矗，它的方法也用synchronized進(jìn)行了同步，它實(shí)際上是繼承于Vector類砂缩。

? ? ? ?HashTable實(shí)現(xiàn)了Map接口作谚，它和HashMap很相似，但是HashTable進(jìn)行了同步處理梯轻，而HashMap沒有。

Collections類是一個(gè)工具提供類尽棕，注意喳挑，它和Collection不同，Collection是一個(gè)頂層的接口滔悉。在Collections類中提供了大量的方法伊诵，比如對(duì)集合或者容器進(jìn)行排序、查找等操作回官。最重要的是曹宴，在它里面提供了幾個(gè)靜態(tài)工廠方法來創(chuàng)建同步容器類，如：

Collectinons.synchronizedList()

Collections.synchronizedSet()

Collections.synchronizedMap()

Collections.synchronizedSortedSet()

Collections.synchronizedSortedMap()

缺點(diǎn)：

1歉提、通過同步方法將訪問操作串行化笛坦，導(dǎo)致并發(fā)環(huán)境下效率低下

2区转、復(fù)合操作（迭代、條件運(yùn)算如沒有則添加等）非線程安全版扩，需要客戶端代碼來實(shí)現(xiàn)加鎖

二废离、并發(fā)容器

理解基本的線程安全工具。

理解傳統(tǒng)集合框架并發(fā)編程中Map存在的問題礁芦，清楚簡單同步方式的不足蜻韭。

梳理并發(fā)包內(nèi)，尤其是ConcurrentHashMap采取了哪些方法來提高并發(fā)表現(xiàn)柿扣。

最好能掌握ConcurrentHashMap自身的演進(jìn)肖方。

?? 1）ConcurrentHashMap

????? 為什么需要ConcurrentHashMap？

????? Hashtable或者同步包裝版本未状，只是在方法前加synchronized俯画，導(dǎo)致所有的并發(fā)操作都要競爭同一把鎖，一個(gè)線程在進(jìn)行同步操作時(shí)娩践，其他線程只能等待活翩，大大降低了并發(fā)操作的效率。只是適合在非高度并發(fā)的場景下翻伺。

????? 早期ConcurrentHashMap材泄，其實(shí)是基于：

????????* 分離鎖，也就是將內(nèi)部進(jìn)行分段（Segment）吨岭，里面則是HashEntry的數(shù)組拉宗，和HashMap類似，哈希相同的條目也是以鏈表形式存儲(chǔ)辣辫。

????????* HashEntry內(nèi)部使用volatile的value字段來保證可見性旦事，也利用了不可變對(duì)象的機(jī)制以改進(jìn)利用Unsafe提供的底層能力去直接完成部分操作，以優(yōu)化性能急灭。

????? ConcurrentHashMap最關(guān)鍵的是要理解一個(gè)概念：Segment姐浮，Segment是什么呢？Segment本身就相當(dāng)于一個(gè)HashMap對(duì)象葬馋。同HashMap一樣卖鲤，Segment包含一個(gè)HashEntry數(shù)組，數(shù)組中的每一個(gè)HashEntry既是一個(gè)鍵值對(duì)畴嘶，也是一個(gè)鏈表的頭節(jié)點(diǎn)蛋逾。

單一的Segment結(jié)構(gòu)如下：

像這樣的Segment對(duì)象，在ConcurrentHashMap集合中有多少個(gè)呢窗悯？有2的N次方個(gè)区匣，共同保存在一個(gè)名為segments的數(shù)組當(dāng)中。

因此整個(gè)ConcurrentHashMap的結(jié)構(gòu)如下：

可以說蒋院，ConcurrentHashMap是一個(gè)二級(jí)哈希表亏钩。在一個(gè)總的哈希表下面莲绰，有若干個(gè)子哈希表。

ConcurrentHashMap優(yōu)勢就是采用了[鎖分段技術(shù)]铸屉，每一個(gè)Segment就好比一個(gè)自治區(qū)钉蒲，讀寫操作高度自治，Segment之間互不影響彻坛。

并發(fā)讀寫的幾種情形：

Case1：不同Segment的并發(fā)寫入

不同Segment的寫入是可以并發(fā)執(zhí)行的顷啼。

Case2：同一Segment的一寫一讀

同一Segment的寫和讀是可以并發(fā)執(zhí)行的。

Case3：同一Segment的并發(fā)寫入

Segment的寫入是需要上鎖的昌屉，因此對(duì)同一Segment的并發(fā)寫入會(huì)被阻塞钙蒙。

由此可見，ConcurrentHashMap當(dāng)中每個(gè)Segment通過繼承ReentrantLock來進(jìn)行加鎖间驮，各自持有一把鎖躬厌。在保證線程安全的同時(shí)降低了鎖的粒度，讓并發(fā)操作效率更高竞帽。

ConcurrentHashMap讀寫詳細(xì)過程：

Get方法：

1.為輸入的Key做Hash運(yùn)算扛施，得到hash值。

2.通過hash值屹篓，定位到對(duì)應(yīng)的Segment對(duì)象

3.再次通過hash值疙渣，定位到Segment當(dāng)中數(shù)組的具體位置。

Put方法：

1.為輸入的Key做Hash運(yùn)算堆巧，得到hash值妄荔。

2.通過hash值，定位到對(duì)應(yīng)的Segment對(duì)象

3.獲取可重入鎖

4.再次通過hash值谍肤，定位到Segment當(dāng)中數(shù)組的具體位置啦租。

5.插入或覆蓋HashEntry對(duì)象。

6.釋放鎖荒揣。

從上述步驟可以看出篷角，ConcurrentHashMap在讀寫時(shí)都需要二次定位，首先定位到Segment系任，之后定位到Segment內(nèi)的具體數(shù)組下標(biāo)恳蹲。

Size方法：

既然每個(gè)Segment都各自加鎖，那么在調(diào)用Size方法的時(shí)候赋除，怎么解決一致性的問題呢阱缓？

Size方法的目的是統(tǒng)計(jì)ConcurrentHashMap的總元素?cái)?shù)量非凌， 自然需要把各個(gè)Segment內(nèi)部的元素?cái)?shù)量匯總起來举农。

但是，如果在統(tǒng)計(jì)Segment元素?cái)?shù)量的過程中敞嗡，已統(tǒng)計(jì)過的Segment瞬間插入新的元素颁糟，這時(shí)候該怎么辦呢航背？

ConcurrentHashMap的Size方法是一個(gè)嵌套循環(huán)，大體邏輯如下：

1.遍歷所有的Segment棱貌。

2.把Segment的元素?cái)?shù)量累加起來玖媚。

3.把Segment的修改次數(shù)累加起來。

4.判斷所有Segment的總修改次數(shù)是否大于上一次的總修改次數(shù)婚脱。如果大于今魔，說明統(tǒng)計(jì)過程中有修改，重新統(tǒng)計(jì)障贸，嘗試次數(shù)+1错森；如果不是。說明沒有修改篮洁，統(tǒng)計(jì)結(jié)束涩维。

5.如果嘗試次數(shù)超過閾值，則對(duì)每一個(gè)Segment加鎖袁波，再重新統(tǒng)計(jì)瓦阐。

6.再次判斷所有Segment的總修改次數(shù)是否大于上一次的總修改次數(shù)。由于已經(jīng)加鎖篷牌，次數(shù)一定和上次相等睡蟋。

7.釋放鎖，統(tǒng)計(jì)結(jié)束娃磺。

為什么這樣設(shè)計(jì)呢薄湿？這種思想和樂觀鎖悲觀鎖的思想如出一轍。

為了盡量不鎖住所有Segment偷卧，首先樂觀地假設(shè)Size過程中不會(huì)有修改豺瘤。當(dāng)嘗試一定次數(shù)(最多3次)，才無奈轉(zhuǎn)為悲觀鎖听诸，鎖住所有Segment保證強(qiáng)一致性坐求。

ConcurrentHashMap在jdk1.7和jdk1.8的區(qū)別：

* 總體結(jié)構(gòu)上，它的內(nèi)部存儲(chǔ)變得和HashMap結(jié)構(gòu)非常相似晌梨，同樣是大的桶數(shù)組桥嗤，然后內(nèi)部也是一個(gè)個(gè)所謂的鏈表結(jié)構(gòu)，同步的粒度要更細(xì)致一些仔蝌。

* 其內(nèi)部仍然有Segment定義泛领，但僅僅是為了保證序列化時(shí)的兼容性而已，不再有任何結(jié)構(gòu)上的用處敛惊。

* 因?yàn)椴辉偈褂肧egment渊鞋，初始化操作大大簡化，修改為lazy-load形式，這樣可以避免初始開銷锡宋，解決了老版本很多人抱怨的這一點(diǎn)儡湾。

* 數(shù)據(jù)存儲(chǔ)利用volatile保證可見性。

* 使用CAS等操作执俩，在特定場景進(jìn)行無鎖并發(fā)操作徐钠。

* 使用Unsafe、LongAdder之類的底層手段役首，進(jìn)行極端情況的優(yōu)化尝丐。

Java 7中的ConcurrentHashMap的底層數(shù)據(jù)結(jié)構(gòu)仍然是數(shù)組和鏈表。與HashMap不同的是衡奥，ConcurrentHashMap最外層不是一個(gè)大的數(shù)組摊崭，而是一個(gè)Segment的數(shù)組。每個(gè)Segment包含一個(gè)與HashMap數(shù)據(jù)結(jié)構(gòu)差不多的鏈表數(shù)組杰赛。結(jié)構(gòu)如下：

Java 7為實(shí)現(xiàn)并行訪問呢簸，引入了Segment這一結(jié)構(gòu)，實(shí)現(xiàn)了分段鎖乏屯，理論上最大并發(fā)度與Segment個(gè)數(shù)相等根时。Java 8為進(jìn)一步提高并發(fā)性，摒棄了分段鎖的方案辰晕，而是直接使用一個(gè)大的數(shù)組蛤迎，采用Node + CAS + Synchronized來保證并發(fā)安全進(jìn)行實(shí)現(xiàn)。同時(shí)為了提高哈希碰撞下的尋址性能含友，Java 8在鏈表長度超過一定閾值（8）時(shí)將鏈表（尋址時(shí)間復(fù)雜度為O(N)）轉(zhuǎn)換為紅黑樹（尋址時(shí)間復(fù)雜度為O(long(N))）谓厘。

可以理解為囚玫，Java8相當(dāng)于把Segment分段鎖更細(xì)粒度了翻默，每個(gè)數(shù)組元素就是原來的一個(gè)Segment隧期，那并發(fā)讀就由原來的Segment數(shù)變?yōu)閿?shù)組長度了。然后用到了CAS樂觀鎖惠赫，所以能支持更高的并發(fā)把鉴。

Java8的ConcurrentHashMap結(jié)構(gòu)如下：

對(duì)于put操作，如果Key對(duì)應(yīng)的數(shù)組元素為null儿咱，則通過CAS操作將其設(shè)置為當(dāng)前值庭砍。如果Key對(duì)應(yīng)的數(shù)組元素（也即鏈表表頭或者樹的根元素）不為null，則對(duì)該元素使用synchronized關(guān)鍵字申請鎖混埠，然后進(jìn)行操作怠缸。在同步邏輯上為什么使用的是synchronized，而不是通常建議的ReentrantLock之類钳宪？現(xiàn)在JDK中揭北，synchronized已經(jīng)被不斷優(yōu)化概耻，可以不再過分擔(dān)心性能差異，另外罐呼，相比ReentrantLock，它可以減少內(nèi)存消耗侦高，這是個(gè)非常大的優(yōu)勢嫉柴。如果該put操作使得當(dāng)前鏈表長度超過一定閾值，則將該鏈表轉(zhuǎn)換為樹奉呛，從而提高尋址效率计螺。

對(duì)于讀操作，由于數(shù)組被volatile關(guān)鍵字修飾瞧壮，因此不用擔(dān)心數(shù)組的可見性問題登馒。同時(shí)每個(gè)元素是一個(gè)Node實(shí)例（Java 7中每個(gè)元素是一個(gè)HashEntry），它的Key值和hash值都由final修飾咆槽，不可變更陈轿，無須關(guān)心它們被修改后的可見性問題。而其Value及對(duì)下一個(gè)元素的引用由volatile修飾秦忿，可見性也有保障麦射。

2）CopyOnWriteArrayList和CopyOnWriteArraySet

?? CopyOnWriteArrayList是Java并發(fā)包中提供的一個(gè)并發(fā)容器，它是個(gè)線程安全且讀操作無鎖的ArrayList灯谣，寫操作則通過創(chuàng)建底層數(shù)組的新副本來實(shí)現(xiàn)潜秋，是一種讀寫分離的并發(fā)策略，我們也可以稱這種容器為"寫時(shí)復(fù)制器"胎许，Java并發(fā)包中類似的容器還有CopyOnWriteArraySet峻呛。

實(shí)現(xiàn)原理

　　我們都知道，集合框架中的ArrayList是非線程安全的辜窑，Vector雖是線程安全的钩述，但由于簡單粗暴的鎖同步機(jī)制，性能較差穆碎。而CopyOnWriteArrayList則提供了另一種不同的并發(fā)處理策略（當(dāng)然是針對(duì)特定的并發(fā)場景）切距。

很多時(shí)候，我們的系統(tǒng)應(yīng)對(duì)的都是讀多寫少的并發(fā)場景惨远。CopyOnWriteArrayList容器允許并發(fā)讀谜悟，讀操作是無鎖的，性能較高北秽。至于寫操作葡幸，比如向容器中添加一個(gè)元素，則首先將當(dāng)前容器復(fù)制一份贺氓，然后在新副本上執(zhí)行寫操作蔚叨，結(jié)束之后再將原容器的引用指向新容器。

優(yōu)缺點(diǎn)分析

　　了解了CopyOnWriteArrayList的實(shí)現(xiàn)原理，分析它的優(yōu)缺點(diǎn)及使用場景就很容易了蔑水。

　　優(yōu)點(diǎn)：

　　讀操作性能很高邢锯，因?yàn)闊o需任何同步措施，比較適用于讀多寫少的并發(fā)場景搀别。Java的list在遍歷時(shí)丹擎，若中途有別的線程對(duì)list容器進(jìn)行修改，則會(huì)拋出ConcurrentModificationException異常歇父。而CopyOnWriteArrayList由于其"讀寫分離"的思想蒂培，遍歷和修改操作分別作用在不同的list容器，所以在使用迭代器進(jìn)行遍歷時(shí)候榜苫，也就不會(huì)拋出ConcurrentModificationException異常了

　　缺點(diǎn)：

缺點(diǎn)也很明顯护戳，一是內(nèi)存占用問題，畢竟每次執(zhí)行寫操作都要將原容器拷貝一份垂睬，數(shù)據(jù)量大時(shí)媳荒，對(duì)內(nèi)存壓力較大，可能會(huì)引起頻繁GC驹饺；二是無法保證實(shí)時(shí)性肺樟，Vector對(duì)于讀寫操作均加鎖同步，可以保證讀和寫的強(qiáng)一致性逻淌。而CopyOnWriteArrayList由于其實(shí)現(xiàn)策略的原因么伯，寫和讀分別作用在新老不同容器上，在寫操作執(zhí)行過程中卡儒，讀不會(huì)阻塞但讀取到的卻是老容器的數(shù)據(jù)田柔。

3）阻塞隊(duì)列

???? ?使用非阻塞隊(duì)列的時(shí)候有一個(gè)很大問題就是：它不會(huì)對(duì)當(dāng)前線程產(chǎn)生阻塞，那么在面對(duì)類似消費(fèi)者-生產(chǎn)者的模型時(shí)骨望，就必須額外地實(shí)現(xiàn)同步策略以及線程間喚醒策略硬爆，這個(gè)實(shí)現(xiàn)起來就非常麻煩。但是有了阻塞隊(duì)列就不一樣了擎鸠，它會(huì)對(duì)當(dāng)前線程產(chǎn)生阻塞缀磕，比如一個(gè)線程從一個(gè)空的阻塞隊(duì)列中取元素，此時(shí)線程會(huì)被阻塞直到阻塞隊(duì)列中有了元素劣光。當(dāng)隊(duì)列中有元素后袜蚕，被阻塞的線程會(huì)自動(dòng)被喚醒（不需要我們編寫代碼去喚醒）。這樣提供了極大的方便性绢涡。

?????? 阻塞隊(duì)列（BlockingQueue）是一個(gè)支持兩個(gè)附加操作的隊(duì)列牲剃。這兩個(gè)附加的操作是：在隊(duì)列為空時(shí)，獲取元素的線程會(huì)等待隊(duì)列變?yōu)榉强招劭伞．?dāng)隊(duì)列滿時(shí)凿傅，存儲(chǔ)元素的線程會(huì)等待隊(duì)列可用缠犀。阻塞隊(duì)列常用于生產(chǎn)者和消費(fèi)者的場景，生產(chǎn)者是往隊(duì)列里添加元素的線程聪舒，消費(fèi)者是從隊(duì)列里拿元素的線程辨液。阻塞隊(duì)列就是生產(chǎn)者存放元素的容器，而消費(fèi)者也只從容器里拿元素箱残。阻塞隊(duì)列用Condition接口的await和signal方法實(shí)現(xiàn)滔迈。

當(dāng)隊(duì)列中沒有數(shù)據(jù)的情況下，消費(fèi)者端的所有線程都會(huì)被自動(dòng)阻塞（掛起）疚宇，直到有數(shù)據(jù)放入隊(duì)列：

當(dāng)隊(duì)列中填滿數(shù)據(jù)的情況下，生產(chǎn)者端的所有線程都會(huì)被自動(dòng)阻塞（掛起）赏殃，直到隊(duì)列中有空的位置敷待，線程被自動(dòng)喚醒：

阻塞隊(duì)列種類：

ArrayBlockingQueue：基于數(shù)組實(shí)現(xiàn)的一個(gè)阻塞隊(duì)列，維護(hù)了一個(gè)定長數(shù)組仁热，以便緩存隊(duì)列中的數(shù)據(jù)對(duì)象榜揖，在創(chuàng)建ArrayBlockingQueue對(duì)象時(shí)必須制定容量大小。并且可以指定公平性與非公平性抗蠢，默認(rèn)情況下為非公平的举哟，即不保證等待時(shí)間最長的隊(duì)列最優(yōu)先能夠訪問隊(duì)列。

LinkedBlockingQueue：基于鏈表實(shí)現(xiàn)的一個(gè)阻塞隊(duì)列迅矛，其內(nèi)部也維持著一個(gè)數(shù)據(jù)緩沖隊(duì)列（該隊(duì)列由一個(gè)鏈表構(gòu)成）妨猩。當(dāng)生產(chǎn)者往隊(duì)列中放入一個(gè)數(shù)據(jù)時(shí)，隊(duì)列會(huì)從生產(chǎn)者手中獲取數(shù)據(jù)秽褒，并緩存在隊(duì)列內(nèi)部壶硅，而生產(chǎn)者立即返回；只有當(dāng)隊(duì)列緩沖區(qū)達(dá)到最大值緩存容量時(shí)（LinkedBlockingQueue可以通過構(gòu)造函數(shù)指定該值）销斟，才會(huì)阻塞生產(chǎn)者隊(duì)列庐椒，直到消費(fèi)者從隊(duì)列中消費(fèi)掉一份數(shù)據(jù)，生產(chǎn)者線程會(huì)被喚醒蚂踊，反之對(duì)于消費(fèi)者這端的處理也基于同樣的原理约谈。作為開發(fā)者，我們需要注意的是犁钟，如果構(gòu)造一個(gè)LinkedBlockingQueue對(duì)象棱诱，而沒有指定其容量大小，LinkedBlockingQueue會(huì)默認(rèn)一個(gè)類似無限大小的容量（Integer.MAX_VALUE）涝动，這樣的話军俊，如果生產(chǎn)者的速度一旦大于消費(fèi)者的速度，也許還沒有等到隊(duì)列滿阻塞產(chǎn)生捧存，系統(tǒng)內(nèi)存就有可能已被消耗殆盡了粪躬。

ArrayBlockingQueue和LinkedBlockingQueue是兩個(gè)最普通也是最常用的阻塞隊(duì)列担败，一般情況下，在處理多線程間的生產(chǎn)者消費(fèi)者問題镰官，使用這兩個(gè)類足矣提前。

PriorityBlockingQueue：以上2種隊(duì)列都是先進(jìn)先出隊(duì)列，而PriorityBlockingQueue卻不是泳唠，它會(huì)按照元素的優(yōu)先級(jí)對(duì)元素進(jìn)行排序狈网，按照優(yōu)先級(jí)順序出隊(duì)，每次出隊(duì)的元素都是優(yōu)先級(jí)最高的元素笨腥。注意拓哺，此阻塞隊(duì)列為無界阻塞隊(duì)列，即容量沒有上限脖母，前面2種都是有界隊(duì)列士鸥。

DelayQueue：基于PriorityQueue，一種延時(shí)阻塞隊(duì)列谆级，DelayQueue中的元素只有當(dāng)其指定的延遲時(shí)間到了烤礁，才能夠從隊(duì)列中獲取到該元素。DelayQueue也是一個(gè)無界隊(duì)列肥照，因此往隊(duì)列中插入數(shù)據(jù)的操作（生產(chǎn)者）永遠(yuǎn)不會(huì)被阻塞脚仔，而只有獲取數(shù)據(jù)的操作（消費(fèi)者）才會(huì)被阻塞。

SynchronousQueue：一種無緩沖的等待隊(duì)列舆绎，每個(gè)刪除操作都要等待插入操作鲤脏，反之每個(gè)插入操作也都要等待刪除操作。類似于無中介的直接交易吕朵，相對(duì)于有緩沖的BlockingQueue來說凑兰，少了一個(gè)中間經(jīng)銷商的環(huán)節(jié)（緩沖區(qū)），如果有經(jīng)銷商边锁，生產(chǎn)者直接把產(chǎn)品批發(fā)給經(jīng)銷商姑食，而無需在意經(jīng)銷商最終會(huì)將這些產(chǎn)品賣給那些消費(fèi)者，由于經(jīng)銷商可以庫存一部分商品茅坛，因此相對(duì)于直接交易模式音半，總體來說采用中間經(jīng)銷商的模式會(huì)吞吐量高一些（可以批量買賣）；但另一方面贡蓖，又因?yàn)榻?jīng)銷商的引入曹鸠，使得產(chǎn)品從生產(chǎn)者到消費(fèi)者中間增加了額外的交易環(huán)節(jié)，單個(gè)產(chǎn)品的及時(shí)響應(yīng)性能可能會(huì)降低斥铺。

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

看它的兩個(gè)關(guān)鍵方法的實(shí)現(xiàn)：put()和take()：

public void put(E e) throws InterruptedException {

??? if (e == null) throw newNullPointerException();

??? final E[] items =this.items;

??? final ReentrantLock lock= this.lock;

???lock.lockInterruptibly();

??? try {

??????? try {

??????????? while (count ==items.length)

???????????????notFull.await();

??????? } catch(InterruptedException ie) {

???????????notFull.signal(); // propagate to non-interrupted thread

??????????? throw ie;

??????? }

??????? insert(e);

??? } finally {

??????? lock.unlock();

??? }

}

private void insert(E x) {

??? items[putIndex] = x;

??? putIndex =inc(putIndex);

??? ++count;

??? notEmpty.signal();

}

從put方法的實(shí)現(xiàn)可以看出彻桃，它先獲取了鎖，并且獲取的是可中斷鎖晾蜘，然后判斷當(dāng)前元素個(gè)數(shù)是否等于數(shù)組的長度邻眷，如果相等眠屎，則調(diào)用notFull.await()進(jìn)行等待，如果捕獲到中斷異常肆饶，則喚醒線程并拋出異常改衩。當(dāng)被其他線程喚醒時(shí)，通過insert(e)方法插入元素驯镊，最后解鎖葫督。

下面是take()方法的實(shí)現(xiàn)：

public E take() throws InterruptedException {

??? final ReentrantLock lock= this.lock;

??? lock.lockInterruptibly();

??? try {

??????? try {

??????????? while (count ==0)

???????????????notEmpty.await();

??????? } catch(InterruptedException ie) {

???????????notEmpty.signal(); // propagate to non-interrupted thread

??????????? throw ie;

??????? }

?????? ?E x = extract();

??????? return x;

??? } finally {

??????? lock.unlock();

??? }

}

private?E extract() {

final?E[] items =?this.items;

E x = items[takeIndex];

items[takeIndex] =?null;

takeIndex = inc(takeIndex);

--count;

notFull.signal();

return?x;

}

跟put方法實(shí)現(xiàn)很類似，只不過put方法等待的是notFull信號(hào)板惑，而take方法等待的是notEmpty信號(hào)橄镜。在take方法中，如果可以取元素冯乘，則通過extract方法取得元素洽胶。

從這里大家應(yīng)該明白了阻塞隊(duì)列的實(shí)現(xiàn)原理，事實(shí)它和我們用Object.wait()往湿、Object.notify()和非阻塞隊(duì)列實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者的思路類似妖异，只不過它把這些工作一起集成到了阻塞隊(duì)列中實(shí)現(xiàn)惋戏。

4）EnumMap和EnumSet

?? EnumMap是專門為枚舉類型量身定做的Map實(shí)現(xiàn)领追。雖然使用其它的Map實(shí)現(xiàn)（如HashMap）也能完成枚舉類型實(shí)例到值得映射，但是使用EnumMap會(huì)更加高效：它只能接收同一枚舉類型的實(shí)例作為鍵值响逢，并且由于枚舉類型實(shí)例的數(shù)量相對(duì)固定并且有限绒窑，所以EnumMap使用數(shù)組來存放與枚舉類型對(duì)應(yīng)的值。這使得EnumMap的效率非常高舔亭。與HashMap的主要不同些膨，一是構(gòu)造方法需要傳遞類型參數(shù)，二是保證順序钦铺。

EnumMap的基本實(shí)現(xiàn)原理订雾，內(nèi)部有兩個(gè)數(shù)組，長度相同矛洞，一個(gè)表示所有可能的鍵洼哎，一個(gè)表示對(duì)應(yīng)的值，值為null表示沒有該鍵值對(duì)沼本，鍵都有一個(gè)對(duì)應(yīng)的索引噩峦，根據(jù)索引可直接訪問和操作其鍵和值，效率很高抽兆。

EnumSet是使用位向量實(shí)現(xiàn)的识补，什么是位向量呢？就是用一個(gè)位表示一個(gè)元素的狀態(tài)辫红，用一組位表示一個(gè)集合的狀態(tài)凭涂，每個(gè)位對(duì)應(yīng)一個(gè)元素祝辣，而狀態(tài)只可能有兩種。

EnumSet是一個(gè)抽象類导盅，它沒有定義使用的向量長度较幌，它有兩個(gè)子類，RegularEnumSet和JumboEnumSet白翻。RegularEnumSet使用一個(gè)long類型的變量作為位向量乍炉，long類型的位長度是64，而JumboEnumSet使用一個(gè)long類型的數(shù)組滤馍。如果枚舉值個(gè)數(shù)小于等于64岛琼，則靜態(tài)工廠方法中創(chuàng)建的就是RegularEnumSet，大于64的話就是JumboEnumSet巢株。

5）Collections.sort()和Arrays.sort()

?? 總結(jié)一下Arrays.sort()方法槐瑞，如果數(shù)組長度大于等于286且連續(xù)性好的話，就用歸并排序阁苞，如果大于等于286且連續(xù)性不好的話就用雙軸快速排序困檩。如果長度小于286且大于等于47的話就用雙軸快速排序，如果長度小于47的話就用插入排序那槽。

再來看看Collections.sort()悼沿，一路點(diǎn)進(jìn)去，發(fā)現(xiàn)會(huì)進(jìn)到Arrays里了骚灸，來看看又有什么選擇：

public static void sort(T[] a, Comparator c) {

??? if (c == null) {

??????? sort(a);

??? } else {

??????? if(LegacyMergeSort.userRequested)

???????????legacyMergeSort(a, c);

??????? else

??????????? TimSort.sort(a,0, a.length, c, null, 0, 0);

??? }

}

會(huì)發(fā)現(xiàn)如果LegacyMergeSort.userRequested為true的話就會(huì)使用歸并排序糟趾，可以通過下面代碼設(shè)置為true

System.setProperty("java.util.Arrays.useLegacyMergeSort","true");

不過方法legacyMergeSort的注釋上有這么一句話，說明以后傳統(tǒng)歸并可能會(huì)被移除了甚牲。

/** To be removed in a future release. */

如果不為true的話就會(huì)用一個(gè)叫TimSort的排序算法义郑。

參考書目：《Java編程思想》、《Java核心技術(shù)卷一》丈钙、《Effective Java》