01、背景介紹

在 Java 中，集合大致可以分為兩大體系，一個是 Collection，另一個是 Map，都位于java.util包下。

• Collection ：主要由 List、Set、Queue 接口組成，List 代表有序、重復(fù)的集合；其中 Set 代表無序、不可重復(fù)的集合；Java 5 又增加了 Queue 體系集合，代表隊列集合。
• Map：則代表具有映射關(guān)系的鍵值對集合。

很多書籍將 List、Set、Queue、Map 等能存放元素的接口體系，也歸納為容器，因為他們可以存放元素！

集合和容器，這兩者只是在概念上定義不同，比如ArrayList是一個存放數(shù)組的對象，真正用起來并不會去關(guān)心這個東西到底是集合還是容器，把東西用好才是關(guān)鍵！

java.util.Collection下的接口和繼承類關(guān)系簡易結(jié)構(gòu)圖：

圖片

java.util.Map下的接口和繼承類關(guān)系簡易結(jié)構(gòu)圖：

圖片

需要注意的是，網(wǎng)上有些集合架構(gòu)圖將 Map 畫成繼承自 Collection，實際上 Map 并沒有繼承 Collection，Map 是單獨的一個集合體系，這點需要糾正一下。

圖片

在 Java 集合框架中，數(shù)據(jù)結(jié)構(gòu)和算法可以說在里面體現(xiàn)的淋淋盡致，這一點可以從我們之前對各個集合類的分析就可以看的出來，如動態(tài)數(shù)組、鏈表、紅黑樹、Set、Map、隊列、棧、堆等，基本上只要出去面試，集合框架的話題一定不會少！

下面我們就一起來看看各大數(shù)據(jù)結(jié)構(gòu)的具體實現(xiàn)！

02、List

List 集合的特點：存取有序，可以存儲重復(fù)的元素，可以用下標進行元素的操作。

List 集合中，各個類繼承結(jié)構(gòu)圖：

圖片

從圖中可以看出，List 主要實現(xiàn)類有：ArrayList、LinkedList、Vector、Stack。

2.1、ArrayList

ArrayList 是一個動態(tài)數(shù)組結(jié)構(gòu)，支持隨機存取，在指定的位置插入、刪除效率低（因為要移動數(shù)組元素）；如果內(nèi)部數(shù)組容量不足則自動擴容，擴容系數(shù)為原來的1.5倍，因此當數(shù)組很大時，效率較低。

圖片

當然，插入刪除也不是效率非常低，在某些場景下，比如尾部插入、刪除，因為不需要移動數(shù)組元素，所以效率也很高哦！

ArrayList 是一個非線程安全的類，在多線程環(huán)境下使用迭代器遍歷元素時，會報錯，拋ConcurrentModificationException異常！

因此，如果想要在多線程環(huán)境下使用 ArrayList，建議直接使用并發(fā)包中的CopyOnWriteArrayList！

2.2、LinkedList

LinkedList 是一個雙向鏈表結(jié)構(gòu)，在任意位置插入、刪除都很方便，但是不支持隨機取值，每次都只能從一端開始遍歷，直到找到查詢的對象，然后返回；不過，它不像 ArrayList 那樣需要進行內(nèi)存拷貝，因此相對來說效率較高，但是因為存在額外的前驅(qū)和后繼節(jié)點指針，因此占用的內(nèi)存比 ArrayList 多一些。

圖片

LinkedList 底層通過雙向鏈表實現(xiàn)，通過first和last引用分別指向鏈表的第一個和最后一個元素，注意這里沒有所謂的啞元（某個參數(shù)如果在子程序或函數(shù)中沒有用到，那就被稱為啞元），當鏈表為空的時候first和last都指向null。

2.3、Vector

Vector 也是一個動態(tài)數(shù)組結(jié)構(gòu)，一個元老級別的類，早在 jdk1.1 就引入進來了，之后在 jdk1.2 里引進 ArrayList，ArrayList 可以說是 Vector 的一個迷你版，ArrayList 大部分的方法和 Vector 比較相似！

