01、背景介紹

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

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

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

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

java.util.Collection下的接口和繼承類關系簡易結構圖：

圖片

java.util.Map下的接口和繼承類關系簡易結構圖：

圖片

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

圖片

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

下面我們就一起來看看各大數據結構的具體實現！

02、List

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

List 集合中，各個類繼承結構圖：

圖片

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

2.1、ArrayList

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

圖片

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

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

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

2.2、LinkedList

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

圖片

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

2.3、Vector

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

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

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

在 JDK 中 Vector 已經屬于過時的類，官方不建議在程序中采用，如果想要在多線程環境下使用 Vector，建議直接使用并發包中的CopyOnWriteArrayList！

2.4、Stack

Stack 是 Vector 的一個子類，本質也是一個動態數組結構，不同的是，它的數據結構是先進后出，取名叫棧！

不過，關于 Java 中 Stack 類，有很多的質疑聲，棧更適合用隊列結構來實現，這使得 Stack 在設計上不嚴謹，因此，官方推薦使用 Deque 下的類來是實現棧！

2.5、小結

List 接口各個實現類性能比較，如圖：

圖片

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

03、Map

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

從上文中，我們了解到 Map 集合結構體系如下：

圖片

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

3.1、HashMap

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

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

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

圖片

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

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

圖片

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

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

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

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

圖片

從 jdk1.8 開始，ConcurrentHashMap 類取消了 Segment 分段鎖，采用 CAS + synchronized來保證并發安全，數據結構跟 jdk1.8 中 HashMap 結構保持一致，都是數組 + 鏈表（當鏈表長度大于8時，鏈表結構轉為紅黑樹）結構。

圖片

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

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

3.2、LinkedHashMap

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

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

圖片

雙向鏈表頭部插入的數據為鏈表的入口，迭代器遍歷方向是從鏈表的頭部開始到鏈表尾部結束，結構圖如下：

圖片

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

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

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

3.3、TreeMap

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

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

如下為紅黑樹圖：

圖片

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

繞某元素右旋轉，圖解如下：

圖片

繞某元素右旋轉，圖解如下：

圖片

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

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

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

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

圖片

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

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

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

3.4、IdentityHashMap

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

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

圖片

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

IdentityHashMap 的實現也不同于 HashMap，雖然也是數組，不過 IdentityHashMap 中沒有用到鏈表，解決沖突的方式是計算下一個有效索引，并且將數據 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 自動刪除，即使程序員沒有顯示調用 remove() 或者 clear() 方法。

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

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("數組長度："+weakHashMap.size() + "，輸出結果：" + weakHashMap);
    //主動觸發一次GC
    System.gc();
    //再輸出添加的元素
    System.out.println("數組長度："+weakHashMap.size() + "，輸出結果：" + weakHashMap);
}

輸出結果：

數組長度：3，輸出結果：{key-2=value-2, key-1=value-1, key-0=value-0}
數組長度：3，輸出結果：{}

當主動調用 GC 回收器的時候，再次查詢 WeakHashMap 里面的數據的時候，數據已經被 GC 收集了，內容為空。

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

不過，由于垃圾回收器是一個優先級很低的線程，因此不一定會很快發現那些只具有弱引用的對象。

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

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

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

比較典型的例子，Tomcat 中的 ConcurrentCache 類就使用了 WeekHashMap 來實現數據緩存。

3.6、Hashtable

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

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

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

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

3.7、Properties

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

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

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

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

圖片

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

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

04、Set

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

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

Set 集合中，各個類繼承結構圖：

圖片

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

4.1、HashSet

HashSet 是一個輸入輸出無序的集合，底層基于 HashMap 來實現，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 來實現。

LinkedHashSet 的源碼，類定義如下：

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

查詢源碼，super調用的方法，源碼如下：

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

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

4.3、TreeSet

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

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>());
    }
    //對象初始化調用的方法
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
}

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

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

因為TreeMap實現了NavigableMap接口，所以沒啥問題。

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

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

4.4、EnumSet

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

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

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

public enum EnumEntity {
    WOMAN,MAN;
}

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

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

輸出結果：

[WOMAN, MAN]

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

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

4.5、小結

圖片

05、Queue

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

Queue 接口是由大名鼎鼎的 Doug Lea 創建，中文名為道格·利，翻開 JDK1.8 源代碼，可以將 Queue 接口旗下的實現類抽象成如下結構圖：

圖片

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

5.1、ArrayDeque

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

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

如下為 ArrayDeque 數據結構圖，head 表示頭部指針，tail表示尾部指針：

圖片

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

5.2、LinkedList

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

圖片

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

從上圖中可以得出，ArrayDeque 和 LinkedList 都是 Deque 接口的實現類，都具備既可以作為隊列，又可以作為棧來使用的特性，兩者主要區別在于底層數據結構的不同。

ArrayDeque 底層數據結構是以循環數組為基礎，而 LinkedList 底層數據結構是以循環鏈表為基礎。

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

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

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

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

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

所以，在大數據量的時候，LinkedList 的內存開銷明顯大于 ArrayDeque，在插入、刪除方面，都要頻發修改節點的前驅、后繼變量；而 ArrayDeque 在插入、刪除方面依然保存高性能。

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

5.3、PriorityQueue

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

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

優先隊列的作用是保證每次取出的元素都是隊列中權值最小的。

PriorityQueue 排序實現與上文中說到的 TreeMap 類似。

圖片

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

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