Java集合大全

2020 年 9 月 13 日
筆記
Java基礎, 學習之路

集合也是一種容器，在開發過程中的應用數不勝數，除了常見的HashMap、ArrayList、LinkedList和HashSet等等，了解這些集合API的同時，也應該了解這些集合內部發生了什麼事情，這樣就不再是集合提供了什麼功能給我們用，而是我們選擇了它的什麼功能。

一、Java集合架構圖

1.集合框架提供兩個遍歷接口：Iterator和ListIterator，後者是前者的優化版，支持在集合任意一個位置進行前後雙向遍歷;
2.整個集合框架分為兩個類型：Collection和Map，前者是一個容器，存儲一系列的對象；後者是鍵值對<key, value>，存儲一系列的鍵值對;
3.在現有的集合框架體系下，衍生出四種具體集合類型：Map、Set、List、Queue;
4.Map存儲<key,value>鍵值對，查找元素時通過key查找value;
5.Set內部存儲一系列不可重複的對象，且是一個無序集合，對象排列順序不一;
6.List內部存儲一系列可重複的對象，是一個有序集合，對象按插入順序排列;
7.Queue是一個隊列容器，其特性與List相同，但只能從隊頭和隊尾操作元素;
8.JDK 為集合的各種操作提供了兩個工具類Collections和Arrays;

9.四種具體類型的集合，內部會再衍生許多不同特性的集合子類，根據不通的應用場景選擇使用的集合;

二、集合的迭代器

目前Java里有三個迭代器：Iterator Iterable ListIterator。

1. 首先看Iterator接口：

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

提供的API接口含義如下：
hasNext()：判斷集合中是否還有下一個對象。
next()：返回集合中的下一個對象，並將訪問指針移動一位。
remove()：刪除集合中調用next()方法返回的對象。
在JDK早期版本里，遍歷集合的方式只有一種，那就是通過Iterator迭代器操作，具體實例如下：

List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
Iterator iter = list.iterator();
while (iter.hasNext()) {
    Integer next = iter.next();
    System.out.println(next);
    if (next == 20) {
      iter.remove(); 
    }
}

2. Iterable接口

public interface Iterable<T> {
    Iterator<T> iterator();
    // since JDK 1.8
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    // since JDK 1.8
    default Spliterator<T> spliterator() {
       return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

　Iterable接口裏面提供了一個Iterator()方法返回迭代器，因此實現了Iterable接口的集合依舊可以使用迭代器遍歷和操作集合中的對象。在 JDK 1.8中，Iterable接口新增了一個方法forEach()，它允許使用增強 for 循環遍歷對象。

為什麼要設計兩個接口Iterable和Iterator？Iterator接口的保留可以讓子類去實現自己的迭代器，而Iterable接口更加關注於for-each的增強語法。

3. ListIterator

　　ListIterator繼承 Iterator 接口，僅存在於 List 集合之中，通過調用方法可以返回起始下標為 index的迭代器。ListIterator 中有幾個重要方法，大多數方法與 Iterator 中定義的含義相同，此外根據返回的迭代器，且可以實現雙向遍歷。

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    // 替換當前下標的元素,即訪問過的最後一個元素
    void set(E e);
    void add(E e);
}

三、Map和Collection接口

　　Map接口和Collection接口是Java的集合框架中的兩個重要門派，Collection存儲的是集合元素本身，Map存儲的是<key,value>鍵值對，但是部分Collection子類使用了Map來實現的。例如：HashSet底層使用了HashMap，TreeSet底層使用了TreeMap，LinkedHashSet底層使用了LinkedHashMap

Map接口的數據結構是<key, value>形式，key 映射value，一個key對應一個value，key不可重複，value可重複。Map接口細分為不同的種類：

SortedMap接口：該類映射可以對<key, value>按照自己的規則進行排序，具體實現有 TreeMap
AbsractMap抽象類：它為子類提供好一些通用的API實現，所有的具體Map如HashMap都會繼承它

Collection接口提供了所有集合的通用方法（注意這裡不包括Map）：
    添加方法：add(E e) / addAll(Collection<? extends E> var1)/ addAll(int index, Collection<? extends E> var1)
查找方法：contains(Object var1) / containsAll(Collection<?> var1)/
    查詢集合自身信息：size() / isEmpty()
  刪除方法：remove(O o)/removeAll(Collection<?> var1)/求交集：retainAll(Collection c)

… …

Collection接口將集合細分為不同的種類：