兩者不同的是，Vector 中的方法都加了synchronized，保證操作是線程安全的，但是效率低，而 ArrayList 所有的操作都是非線程安全的，執(zhí)行效率高，但不安全！

對于 Vector，雖然可以在多線程環(huán)境下使用，但是在迭代遍歷元素的時候依然會報錯，拋ConcurrentModificationException異常！

在 JDK 中 Vector 已經(jīng)屬于過時的類，官方不建議在程序中采用，如果想要在多線程環(huán)境下使用 Vector，建議直接使用并發(fā)包中的CopyOnWriteArrayList！

2.4、Stack

Stack 是 Vector 的一個子類，本質(zhì)也是一個動態(tài)數(shù)組結(jié)構(gòu)，不同的是，它的數(shù)據(jù)結(jié)構(gòu)是先進后出，取名叫棧！

不過，關(guān)于 Java 中 Stack 類，有很多的質(zhì)疑聲，棧更適合用隊列結(jié)構(gòu)來實現(xiàn)，這使得 Stack 在設(shè)計上不嚴謹，因此，官方推薦使用 Deque 下的類來是實現(xiàn)棧！

2.5、小結(jié)

List 接口各個實現(xiàn)類性能比較，如圖：

圖片

• ArrayList（動態(tài)數(shù)組結(jié)構(gòu)），查詢快（隨意訪問或順序訪問），增刪慢，但在末尾插入刪除，速度與LinkedList相差無幾，但是是非線程安全的！
• LinkedList（雙向鏈表結(jié)構(gòu)），查詢慢，增刪快，也是非線程安全的！
• Vector（動態(tài)數(shù)組結(jié)構(gòu)），因為方法加了同步鎖，相比 ArrayList 執(zhí)行都慢，基本不在使用，如果需要在多線程下使用，推薦使用并發(fā)容器中的CopyOnWriteArrayList來操作，效率高！
• Stack（棧結(jié)構(gòu)）繼承于Vector，數(shù)據(jù)是先進后出，基本不在使用，如果要實現(xiàn)棧，推薦使用 Deque 下的 ArrayDeque，效率比 Stack 高！

03、Map

Map是一個雙列集合，其中保存的是鍵值對，鍵要求保持唯一性，值可以重復(fù)。

從上文中，我們了解到 Map 集合結(jié)構(gòu)體系如下：

圖片

從圖中可以看出，Map 的實現(xiàn)類有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties 等等。

3.1、HashMap

關(guān)于 HashMap，相信大家都不陌生，是一個使用非常頻繁的容器類，繼承自 AbstractMap，它允許鍵值都放入 null 元素，但是 key 不可重復(fù)。

因為使用的是哈希表存儲元素，所以輸入的數(shù)據(jù)與輸出的數(shù)據(jù)，順序基本不一致，另外，HashMap 最多只允許一條記錄的 key 為 null。

在 jdk1.7中，HashMap 主要是由 數(shù)組+ 單向鏈表 組成，當發(fā)生 hash 沖突的時候，就將沖突的元素放入鏈表中。

圖片

從 jdk1.8開始，HashMap 主要是由** 數(shù)組+單向鏈表+紅黑樹** 實現(xiàn)，相比 jdk1.7 而言，多了一個紅黑樹實現(xiàn)。

當鏈表長度超過 8 的時候，就將鏈表變成紅黑樹，如圖所示。

圖片

HashMap 的實現(xiàn)原理，算是面試必問的一個話題，詳細的實現(xiàn)過程，有興趣的朋友可以閱讀小編之前寫的文章《深入分析HashMap》！

HashMap 雖然很強大，但是它是非線程安全的，也就是說，如果在多線程環(huán)境下使用，可能因為程序自動擴容操作將單向鏈表轉(zhuǎn)變成了循環(huán)鏈表，在查詢遍歷元素的時候，造成程序死循環(huán)！此時 CPU 直接會飆到 100%！

