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基础学习之路