    Set接口：一個不允許存儲重複元素的無序集合，具體實現有HashSet / TreeSet···
    List接口：一個可存儲重複元素的有序集合，具體實現有ArrayList / LinkedList···
    Queue接口：一個可存儲重複元素的隊列，具體實現有PriorityQueue / ArrayDeque···

1. Map接口詳解

Map 體系下主要分為 AbstractMap 和 SortedMap兩類集合
AbstractMap是對Map接口的擴展，定義了普通Map集合具有的通用方法，可避免子類重複編寫大量相同代碼，子類繼承 AbstractMap 後可重寫它的方法，並實現額外邏輯，對外可提供更多的功能。
SortedMap接口定義了Map具有排序行為，當子類實現它時，必須重寫所有方法，對外提供排序功能。

1.1 HashMap

HashMap 是一個最通用的利用哈希表存儲元素的集合，有元素加入HashMap時，會將key的哈希值轉換為數組的索引下標確定存放位置，在查找元素時，根據key的哈希地址轉換成數組的索引下標確定查找位置。
HashMap 底層是用數組 + 鏈表 + 紅黑樹這三種數據結構實現，是非線程安全的集合。

加入元素髮生哈希衝突時，HashMap會將相同地址的元素連成一條鏈表，若鏈表長度大於8，且數組長度大於64會轉換成紅黑樹數據結構。

關於 HashMap 的簡要總結：
1. 它是集合中最常用的Map集合類型，底層由數組 + 鏈表 + 紅黑樹組成；
2. HashMap不是線程安全的；
3. 插入元素時，通過計算元素哈希值，通過哈希映射函數轉換為數組下標；查找元素時，通過哈希映射函數得到數組下標定位元素的位置。

1.2 LinkedHashMap

LinkedHashMap可以看作是 HashMap 和 LinkedList 的結合：它是在 HashMap 的基礎上添加了一條雙向鏈表，默認存儲各個元素的插入順序，但由於這條雙向鏈表，使得 LinkedHashMap 可以實現 LRU緩存淘汰策略，因為我們可以設置這條雙向鏈表按照元素的訪問次序進行排序

// 頭節點
transient LinkedHashMap.Entry<K, V> head;
// 尾結點
transient LinkedHashMap.Entry<K, V> tail;

利用 LinkedHashMap 可以實現 LRU 緩存淘汰策略，因為它提供了一個方法：

protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
    return false;
}

該方法可以移除最靠近鏈表頭部的一個節點，而在get(key)方法源代碼如下，其作用是挪動結點的位置：

public V get(Object key) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
      return null;
   if (accessOrder)
      afterNodeAccess(e);
   return e.value;
}

只要調用了get(key)且accessOrder = true，則會將該節點更新到鏈表尾部，具體的邏輯在afterNodeAccess()中，源碼如下：

void afterNodeAccess(Node<K,V> e) { // move node to last
　　LinkedHashMap.Entry<K,V> last;
　　if (accessOrder && (last = tail) != e) {
　　　　LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
　　　　p.after = null;
　　　　if (b == null) head = a;
　　　　  else b.after = a;
　　　　if (a != null) a.before = b;
　　　　else last = b;
　　　　if (last == null) head = p;
　　　　else {
　　　　　　p.before = last;
　　　　　　last.after = p;
　　　  }
　　　　tail = p;
　　　　++modCount;
　　}
}

指定accessOrder = true，可以設定鏈表按照訪問順序排列，通過提供的構造器可以設定accessOrder。

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

重寫removeEldestEntry()方法，內部定義邏輯，通常是判斷容量是否達到上限，若是則執行淘汰。