如果我們想在多線程環(huán)境下使用 HashMap，其中一個推薦的解決辦法就是使用 java 并發(fā)包下的 ConcurrentHashMap 類！

在 JDK1.7 中，ConcurrentHashMap 類采用了分段鎖的思想，將 HashMap 進行切割，把 HashMap 中的哈希數(shù)組切分成小數(shù)組（Segment），每個小數(shù)組有 n 個 HashEntry 組成，其中 Segment 繼承自ReentrantLock（可重入鎖），從而實現(xiàn)并發(fā)控制！

圖片

從 jdk1.8 開始，ConcurrentHashMap 類取消了 Segment 分段鎖，采用 CAS + synchronized來保證并發(fā)安全，數(shù)據(jù)結(jié)構(gòu)跟 jdk1.8 中 HashMap 結(jié)構(gòu)保持一致，都是數(shù)組 + 鏈表（當鏈表長度大于8時，鏈表結(jié)構(gòu)轉(zhuǎn)為紅黑樹）結(jié)構(gòu)。

圖片

jdk1.8 中的 ConcurrentHashMap 中 synchronized 只鎖定當前鏈表或紅黑樹的首節(jié)點，只要節(jié)點 hash 不沖突，就不會產(chǎn)生并發(fā)，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍！

詳細的實現(xiàn)原理，可以參閱小編之前寫的文章《深入分析ConcurrentHashMap》！

3.2、LinkedHashMap

LinkedHashMap 繼承自 HashMap，可以認為是 HashMap + LinkedList，它既使用 HashMap 操作數(shù)據(jù)結(jié)構(gòu)，又使用 LinkedList 維護插入元素的先后順序，內(nèi)部采用雙向鏈表（doubly-linked list）的形式將所有元素（ entry ）連接起來。

從名字上，就可以看出 LinkedHashMap 是一個 LinkedList 和 HashMap 的混合體，同時滿足 HashMap 和 LinkedList 的某些特性，可將 LinkedHashMap 看作采用 Linkedlist 增強的HashMap。

圖片

雙向鏈表頭部插入的數(shù)據(jù)為鏈表的入口，迭代器遍歷方向是從鏈表的頭部開始到鏈表尾部結(jié)束，結(jié)構(gòu)圖如下：

圖片

這種結(jié)構(gòu)除了可以保持迭代的順序，還有一個好處：迭代 LinkedHashMap 時不需要像 HashMap 那樣遍歷整個 table，而只需要直接遍歷 header 指向的雙向鏈表即可，也就是說 LinkedHashMap 的迭代時間就只跟 entry 的個數(shù)相關(guān)，而跟 table 的大小無關(guān)。

LinkedHashMap 繼承了 HashMap，所有大部分功能特性與 HashMap 基本相同，允許放入 key 為null的元素，也允許插入 value 為null的元素。

二者唯一的區(qū)別是 LinkedHashMap 在 HashMap 的基礎(chǔ)上，采用雙向鏈表（doubly-linked list）的形式將所有 entry 連接起來，這樣是為保證元素的迭代順序跟插入順序相同。

3.3、TreeMap

TreeMap實現(xiàn)了 SortedMap 接口，也就是說會按照 key 的大小順序?qū)?Map 中的元素進行排序，key 大小的評判可以通過其本身的自然順序（natural ordering），也可以通過構(gòu)造時傳入的比較器（Comparator）。

TreeMap 底層通過紅黑樹（Red-Black tree）實現(xiàn)，所以要了解 TreeMap 就必須對紅黑樹有一定的了解。

如下為紅黑樹圖：

圖片

紅黑樹是基于平衡二叉樹實現(xiàn)的，基于平衡二叉樹的實現(xiàn)還有 AVL 算法，也被稱為 AVL 樹，AVL 算法要求任何節(jié)點的兩棵子樹的高度差不大于1，為了保持樹的高度差不大于1，主要有2中調(diào)整方式：左旋轉(zhuǎn)、右旋轉(zhuǎn)。

