一、同步容器
?? 在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存在的問題，清楚簡(jiǎn)單同步方式的不足。
梳理并發(fā)包內(nèi)，尤其是ConcurrentHashMap采取了哪些方法來提高并發(fā)表現(xiàn)。
最好能掌握ConcurrentHashMap自身的演進(jìn)。
?? 1）ConcurrentHashMap
????? 為什么需要ConcurrentHashMap？
????? Hashtable或者同步包裝版本，只是在方法前加synchronized，導(dǎo)致所有的并發(fā)操作都要競(jìng)爭(zhēng)同一把鎖，一個(gè)線程在進(jìn)行同步操作時(shí)，其他線程只能等待，大大降低了并發(fā)操作的效率。只是適合在非高度并發(fā)的場(chǎng)景下。
????? 早期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ì)就是采用了[鎖分段技術(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次)，才無(wú)奈轉(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，初始化操作大大簡(jiǎn)化，修改為lazy-load形式，這樣可以避免初始開銷，解決了老版本很多人抱怨的這一點(diǎn)。
* 數(shù)據(jù)存儲(chǔ)利用volatile保證可見性。
* 使用CAS等操作，在特定場(chǎng)景進(jìn)行無(wú)鎖并發(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在鏈表長(zhǎng)度超過一定閾值（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ù)組長(zhǎng)度了。然后用到了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)鍵字申請(qǐng)鎖，然后進(jìn)行操作。在同步邏輯上為什么使用的是synchronized，而不是通常建議的ReentrantLock之類？現(xiàn)在JDK中，synchronized已經(jīng)被不斷優(yōu)化，可以不再過分擔(dān)心性能差異，另外，相比ReentrantLock，它可以減少內(nèi)存消耗，這是個(gè)非常大的優(yōu)勢(shì)。如果該put操作使得當(dāng)前鏈表長(zhǎng)度超過一定閾值，則將該鏈表轉(zhuǎn)換為樹，從而提高尋址效率。
對(duì)于讀操作，由于數(shù)組被volatile關(guān)鍵字修飾，因此不用擔(dān)心數(shù)組的可見性問題。同時(shí)每個(gè)元素是一個(gè)Node實(shí)例（Java 7中每個(gè)元素是一個(gè)HashEntry），它的Key值和hash值都由final修飾，不可變更，無(wú)須關(guān)心它們被修改后的可見性問題。而其Value及對(duì)下一個(gè)元素的引用由volatile修飾，可見性也有保障。
2）CopyOnWriteArrayList和CopyOnWriteArraySet
?? CopyOnWriteArrayList是Java并發(fā)包中提供的一個(gè)并發(fā)容器，它是個(gè)線程安全且讀操作無(wú)鎖的ArrayList，寫操作則通過創(chuàng)建底層數(shù)組的新副本來實(shí)現(xiàn)，是一種讀寫分離的并發(fā)策略，我們也可以稱這種容器為"寫時(shí)復(fù)制器"，Java并發(fā)包中類似的容器還有CopyOnWriteArraySet。
實(shí)現(xiàn)原理
我們都知道，集合框架中的ArrayList是非線程安全的，Vector雖是線程安全的，但由于簡(jiǎn)單粗暴的鎖同步機(jī)制，性能較差。而CopyOnWriteArrayList則提供了另一種不同的并發(fā)處理策略（當(dāng)然是針對(duì)特定的并發(fā)場(chǎng)景）。
很多時(shí)候，我們的系統(tǒng)應(yīng)對(duì)的都是讀多寫少的并發(fā)場(chǎng)景。CopyOnWriteArrayList容器允許并發(fā)讀，讀操作是無(wú)鎖的，性能較高。至于寫操作，比如向容器中添加一個(gè)元素，則首先將當(dāng)前容器復(fù)制一份，然后在新副本上執(zhí)行寫操作，結(jié)束之后再將原容器的引用指向新容器。
優(yōu)缺點(diǎn)分析
了解了CopyOnWriteArrayList的實(shí)現(xiàn)原理，分析它的優(yōu)缺點(diǎn)及使用場(chǎng)景就很容易了。
優(yōu)點(diǎn)：
讀操作性能很高，因?yàn)闊o(wú)需任何同步措施，比較適用于讀多寫少的并發(fā)場(chǎng)景。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；二是無(wú)法保證實(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ǎng)景，生產(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è)定長(zhǎng)數(shù)組，以便緩存隊(duì)列中的數(shù)據(jù)對(duì)象，在創(chuàng)建ArrayBlockingQueue對(duì)象時(shí)必須制定容量大小。并且可以指定公平性與非公平性，默認(rèn)情況下為非公平的，即不保證等待時(shí)間最長(zhǎng)的隊(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è)類似無(wú)限大小的容量（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ì)列為無(wú)界阻塞隊(duì)列，即容量沒有上限，前面2種都是有界隊(duì)列。
DelayQueue：基于PriorityQueue，一種延時(shí)阻塞隊(duì)列，DelayQueue中的元素只有當(dāng)其指定的延遲時(shí)間到了，才能夠從隊(duì)列中獲取到該元素。DelayQueue也是一個(gè)無(wú)界隊(duì)列，因此往隊(duì)列中插入數(shù)據(jù)的操作（生產(chǎn)者）永遠(yuǎn)不會(huì)被阻塞，而只有獲取數(shù)據(jù)的操作（消費(fèi)者）才會(huì)被阻塞。
SynchronousQueue：一種無(wú)緩沖的等待隊(duì)列，每個(gè)刪除操作都要等待插入操作，反之每個(gè)插入操作也都要等待刪除操作。類似于無(wú)中介的直接交易，相對(duì)于有緩沖的BlockingQueue來說，少了一個(gè)中間經(jīng)銷商的環(huán)節(jié)（緩沖區(qū)），如果有經(jīng)銷商，生產(chǎn)者直接把產(chǎn)品批發(fā)給經(jīng)銷商，而無(wú)需在意經(jīng)銷商最終會(huì)將這些產(chǎn)品賣給那些消費(fèi)者，由于經(jīng)銷商可以庫(kù)存一部分商品，因此相對(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ù)組的長(zhǎng)度，如果相等，則調(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ù)組，長(zhǎng)度相同，一個(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è)抽象類，它沒有定義使用的向量長(zhǎng)度，它有兩個(gè)子類，RegularEnumSet和JumboEnumSet。RegularEnumSet使用一個(gè)long類型的變量作為位向量，long類型的位長(zhǎng)度是64，而JumboEnumSet使用一個(gè)long類型的數(shù)組。如果枚舉值個(gè)數(shù)小于等于64，則靜態(tài)工廠方法中創(chuàng)建的就是RegularEnumSet，大于64的話就是JumboEnumSet。
5）Collections.sort()和Arrays.sort()
?? 總結(jié)一下Arrays.sort()方法，如果數(shù)組長(zhǎng)度大于等于286且連續(xù)性好的話，就用歸并排序，如果大于等于286且連續(xù)性不好的話就用雙軸快速排序。如果長(zhǎng)度小于286且大于等于47的話就用雙軸快速排序，如果長(zhǎng)度小于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》