關於 LinkedHashMap 總結兩點：
1. 底層維護了一條雙向鏈表，繼承了 HashMap，所以不是線程安全的
2. LinkedHashMap 可實現LRU緩存淘汰策略，其原理是通過設置accessOrder為true並重寫removeEldestEntry方法定義淘汰元素時需滿足的條件。

1.3 TreeMap

TreeMap 是 SortedMap 的子類，所以它具有排序功能，是基於紅黑樹數據實現的，每個鍵值對<key, value>都是一個結點，默認情況下按照key自然排序，另一種是可以通過傳入定製的Comparator進行自定義規則排序。

// 按照 key 自然排序，Integer 的自然排序是升序
TreeMap<Integer, Object> naturalSort = new TreeMap<>();
// 定製排序，按照 key 降序排序
TreeMap<Integer, Object> customSort = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1));

圖中紅黑樹的每一個節點都是一個Entry，在這裡不標明 key 和 value 了，這些元素都是已按照key排好序了，整個數據結構都是保持着有序狀態！
關於自然排序與定製排序：
自然排序：要求key必須實現Comparable接口。
由於Integer類實現了Comparable 接口，按照自然排序規則是按照key從小到大排序。

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(2, "貳");
treeMap.put(1, "壹");
System.out.print(treeMap);
// {1=壹, 2=貳}

定製排序：在初始化 TreeMap 時傳入新的Comparator，不要求key實現 Comparable 接口

TreeMap<Integer, String> treeMap = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1));
treeMap.put(1, "壹");
treeMap.put(2, "貳");
treeMap.put(4, "肆");
treeMap.put(3, "叄");
System.out.println(treeMap);
// {4=肆, 3=叄, 2=貳, 1=壹}

關於 TreeMap 主要介紹了三點：
1. 它底層是由紅黑樹實現的，操作的時間複雜度為O(logN)；
2. TreeMap 可以對key進行自然排序或者自定義排序，自定義排序時需要傳入Comparator，而自然排序要求key實現了Comparable接口；
3. TreeMap 不是線程安全的。

1.4 WeakHashMap

WeakHashMap底層存儲的元素的數據結構是數組 + 鏈表，沒有紅黑樹。日常開發中用的很少，是基於Map實現，Entry中鍵在每一次垃圾回收都會被清除，適合用於短暫訪問或訪問一次的元素，緩存在WeakHashMap中，並儘早地把它回收掉。

public class WeakHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {
}

　　當Entry被GC時，WeakHashMap 是如何感知到某個元素被回收的呢？

在 WeakHashMap 內部維護了一個引用隊列queue：

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

queue里包含了所有被GC掉的key，當JVM開啟GC後，如果回收掉WeakHashMap中的key，會將key放入queue 中，在expungeStaleEntries()中遍歷 queue，把queue中的所有key拿出來，並在WeakHashMap中刪除掉，以達到同步。

圖中被虛線標識的元素將會在下一次訪問 WeakHashMap 時被刪除，WeakHashMap 內部會做好一系列的調整工作，所以隊列的作用是標誌已經被GC掉的元素。
關於 WeakHashMap 需要注意三點：
1. 它的鍵是一種弱鍵，放入 WeakHashMap 時，隨時會被回收掉，所以不能確保某次訪問元素一定存在；
2. 它依賴普通的Map進行實現，是一個非線程安全的集合；
3. WeakHashMap 通常作為緩存使用，適合存儲那些只需訪問一次、或只需保存短暫時間的鍵值對。

1.5 HashTable

Hashtable底層存儲結構是數組+鏈表，是一個線程安全的集合。當鏈表過長時，查詢效率過低，會長時間鎖住Hashtable，所以在並發環境下，性能很差，現在基本上被淘汰了，也很少用了。線程安全，它所有的方法都被加上了 synchronized 關鍵字。HashTable 默認長度為 11，負載因子為 0.75F，即元素個數達到數組長度的 75% 時，會進行一次擴容，每次擴容為原來數組長度的 2 倍

2. Collection 集合體系詳解