繞某元素右旋轉(zhuǎn)，圖解如下：

圖片

繞某元素右旋轉(zhuǎn)，圖解如下：

圖片

雖然 AVL 算法保證了樹高度平衡，查詢效率極高，但是也有缺陷，在刪除某個節(jié)點時，需要多次左旋轉(zhuǎn)或右旋轉(zhuǎn)調(diào)整，紅黑樹的出現(xiàn)就是為了解決盡可能少的調(diào)整，提高平衡二叉樹的整體性能！

那么對于一棵有效的紅黑樹，主要有以下規(guī)則：

• 1、每個節(jié)點要么是紅色，要么是黑色，但根節(jié)點永遠是黑色的；
• 2、每個紅色節(jié)點的兩個子節(jié)點一定都是黑色；
• 3、紅色節(jié)點不能連續(xù)（也即是，紅色節(jié)點的孩子和父親都不能是紅色）；
• 4、從任一節(jié)點到其子樹中每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點；
• 5、所有的葉節(jié)點都是是黑色的（注意這里說葉子節(jié)點其實是上圖中的 NIL 節(jié)點）；

紅黑樹為了保證樹的基本平衡，調(diào)整也有類似 AVL 算法那樣的左旋轉(zhuǎn)、右旋轉(zhuǎn)操作；同時，紅黑樹因為紅色節(jié)點不能連續(xù)，因此還增加一個顏色調(diào)整操作：節(jié)點顏色轉(zhuǎn)換。

圖片

AVL雖然可以保證平衡二叉樹高度平衡，但是在刪除某個節(jié)點的時候，最多需要 n 次調(diào)整，也就是左旋轉(zhuǎn)、右旋轉(zhuǎn)；而紅黑樹，雖然也是基于平衡二叉樹實現(xiàn)，但是并不像 AVL 那樣高度平衡，而是基本平衡，在刪除某個節(jié)點的時候，至多 3 次調(diào)整，效率比 AVL 高！

紅黑樹，在插入的時候，與 AVL 一樣，結(jié)點最多只需要2次旋轉(zhuǎn)；在查詢方面，因為不是高度平衡，紅黑樹在查詢效率方面稍遜于 AVL，但是比二叉查找樹強很多！

就整體來看，紅黑樹的性能要好于 AVL，只是實現(xiàn)稍微復(fù)雜了一些，有興趣的朋友可以參閱小編之前寫的文章《3分鐘看完關(guān)于樹的故事》！

3.4、IdentityHashMap

IdentityHashMap 從名字上看，感覺表示唯一的 HashMap，然后并不是，別被它的名稱所欺騙哦。

IdentityHashMap 的數(shù)據(jù)結(jié)構(gòu)很簡單，底層實際就是一個 Object 數(shù)組，在存儲上并沒有使用鏈表來存儲，而是將 K 和 V 都存放在 Object 數(shù)組上。

圖片

當添加元素的時候，會根據(jù) Key 計算得到散列位置，如果發(fā)現(xiàn)該位置上已經(jīng)有改元素，直接進行新值替換；如果沒有，直接進行存放。當元素個數(shù)達到一定閾值時，Object 數(shù)組會自動進行擴容處理。

IdentityHashMap 的實現(xiàn)也不同于 HashMap，雖然也是數(shù)組，不過 IdentityHashMap 中沒有用到鏈表，解決沖突的方式是計算下一個有效索引，并且將數(shù)據(jù) key 和 value 緊挨著存入 map 中，即table[i]=key、table[i+1]=value；

IdentityHashMap 允許key、value都為null，當key為null的時候，默認會初始化一個Object對象作為key；

3.5、WeakHashMap

WeakHashMap 是 Map 體系中一個很特殊的成員，它的特殊之處在于  WeakHashMap 里的元素可能會被 GC 自動刪除，即使程序員沒有顯示調(diào)用 remove() 或者 clear() 方法。

換言之，當向 WeakHashMap 中添加元素的時候，再次遍歷獲取元素，可能發(fā)現(xiàn)它已經(jīng)不見了，我們來看看下面這個例子。

public static void main(String[] args) {
    Map weakHashMap = new WeakHashMap();
    //向weakHashMap中添加3個元素
    weakHashMap.put("key-1", "value-1");
    weakHashMap.put("key-2", "value-2");
    weakHashMap.put("key-3", "value-3");
    //輸出添加的元素
    System.out.println("數(shù)組長度："+weakHashMap.size() + "，輸出結(jié)果：" + weakHashMap);
    //主動觸發(fā)一次GC
    System.gc();
    //再輸出添加的元素
    System.out.println("數(shù)組長度："+weakHashMap.size() + "，輸出結(jié)果：" + weakHashMap);
}

輸出結(jié)果：

數(shù)組長度：3，輸出結(jié)果：{key-2=value-2, key-1=value-1, key-0=value-0}
數(shù)組長度：3，輸出結(jié)果：{}

當主動調(diào)用 GC 回收器的時候，再次查詢 WeakHashMap 里面的數(shù)據(jù)的時候，數(shù)據(jù)已經(jīng)被 GC 收集了，內(nèi)容為空。

這是因為 WeakHashMap 的 key 使用了弱引用類型，在垃圾回收器線程掃描它所管轄的內(nèi)存區(qū)域的過程中，一旦發(fā)現(xiàn)了只具有弱引用的對象，不管當前內(nèi)存空間足夠與否，都會回收它的內(nèi)存。

不過，由于垃圾回收器是一個優(yōu)先級很低的線程，因此不一定會很快發(fā)現(xiàn)那些只具有弱引用的對象。

WeakHashMap 跟普通的 HashMap 不同，在存儲數(shù)據(jù)時，key 被設(shè)置為弱引用類型，而弱引用類型在 java 中，可能隨時被 jvm 的 gc 回收，所以再次通過獲取對象時，可能得到空值，而 value 是在訪問數(shù)組內(nèi)容的時候，進行清除。

可能很多人覺得這樣做很奇葩，其實不然，WeekHashMap 的這個特點特別適用于需要緩存的場景。

在緩存場景下，由于系統(tǒng)內(nèi)存是有限的，不能緩存所有對象，可以使用 WeekHashMap 進行緩存對象，即使緩存丟失，也可以通過重新計算得到，不會造成系統(tǒng)錯誤。

比較典型的例子，Tomcat 中的 ConcurrentCache 類就使用了 WeekHashMap 來實現(xiàn)數(shù)據(jù)緩存。

3.6、Hashtable

Hashtable 一個元老級的集合類，早在 JDK 1.0 就誕生了，而 HashMap 誕生于 JDK 1.2。

在實現(xiàn)上，HashMap 可以看作是 Hashtable 的一個迷你版，雖然二者的底層數(shù)據(jù)結(jié)構(gòu)都是 數(shù)組 + 鏈表 結(jié)構(gòu)，具有查詢、插入、刪除快的特點，但是二者又有很多的不同。

• 雖然 HashMap 和 Hashtable 都實現(xiàn)了 Map 接口，但 Hashtable 繼承于 Dictionary 類，而 HashMap 是繼承于 AbstractMap；
• HashMap 可以允許存在一個為 null 的 key 和任意個為 null 的 value，但是 HashTable 中的 key 和 value 都不允許為 null；
• Hashtable 的方法是同步的，因為在方法上加了 synchronized 同步鎖，而 HashMap 是非線程安全的；

雖然 Hashtable 是 HashMap 線程安全的一個版本，但是官方已經(jīng)不推薦使用 HashTable了，因為歷史遺留原因，并沒有移除此類，如果需要在線程安全的環(huán)境下使用 HashMap，那么推薦使用 ConcurrentHashMap。在上文中已經(jīng)有所提到！