Collection 集合體系的頂層接口就是Collection，它規定了該集合下的一系列方法。
該集合下可以分為三大類集合：List，Set和Queue
    Set接口：不可存儲重複的元素，且任何操作均需要通過哈希函數映射到集合內部定位元素，集合內部元素默認無序。
    List接口：可存儲重複的元素，且集合內部的元素按照元素插入的順序有序排列，可以通過索引訪問元素。
    Queue接口：是以隊列作為存儲結構，集合內部的元素有序排列，僅可以操作頭結點元素，無法訪問隊列中間的元素。
上面三個接口是最普通，最抽象的實現，而在各個集合接口內部，還會有更加具體的表現，衍生出各種不同的額外功能，使開發者能夠對比各個集合的優勢，擇優使用。

2.1 Set接口

Set接口繼承了Collection接口，是一個不包括重複元素的集合，更確切地說，Set 中任意兩個元素不會出現 o1.equals(o2)，而且 Set 至多只能存儲一個 NULL 值元素。

在Set集合體系中，我們需要着重關注兩點：
存入可變元素時，必須非常小心，因為任意時候元素狀態的改變都有不可能使得 Set 內部出現兩個相等的元素，即 o1.equals(o2) = true，所以一般不要更改存入 Set 中的元素，否則將會破壞了 equals() 的作用！
Set 的最大作用就是判重，在項目中最大的作用也是判重！

HashSet

HashSet 底層藉助 HashMap 實現，我們可以觀察它的多個構造方法，本質上都是 new 一個 HashMap

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
    public HashSet() {
        this.map = new HashMap();
    }
    public HashSet(int initialCapacity, float loadFactor) {
        this.map = new HashMap(initialCapacity, loadFactor);
    }
    public HashSet(int initialCapacity) {
        this.map = new HashMap(initialCapacity);
    }
}

我們可以觀察add()方法和remove()方法是如何將 HashSet 的操作嫁接到 HashMap 的。

private static final Object PRESENT = new Object(); 
public boolean add(E e) { 
   return this.map.put(e, PRESENT) == null; 
} 
public boolean remove(Object o) { 
   return this.map.remove(o) == PRESENT; 
}

HashMap 的 value 值，使用HashSet的開發者只需關注於需要插入的 key，屏蔽了 HashMap 的 value

HashSet 在 HashMap 基礎上實現，所以很多地方可以聯繫到 HashMap：
    底層數據結構：HashSet 也是採用數組 + 鏈表 + 紅黑樹實現
    線程安全性：由於採用 HashMap 實現，而 HashMap 本身線程不安全，在HashSet 中沒有添加額外的同步策略，所以 HashSet 也線程不安全
    存入 HashSet 的對象的狀態最好不要發生變化，因為有可能改變狀態後，在集合內部出現兩個元素o1.equals(o2)，破壞了 equals()的語義。

LinkedHashSet

LinkedHashSet 的代碼少的可憐，如下：

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
    public LinkedHashSet() {
        super(16, .75f, true);
    }
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }
}

關於 LinkedHashSet 需要注意幾個地方：
它繼承了 HashSet，而 HashSet 默認是採用 HashMap 存儲數據的，但是 LinkedHashSet 調用父類構造方法初始化 map 時是 LinkedHashMap 而不是 HashMap，這個要額外注意一下；
由於 LinkedHashMap 不是線程安全的，且在 LinkedHashSet 中沒有添加額外的同步策略，所以 LinkedHashSet 集合也不是線程安全的。

TreeMap

TreeSet 是基於 TreeMap 的實現，所以存儲的元素是有序的，底層的數據結構是數組 + 紅黑樹。

而元素的排列順序有2種，和 TreeMap 相同：自然排序和定製排序，常用的構造方法已經在下面展示出來了，TreeSet 默認按照自然排序，如果需要定製排序，需要傳入Comparator。