3.7、Properties

在 Java 中，其實還有一個非常重要的類 Properties，它繼承自 Hashtable，主要用于讀取配置文件。

Properties 類是 java 工具包中非常重要的一個類，比如在實際開發(fā)中，有些變量，我們可以直接硬寫入到自定義的 java 枚舉類中。

但是有些變量，在測試環(huán)境、預(yù)生產(chǎn)環(huán)境、生產(chǎn)環(huán)境，變量所需要取的值都不一樣，這個時候，我們可以通過使用 properties 文件來加載程序需要的配置信息，以達到一行代碼，多處環(huán)境都可以運行的效果！

比如，最常見的 JDBC 數(shù)據(jù)源配置文件，properties文件以.properties作為后綴，文件內(nèi)容以鍵=值格式書寫，左邊是變量名稱，右邊是變量值，用#做注釋，新建一個jdbc.properties文件，內(nèi)容如下：

圖片

Properties 繼承自 Hashtable，大部分方法都復(fù)用于 Hashtable，與 Hashtable 不同的是， Properties 中的 key 和 value 都是字符串。

實際開發(fā)中，Properties 主要用于讀取配置文件，尤其是在不同的環(huán)境下，變量值需要不一樣的情況，可以通過讀取配置文件來避免將變量值寫死在 java 的枚舉類中，以達到一行代碼，多處運行的目的！

04、Set

Set集合的特點：元素不重復(fù)，存取無序，無下標。

Set 集合，在元素存儲方面，注重獨立無二的特性，如果某個元素在集合中已經(jīng)存在，不會存儲重復(fù)的元素，同時，集合存儲的是元素，不像 Map 集合那樣存儲的是鍵值對。

Set 集合中，各個類繼承結(jié)構(gòu)圖：

圖片

從圖中可以看出，Set 集合主要實現(xiàn)類有：HashSet、LinkedHashSet 、TreeSet 、EnumSet（ RegularEnumSet、JumboEnumSet ）等等

4.1、HashSet

HashSet 是一個輸入輸出無序的集合，底層基于 HashMap 來實現(xiàn)，HashSet 利用 HashMap 中的 key 元素來存放元素，這一點我們可以從源碼上看出來，源碼定義如下：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable{
    // HashMap 變量
    private transient HashMap<E,Object> map;
    /**HashSet 初始化*/
    public HashSet() {
        //默認實例化一個 HashMap
        map = new HashMap<>();
    }
}

因為 HashMap 允許 key 為空為null，所以 HashSet 也允許添加為null的元素。

4.2、LinkedHashSet

LinkedHashSet 是一個輸入輸出有序的集合，繼承自 HashSet，但是底層基于 LinkedHashMap 來實現(xiàn)。

LinkedHashSet 的源碼，類定義如下：

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    public LinkedHashSet() {
        //調(diào)用 HashSet 的方法
        super(16, .75f, true);
    }
}

查詢源碼，super調(diào)用的方法，源碼如下：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    //初始化一個 LinkedHashMap
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

LinkedHashSet 與 HashSet 相比，LinkedHashSet 保證了元素輸入輸出有序！

4.3、TreeSet

TreeSet 是一個排序的集合，實現(xiàn)了NavigableSet、SortedSet、Set接口，底層基于 TreeMap 來實現(xiàn)。

TreeSet 利用 TreeMap 中的 key 元素來存放元素，這一點我們也可以從源碼上看出來，閱讀源碼，類定義如下：

public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
    //TreeSet 使用NavigableMap接口作為變量
    private transient NavigableMap<E,Object> m;
    /**對象初始化*/
    public TreeSet() {
        //默認實例化一個 TreeMap 對象
        this(new TreeMap<E,Object>());
    }
    //對象初始化調(diào)用的方法
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
}

new TreeSet<>()對象實例化的時候，表達的意思，可以簡化為如下：

NavigableMap<E,Object> m = new TreeMap<E,Object>();

因為TreeMap實現(xiàn)了NavigableMap接口，所以沒啥問題。

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
    ......
}

TreeSet 是一個排序的 Set 集合，元素不可重復(fù)，底層基于 TreeMap 的 key 來實現(xiàn)，元素不可以為空，默認按照自然排序來存放元素，也可以使用 Comparable和 Comparator 接口來比較大小，實現(xiàn)自定義排序。

4.4、EnumSet

EnumSet 是一個與枚舉類型搭配使用的專用 Set 集合，在 jdk1.5 中加入。

與 HashSet、LinkedHashSet 、TreeSet 不同的是，EnumSet 元素必須是Enum的類型，并且所有元素都必須來自同一個枚舉類型。

新建一個EnumEntity的枚舉類型，定義2個參數(shù)。

public enum EnumEntity {
    WOMAN,MAN;
}

創(chuàng)建一個 EnumSet，并將枚舉類型的元素全部添加進去！

//創(chuàng)建一個 EnumSet，將EnumEntity 元素內(nèi)容添加到EnumSet中
EnumSet<EnumEntity> allSet = EnumSet.allOf(EnumEntity.class);
System.out.println(allSet);

輸出結(jié)果：

[WOMAN, MAN]

在 Java 中，EnumSet 是一個虛類，有2個實現(xiàn)類 RegularEnumSet、JumboEnumSet，不能顯式的實例化改類，EnumSet 會動態(tài)決定使用哪一個實現(xiàn)類，當元素個數(shù)小于等于64的時候，使用 RegularEnumSet；大于 64的時候，使用JumboEnumSet類。

EnumSet 其內(nèi)部使用位向量實現(xiàn)，擁有極高的時間和空間性能，如果元素是枚舉類型，推薦使用 EnumSet。

4.5、小結(jié)

圖片

05、Queue

在 jdk1.5 中，新增了 Queue 接口，代表一種隊列集合的實現(xiàn)。

Queue 接口是由大名鼎鼎的 Doug Lea 創(chuàng)建，中文名為道格·利，翻開 JDK1.8 源代碼，可以將 Queue 接口旗下的實現(xiàn)類抽象成如下結(jié)構(gòu)圖：

圖片

從上圖可以看出，Queue 接口主要實現(xiàn)類有：ArrayDeque、LinkedList、PriorityQueue。

5.1、ArrayDeque

ArrayQueue 是一個基于數(shù)組實現(xiàn)的雙端隊列，可以想象，在隊列中存在兩個指針，一個指向頭部，一個指向尾部，因此它具有FIFO隊列及LIFO棧的方法特性。

其中隊列（FIFO）表示先進先出，比如水管，先進去的水先出來；棧（LIFO）表示先進后出，比如，手槍彈夾，最后進去的子彈，最先出來。

如下為 ArrayDeque 數(shù)據(jù)結(jié)構(gòu)圖，head 表示頭部指針，tail表示尾部指針：

圖片

在上文中，我們也說到 Stack 也可以作為棧使用，但是 ArrayDeque 的效率要高于 Stack 類，并且功能也比 Stack 類豐富的多，當需要使用棧時，Java 已不推薦使用 Stack，而是推薦使用更高效的 ArrayDeque。

5.2、LinkedList

LinkedList 是一個基于鏈表實現(xiàn)的雙端隊列，在上文中我們也說到 LinkedList 實現(xiàn)自 List，作為一個雙向鏈表時，增加或刪除元素的效率較高，如果查找的話需要遍歷整個鏈表，效率較低！

圖片

于此同時，LinkedList 也實現(xiàn)了 Deque 接口，既可以作隊列使用也可以作為棧使用。