public TreeSet() { 
    this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

對 TreeSet 介紹了它的主要實現方式和應用場景，有幾個值得注意的點。
    TreeSet 的所有操作都會轉換為對 TreeMap 的操作，TreeMap 採用紅黑樹實現，任意操作的平均時間複雜度為 O(logN);
    TreeSet 是一個線程不安全的集合；
    TreeSet 常應用於對不重複的元素定製排序，例如玩家戰力排行榜。

2.2 List

List 接口直接繼承 Collection 接口，它定義為可以存儲重複元素的集合，並且元素按照插入順序有序排列，且可以通過索引訪問指定位置的元素。常見的實現有：ArrayList、LinkedList、Vector和Stack。

AbstractList 和 AbstractSequentialList

AbstractList 抽象類實現了 List 接口，其內部實現了所有的 List 都需具備的功能，子類可以專註於實現自己具體的操作邏輯。

AbstractSequentialList 抽象類繼承了 AbstractList，在原基礎上限制了訪問元素的順序只能夠按照順序訪問，而不支持隨機訪問，如果需要滿足隨機訪問的特性，則繼承 AbstractList。子類 LinkedList 使用鏈表實現，所以僅能支持順序訪問，顧繼承了 AbstractSequentialList而不是 AbstractList。

// 查找元素 o 第一次出現的索引位置
public int indexOf(Object o)
// 查找元素 o 最後一次出現的索引位置
public int lastIndexOf(Object o)
//···

Vector 和 Stack

Vector 在現在已經是一種過時的集合了，包括繼承它的 Stack 集合也如此，它們被淘汰的原因都是因為性能低下。

JDK 1.0 時代，ArrayList 還沒誕生，大家都是使用 Vector 集合，但由於 Vector 的每個操作都被 synchronized 關鍵字修飾，即使在線程安全的情況下，仍然進行無意義的加鎖與釋放鎖，造成額外的性能開銷，做了無用功。

在 JDK 1.2 時，Collection 家族出現了，它提供了大量高性能、適用於不同場合的集合，而 Vector 也是其中一員，但由於 Vector 在每個方法上都加了鎖，由於需要兼容許多老的項目，很難在此基礎上優化Vector了，所以漸漸地也就被歷史淘汰了。
現在，在線程安全的情況下，不需要選用 Vector 集合，取而代之的是 ArrayList 集合；在並發環境下，出現了 CopyOnWriteArrayList，Vector 完全被棄用了。

Stack是一種後入先出（LIFO）型的集合容器，如圖中所示，大雄是最後一個進入容器的，top指針指向大雄，那麼彈出元素時，大雄也是第一個被彈出去的。
Stack 繼承了 Vector 類，提供了棧頂的壓入元素操作（push）和彈出元素操作（pop），以及查看棧頂元素的方法（peek）等等，但由於繼承了 Vector，正所謂跟錯老大沒福報，Stack 也漸漸被淘汰了。
取而代之的是後起之秀 Deque接口，其實現有 ArrayDeque，該數據結構更加完善、可靠性更好，依靠隊列也可以實現LIFO的棧操作，所以優先選擇 ArrayDeque 實現棧。

ArrayList

ArrayList 以數組作為存儲結構，它是線程不安全的集合；具有查詢快、在數組中間或頭部增刪慢的特點，所以它除了線程不安全這一點，其餘可以替代Vector，而且線程安全的 ArrayList 可以使用 CopyOnWriteArrayList代替 Vector。

關於 ArrayList 有幾個重要的點需要注意的：
    具備隨機訪問特點，訪問元素的效率較高，ArrayList 在頻繁插入、刪除集合元素的場景下效率較低。
    底層數據結構：ArrayList 底層使用數組作為存儲結構，具備查找快、增刪慢的特點
    線程安全性：ArrayList 是線程不安全的集合
    ArrayList 首次擴容後的長度為 10，調用 add() 時需要計算容器的最小容量。可以看到如果數組elementData為空數組，會將最小容量設置為10，之後會將數組長度完成首次擴容到 10。

// new ArrayList 時的默認空數組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默認容量
private static final int DEFAULT_CAPACITY = 10;
// 計算該容器應該滿足的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

集合從第二次擴容開始，數組長度將擴容為原來的 1.5 倍，即：newLength = oldLength * 1.5

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList

LinkedList 底層採用雙向鏈表數據結構存儲元素，由於鏈表的內存地址非連續，所以它不具備隨機訪問的特點，但由於它利用指針連接各個元素，所以插入、刪除元素只需要操作指針，不需要移動元素，故具有增刪快、查詢慢的特點。它也是一個非線程安全的集合。

由於以雙向鏈表作為數據結構，它是線程不安全的集合；存儲的每個節點稱為一個Node，下圖可以看到 Node 中保存了next和prev指針，item是該節點的值。在插入和刪除時，時間複雜度都保持為 O(1)

關於 LinkedList，除了它是以鏈表實現的集合外，還有一些特殊的特性需要注意的。
    優勢：LinkedList 底層沒有擴容機制，使用雙向鏈表存儲元素，所以插入和刪除元素效率較高，適用於頻繁操作元素的場景
    劣勢：LinkedList 不具備隨機訪問的特點，查找某個元素只能從 head 或 tail 指針一個一個比較，所以查找中間的元素時效率很低
    查找優化：LinkedList 查找某個下標 index 的元素時做了優化，若 index > (size / 2)，則從 head 往後查找，否則從 tail 開始往前查找，代碼如下所示：

LinkedList.Node<E> node(int index) {
    LinkedList.Node x;
    int i;
    if (index < this.size >> 1) { // 查找的下標處於鏈表前半部分則從頭找
        x = this.first;
        for(i = 0; i < index; ++i) { x = x.next; }
        return x;
    } else { // 查找的下標處於數組的後半部分則從尾開始找
        x = this.last;
        for(i = this.size - 1; i > index; --i) { x = x.prev; }
        return x;
    }
}

雙端隊列：使用雙端鏈表實現，並且實現了 Deque 接口，使得 LinkedList 可以用作雙端隊列。下圖可以看到 Node 是集合中的元素，提供了前驅指針和後繼指針，還提供了一系列操作頭結點和尾結點的方法，具有雙端隊列的特性。

LinkedList 集合最讓人樹枝的是它的鏈表結構，但是我們同時也要注意它是一個雙端隊列型的集合。

Deque<Object> deque = new LinkedList<>();

Queue

Queue隊列，在 JDK 中有兩種不同類型的集合實現：單向隊列（AbstractQueue）和雙端隊列（Deque）。

Queue 中提供了兩套增加、刪除元素的 API，當插入或刪除元素失敗時，會有兩種不同的失敗處理策略。

方法及失敗策略	插入方法	刪除方法	查找方法
拋出異常	add()	remove()	get()
返回默認值	offer()	poll()	peek()

選取哪種方法的決定因素：插入和刪除元素失敗時，希望拋出異常還是返回布爾值，

add() 和 offer() 對比：
在隊列長度大小確定的場景下，隊列放滿元素後，添加下一個元素時，add() 會拋出 IllegalStateException異常，而 offer() 會返回 false 。
remove() 和 poll() 對比：
在隊列為空的場景下， remove() 會拋出 NoSuchElementException異常，而 poll() 則返回 null 。
get()和peek()對比：
在隊列為空的情況下，get()會拋出NoSuchElementException異常，而peek()則返回null。

Deque

Deque 接口的實現非常好理解：從單向隊列演變為雙向隊列，內部額外提供雙向隊列的操作方法即可：

Deque接口額外提供了針對隊列的頭結點和尾結點操作的方法，而插入、刪除方法同樣也提供了兩套不同的失敗策略。除了add()和offer()，remove()和poll()以外，還有get()和peek()出現了不同的策略

ArrayDeque

使用數組實現的雙端隊列，它是無界的雙端隊列，最小的容量是8（JDK 1.8）。在 JDK 11 看到它默認容量已經是 16了。ArrayDeque 在日常使用得不多，值得注意的是它與 LinkedList 的對比：LinkedList 採用鏈表實現雙端隊列，而 ArrayDeque 使用數組實現雙端隊列。

/**
 * The minimum capacity that we\'ll use for a newly created deque.
 * Must be a power of 2.
 */
private static final int MIN_INITIAL_CAPACITY = 8;

由於雙端隊列只能在頭部和尾部操作元素，所以刪除元素和插入元素的時間複雜度大部分都穩定在 O(1) ，除非在擴容時會涉及到元素的批量複製操作。但是在大多數情況下，使用它時應該指定一個大概的數組長度，避免頻繁的擴容。

個人觀點：鏈表的插入、刪除操作涉及到指針的操作，我個人認為作者是覺得數組下標的移動要比指針的操作要廉價，而且數組採用連續的內存地址空間，而鏈表元素的內存地址是不連續的，所以數組操作元素的效率在尋址上會比鏈表要快。請批判看待觀點。

PriorityQueue

PriorityQueue 基於優先級堆實現的優先級隊列，而堆是採用數組實現：

/**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements\'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue; // non-private to simplify nested class access

文檔中的描述告訴我們：該數組中的元素通過傳入 Comparator 進行定製排序，如果不傳入Comparator時，則按照元素本身自然排序，但要求元素實現了Comparable接口，所以 PriorityQueue 不允許存儲 NULL 元素。
PriorityQueue 應用場景：元素本身具有優先級，需要按照優先級處理元素

例如VIP玩家與普通玩家，VIP 等級越高的玩家越優先安排玩耍，減少VIP玩家流失。

public static void main(String[] args) {
    Player vip1 = new Player("范仲淹", 1);
    Player vip3 = new Player("竇憲", 2);
    Player vip4 = new Player("弘曆", 4);
    Player vip2 = new Player("蘇定方", 1);
    Player p1 = new Player("王陽明", 0);
    Player p2 = new Player("趙孟頫", 0);
    // 根據VIP等級降序
    PriorityQueue<Player> queue = new PriorityQueue<>((o1, o2) ->  o2.getScore().compareTo(o1.getScore()));
    queue.add(vip1);queue.add(vip4);queue.add(vip3);
    queue.add(p1);queue.add(p2);queue.add(vip2);
    while (!queue.isEmpty()) {
        Player s1 = queue.poll();
        System.out.println(s1.getName() + "進入遊戲; " + "VIP等級: " + s1.getScore());
    }
}
 public static class Player implements Comparable<Player> {
     private String name;
     private Integer score;
     public Player(String name, Integer score) {
         this.name = name;
         this.score = score;
     }
     @Override
     public int compareTo(Player o) {
         return this.score.compareTo(o.getScore());
     }
 }

結果如下：

弘曆進入遊戲; VIP等級: 4
竇憲進入遊戲; VIP等級: 2
范仲淹進入遊戲; VIP等級: 1
蘇定方進入遊戲; VIP等級: 1
王陽明進入遊戲; VIP等級: 0
趙孟頫進入遊戲; VIP等級: 0

VIP 等級越高（優先級越高）就越優先安排玩（優先處理），類似這種有優先級的場景還有非常多，各位可以發揮自己的想像力。

PriorityQueue 總結：
PriorityQueue 是基於優先級堆實現的優先級隊列，而堆是用數組維護的
PriorityQueue 適用於元素按優先級處理的業務場景，例如用戶在請求人工客服需要排隊時，根據用戶的VIP等級進行插隊處理，等級越高，越先安排客服。

四、下面來個大總結：

數據類型	插入刪除的時間複雜度	查詢時間複雜度	底層數據結構	是否線程安全
Vector	O(N)	O(1)	數組	是
ArrayList	O(N)	O(1)	數組	否
LinkedList	O(1)	O(N)	雙向鏈表	否
HashSet	O(1)	O(1)	數組+鏈表+紅黑樹	否
TreeSet	O(LogN)	O(LogN)	紅黑樹	否
LingkedHashSet	O(1)	O(1)~ O(N)	數組+鏈表+紅黑樹	否
ArrayDeque	O(N)	O(1)	數組	否
PriorityQueue	O(LogN)	O(LogN)	堆(數組)	否
HashMap	O(1)~ O(N)	O(1)~ O(N)	數組+鏈表+紅黑樹	否
TreeMap	O(LogN)	O(LogN)	數組+紅黑樹	否
HashTable	O(1) / O(N)	O(1) / O(N)	數組+鏈表	是

Tags: Java基礎學習之路