從上圖中可以得出，ArrayDeque 和 LinkedList 都是 Deque 接口的實現(xiàn)類，都具備既可以作為隊列，又可以作為棧來使用的特性，兩者主要區(qū)別在于底層數(shù)據(jù)結(jié)構(gòu)的不同。

ArrayDeque 底層數(shù)據(jù)結(jié)構(gòu)是以循環(huán)數(shù)組為基礎(chǔ)，而 LinkedList 底層數(shù)據(jù)結(jié)構(gòu)是以循環(huán)鏈表為基礎(chǔ)。

理論上，鏈表在添加、刪除方面性能高于數(shù)組結(jié)構(gòu)，在查詢方面數(shù)組結(jié)構(gòu)性能高于鏈表結(jié)構(gòu)，但是對于數(shù)組結(jié)構(gòu)，如果不進行數(shù)組移動，在添加方面效率也很高。

下面，分別以10萬條數(shù)據(jù)為基礎(chǔ)，通過添加、刪除，來測試兩者作為隊列、棧使用時所消耗的時間，測試結(jié)果如下圖：

從數(shù)據(jù)上可以看出，在 10 萬條數(shù)據(jù)下，兩者性能都差不多，當達到 100 萬條、1000 萬條數(shù)據(jù)的時候，兩者的差別就比較明顯了，ArrayDeque 無論是作為隊列還是作為棧使用，性能均高于 LinkedList 。

為什么 ArrayDeque 性能，在大數(shù)據(jù)量的時候，明顯高于 LinkedList？

個人分析，LinkedList 底層是以循環(huán)鏈表來實現(xiàn)的，每一個節(jié)點都有一個前驅(qū)、后繼的變量，也就是說，每個節(jié)點上都存放有它上一個節(jié)點的指針和它下一個節(jié)點的指針，同時還包括它自己的元素，每次插入或刪除節(jié)點時需要修改前驅(qū)、后繼節(jié)點變量，在同等的數(shù)據(jù)量情況下，鏈表的內(nèi)存開銷要明顯大于數(shù)組，同時因為 ArrayDeque 底層是數(shù)組結(jié)構(gòu)，天然在查詢方面占優(yōu)勢，在插入、刪除方面，只需要移動一下頭部或者尾部變量，時間復(fù)雜度是 O（1）。

所以，在大數(shù)據(jù)量的時候，LinkedList 的內(nèi)存開銷明顯大于 ArrayDeque，在插入、刪除方面，都要頻發(fā)修改節(jié)點的前驅(qū)、后繼變量；而 ArrayDeque 在插入、刪除方面依然保存高性能。

如果對于小數(shù)據(jù)量，ArrayDeque 和 LinkedList 在效率方面相差不大，但是對于大數(shù)據(jù)量，推薦使用 ArrayDeque。

5.3、PriorityQueue

PriorityQueue 并沒有直接實現(xiàn) Queue接口，而是通過繼承 AbstractQueue 類來實現(xiàn) Queue 接口一些方法，在 Java 定義中，PriorityQueue 是一個基于優(yōu)先級的無界優(yōu)先隊列。

通俗的說，添加到 PriorityQueue 隊列里面的元素都經(jīng)過了排序處理，默認按照自然順序，也可以通過 Comparator 接口進行自定義排序。

優(yōu)先隊列的作用是保證每次取出的元素都是隊列中權(quán)值最小的。

PriorityQueue 排序?qū)崿F(xiàn)與上文中說到的 TreeMap 類似。

圖片

在 Java 中 PriorityQueue 是一個使用數(shù)組結(jié)構(gòu)來存儲元素的優(yōu)先隊列，雖然它也實現(xiàn)了Queue接口，但是元素存取并不是先進先出，而是通過一個二叉小頂堆實現(xiàn)的，默認底層使用自然排序規(guī)則給插入的元素進行排序，也可以使用自定義比較器來實現(xiàn)排序，每次取出的元素都是隊列中權(quán)值最小的。

同時需要注意的是，PriorityQueue 不能插入null，否則報空指針異常！