集合在我們日常開發使用的次數數不勝數，ArrayList/LinkedList/HashMap/HashSet······信手拈來，抬手就拿來用，在 IDE 上龍飛鳳舞，但是作為一名合格的優雅的程序猿，僅僅了解怎麼使用API是遠遠不夠的，如果在調用API時，知道它內部發生了什麼事情，就像開了透視外掛一樣，洞穿一切，這種感覺才真的爽，而且這樣就不是集合提供什麼功能給我們使用，而是我們選擇使用它的什麼功能了。

集合框架總覽

下圖堪稱集合框架的上帝視角，講到集合框架不得不看的就是這幅圖，當然，你會覺得眼花繚亂，不知如何看起，這篇文章帶你一步一步地秒殺上面的每一個接口、抽象類和具體類。我們將會從最頂層的接口開始講起，一步一步往下深入，幫助你把對集合的認知構建起一個知識網絡。

工欲善其事必先利其器，讓我們先來過一遍整個集合框架的組成部分：

1. 集合框架提供了兩個遍歷接口：Iterator和ListIterator，其中後者是前者的優化版，支持在任意一個位置進行前後雙向遍歷。注意圖中的Collection應當繼承的是Iterable而不是Iterator，後面會解釋Iterable和Iterator的區別
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. 四種抽象集合類型內部也會衍生出許多具有不同特性的集合類，不同場景下擇優使用，沒有最佳的集合

上面了解了整個集合框架體系的組成部分，接下來的章節會嚴格按照上面羅列的順序進行講解，每一步都會有承上啟下的作用

學習Set前，最好最好要先學習Map，因為Set的操作本質上是對Map的操作，往下看準沒錯

Iterator Iterable ListIterator

在第一次看這兩個接口，真以為是一模一樣的，沒發現裡面有啥不同，存在即合理，它們兩個還是有本質上的區別的。

首先來看Iterator接口：

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

提供的API接口含義如下：

• hasNext()：判斷集合中是否存在下一個對象
• next()：返回集合中的下一個對象，並將訪問指針移動一位
• remove()：刪除集合中調用next()方法返回的對象

在早期，遍歷集合的方式只有一種，通過Iterator疊代器操作

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

再來看Iterable接口：

public interface Iterable<T> {
    Iterator<T> iterator();
    // JDK 1.8
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
}

可以看到Iterable接口裡面提供了Iterator接口，所以實現了Iterable接口的集合依舊可以使用疊代器遍歷和操作集合中的對象；

而在 JDK 1.8中，Iterable提供了一個新的方法forEach()，它允許使用增強 for 循環遍歷對象。

List<Integer> list = new ArrayList<>();
for (Integer num : list) {
    System.out.println(num);
}

我們通過命令：javap -c反編譯上面的這段代碼後，發現它只是 Java 中的一個語法糖，本質上還是調用Iterator去遍歷。

翻譯成代碼，就和一開始的Iterator疊代器遍歷方式基本相同了。

Iterator iter = list.iterator();
while (iter.hasNext()) {
    Integer num = iter.next();
    System.out.println(num);
}

還有更深層次的探討：為什麼要設計兩個接口Iterable和Iterator，而不是保留其中一個就可以了。

簡單講解：Iterator的保留可以讓子類去實現自己的疊代器，而Iterable接口更加關注於for-each的增強語法。具體可參考：Java中的Iterable與Iterator詳解

關於Iterator和Iterable的講解告一段落，下面來總結一下它們的重點：

1. Iterator是提供集合操作內部對象的一個疊代器，它可以遍歷、移除對象，且只能夠單向移動
2. Iterable是對Iterator的封裝，在JDK 1.8時，實現了Iterable接口的集合可以使用增強 for 循環遍歷集合對象，我們通過反編譯後發現底層還是使用Iterator疊代器進行遍歷

等等，這一章還沒完，還有一個ListIterator。它繼承 Iterator 接口，在遍歷List集合時可以從任意索引下標開始遍歷，而且支持雙向遍歷。

ListIterator 存在於 List 集合之中，通過調用方法可以返回起始下標為 index的疊代器

List<Integer> list = new ArrayList<>();
// 返回下標為0的疊代器
ListIterator<Integer> listIter1 = list.listIterator(); 
// 返回下標為5的疊代器
ListIterator<Integer> listIter2 = list.listIterator(5); 

ListIterator 中有幾個重要方法，大多數方法與 Iterator 中定義的含義相同，但是比 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 接口是集合框架體系的兩大門派，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)
• 刪除方法：remove(Object var1) / removeAll(Collection<?> var1)
• 查找方法：contains(Object var1) / containsAll(Collection<?> var1);
• 查詢集合自身信息：size() / isEmpty()
• ···

在Collection接口下，同樣會將集合細分為不同的種類：

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

Map 集合體系詳解

Map接口是由<key, value>組成的集合，由key映射到唯一的value，所以Map不能包含重複的key，每個鍵至多映射一個值。下圖是整個 Map 集合體系的主要組成部分，我將會按照日常使用頻率從高到低一一講解。

不得不提的是 Map 的設計理念：定位元素的時間複雜度優化到 O(1)

Map 體系下主要分為 AbstractMap 和 SortedMap兩類集合

AbstractMap是對 Map 接口的擴展，它定義了普通的 Map 集合具有的通用行為，可以避免子類重複編寫大量相同的代碼，子類繼承 AbstractMap 後可以重寫它的方法，實現額外的邏輯，對外提供更多的功能。

SortedMap 定義了該類 Map 具有 排序行為，同時它在內部定義好有關排序的抽象方法，當子類實現它時，必須重寫所有方法，對外提供排序功能。

HashMap

HashMap 是一個最通用的利用哈希表存儲元素的集合，將元素放入 HashMap 時，將key的哈希值轉換為數組的索引下標確定存放位置，查找時，根據key的哈希地址轉換成數組的索引下標確定查找位置。

HashMap 底層是用數組 + 鍊表 + 紅黑樹這三種數據結構實現，它是非線程安全的集合。

發送哈希衝突時，HashMap 的解決方法是將相同映射地址的元素連成一條鍊表，如果鍊表的長度大於8時，且數組的長度大於64則會轉換成紅黑樹數據結構。

關於 HashMap 的簡要總結：

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

LinkedHashMap

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

LinkedHashMap 是 HashMap 的子類，所以它具備 HashMap 的所有特點，其次，它在 HashMap 的基礎上維護了一條雙向鍊表，該鍊表存儲了所有元素，默認元素的順序與插入順序一致。若accessOrder屬性為true，則遍歷順序按元素的訪問次序進行排序。

// 頭節點
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()方法中可以看到下面這段代碼，其作用是挪動結點的位置：

if (this.accessOrder) {
    this.afterNodeAccess(e);
}

只要調用了get()且accessOrder = true，則會將該節點更新到鍊表尾部，具體的邏輯在afterNodeAccess()中，感興趣的可翻看源碼，篇幅原因這裡不再展開。

現在如果要實現一個LRU緩存策略，則需要做兩件事情：

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

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

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

這裡就要貼出一道大廠面試必考題目：146. LRU緩存機制，只要跟著我的步驟，就能順利完成這道大廠題了。

關於 LinkedHashMap 主要介紹兩點：

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

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));

TreeMap 底層使用了數組+紅黑樹實現，所以裡面的存儲結構可以理解成下面這幅圖哦。

圖中紅黑樹的每一個節點都是一個Entry，在這裡為了圖片的簡潔性，就不標明 key 和 value 了，注意這些元素都是已經按照key排好序了，整個數據結構都是保持著有序 的狀態！

關於自然排序與定製排序：

• 自然排序：要求key必須實現Comparable接口。

由於Integer類實現了 Comparable 接口，按照自然排序規則是按照key從小到大排序。

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

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

TreeMap<Integer, String> treeMap = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1));
treeMap.put(1, "ONE");
treeMap.put(2, "TWO");
treeMap.put(4, "FOUR");
treeMap.put(3, "THREE");
System.out.println(treeMap);
// {4=FOUR, 3=THREE, 2=TWO, 1=ONE}

通過傳入新的Comparator比較器，可以覆蓋默認的排序規則，上面的代碼按照key降序排序，在實際應用中還可以按照其它規則自定義排序。

compare()方法的返回值有三種，分別是：0，-1，+1

（1）如果返回0，代表兩個元素相等，不需要調換順序

（2）如果返回+1，代表前面的元素需要與後面的元素調換位置

（3）如果返回-1，代表前面的元素不需要與後面的元素調換位置

而何時返回+1和-1，則由我們自己去定義，JDK默認是按照自然排序，而我們可以根據key的不同去定義降序還是升序排序。

關於 TreeMap 主要介紹了兩點：

1. 它底層是由紅黑樹這種數據結構實現的，所以操作的時間複雜度恆為O(logN)
2. TreeMap 可以對key進行自然排序或者自定義排序，自定義排序時需要傳入Comparator，而自然排序要求key實現了Comparable接口
3. TreeMap 不是線程安全的。

WeakHashMap

WeakHashMap 日常開發中比較少見，它是基於普通的Map實現的，而裡面Entry中的鍵在每一次的垃圾回收都會被清除掉，所以非常適合用於短暫訪問、僅訪問一次的元素，緩存在WeakHashMap中，並儘早地把它回收掉。

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

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

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

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

private void expungeStaleEntries() {
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            // 去 WeakHashMap 中刪除該鍵值對
        }
    }
}

再者，需要注意 WeakHashMap 底層存儲的元素的數據結構是數組 + 鍊表，沒有紅黑樹哦，可以換一個角度想，如果還有紅黑樹，那乾脆直接繼承 HashMap ，然後再擴展就完事了嘛，然而它並沒有這樣做：

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

所以，WeakHashMap 的數據結構圖我也為你準備好啦。

圖中被虛線標識的元素將會在下一次訪問 WeakHashMap 時被刪除掉，WeakHashMap 內部會做好一系列的調整工作，所以記住隊列的作用就是標誌那些已經被GC回收掉的元素。

關於 WeakHashMap 需要注意兩點：

1. 它的鍵是一種弱鍵，放入 WeakHashMap 時，隨時會被回收掉，所以不能確保某次訪問元素一定存在
2. 它依賴普通的Map進行實現，是一個非線程安全的集合
3. WeakHashMap 通常作為緩存使用，適合存儲那些只需訪問一次、或只需保存短暫時間的鍵值對

Hashtable

Hashtable 底層的存儲結構是數組 + 鍊表，而它是一個線程安全的集合，但是因為這個線程安全，它就被淘汰掉了。

下面是Hashtable存儲元素時的數據結構圖，它只會存在數組+鍊表，當鍊表過長時，查詢的效率過低，而且會長時間鎖住Hashtable。

這幅圖是否有點眼熟哈哈哈哈，本質上就是 WeakHashMap 的底層存儲結構了。你千萬別問為什麼 WeakHashMap 不繼承 Hashtable 哦，Hashtable 的性能在並發環境下非常差，在非並發環境下可以用HashMap更優。

HashTable 本質上是 HashMap 的前輩，它被淘汰的原因也主要因為兩個字：性能

HashTable 是一個 線程安全 的 Map，它所有的方法都被加上了 synchronized 關鍵字，也是因為這個關鍵字，它註定成為了時代的棄兒。

HashTable 底層採用 數組+鍊表 存儲鍵值對，由於被棄用，後人也沒有對它進行任何改進

HashTable 默認長度為 11，負載因子為 0.75F，即元素個數達到數組長度的 75% 時，會進行一次擴容，每次擴容為原來數組長度的 2 倍

HashTable 所有的操作都是線程安全的。

Collection 集合體系詳解

Collection 集合體系的頂層接口就是Collection，它規定了該集合下的一系列行為約定。

該集合下可以分為三大類集合：List，Set和Queue

Set接口定義了該類集合不允許存儲重複的元素，且任何操作時均需要通過哈希函數映射到集合內部定位元素，集合內部的元素默認是無序的。

List接口定義了該類集合允許存儲重複的元素，且集合內部的元素按照元素插入的順序有序排列，可以通過索引訪問元素。

Queue接口定義了該類集合是以隊列作為存儲結構，所以集合內部的元素有序排列，僅可以操作頭結點元素，無法訪問隊列中間的元素。

上面三個接口是最普通，最抽象的實現，而在各個集合接口內部，還會有更加具體的表現，衍生出各種不同的額外功能，使開發者能夠對比各個集合的優勢，擇優使用。

Set 接口

Set接口繼承了Collection接口，是一個不包括重複元素的集合，更確切地說，Set 中任意兩個元素不會出現 o1.equals(o2)，而且 Set 至多只能存儲一個 NULL 值元素，Set 集合的組成部分可以用下面這張圖概括：

在 Set 集合體系中，我們需要著重關注兩點：

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

接下來我們去看它的實現類和子類： AbstractSet 和 SortedSet

AbstractSet 抽象類

AbstractSet 是一個實現 Set 的一個抽象類，定義在這裡可以將所有具體 Set 集合的相同行為在這裡實現，避免子類包含大量的重複代碼

所有的 Set 也應該要有相同的 hashCode() 和 equals() 方法，所以使用抽象類把該方法重寫後，子類無需關心這兩個方法。

public abstract class AbstractSet<E> implements Set<E> {
    // 判斷兩個 set 是否相等
    public boolean equals(Object o) {
        if (o == this) { // 集合本身
            return true;
        } else if (!(o instanceof Set)) { // 集合不是 set
            return false;
        } else {
            // 比較兩個集合的元素是否全部相同
        }
    }
    // 計算所有元素的 hashcode 總和
    public int hashCode() { 
        int h = 0;
        Iterator i = this.iterator();
        while(i.hasNext()) {
            E obj = i.next();
            if (obj != null) {
                h += obj.hashCode();
            }
        }
        return h;
    }
}

SortedSet 接口

SortedSet 是一個接口，它在 Set 的基礎上擴展了排序的行為，所以所有實現它的子類都會擁有排序功能。

public interface SortedSet<E> extends Set<E> {
    // 元素的比較器,決定元素的排列順序
    Comparator<? super E> comparator(); 
    // 獲取 [var1, var2] 之間的 set
    SortedSet<E> subSet(E var1, E var2); 
    // 獲取以 var1 開頭的 Set
    SortedSet<E> headSet(E var1); 
    // 獲取以 var1 結尾的 Set
    SortedSet<E> tailSet(E var1); 
    // 獲取首個元素
    E first(); 
    // 獲取最後一個元素
    E last();
}

HashSet

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

這也是這篇文章為什麼先講解 Map 再講解 Set 的原因！先學習 Map，有助於理解 Set

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;
}

我們看到 PRESENT 就是一個靜態常量：使用 PRESENT 作為 HashMap 的 value 值，使用HashSet的開發者只需關注於需要插入的 key，屏蔽了 HashMap 的 value

上圖可以觀察到每個Entry的value都是 PRESENT 空對象，我們就不用再理會它了。

HashSet 在 HashMap 基礎上實現，所以很多地方可以聯繫到 HashMap：

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

LinkedHashSet

LinkedHashSet 的代碼少的可憐，不信我給你我粘出來

少歸少，還是不能鬧，LinkedHashSet繼承了HashSet，我們跟隨到父類 HashSet 的構造方法看看

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    this.map = new LinkedHashMap(initialCapacity, loadFactor);
}

發現父類中 map 的實現採用LinkedHashMap，這裡注意不是HashMap，而 LinkedHashMap 底層又採用 HashMap + 雙向鍊表 實現的，所以本質上 LinkedHashSet 還是使用 HashMap 實現的。

LinkedHashSet -> LinkedHashMap -> HashMap + 雙向鍊表

而 LinkedHashMap 是採用 HashMap和雙向鍊表實現的，這條雙向鍊表中保存了元素的插入順序。所以 LinkedHashSet 可以按照元素的插入順序遍曆元素，如果你熟悉LinkedHashMap，那 LinkedHashSet 也就更不在話下了。

關於 LinkedHashSet 需要注意幾個地方：

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

TreeSet

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

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

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

TreeSet 應用場景有很多，像在遊戲里的玩家戰鬥力排行榜

public class Player implements Comparable<Integer> {
    public String name;
    public int score;
    @Override
    public int compareTo(Student o) {
        return Integer.compareTo(this.score, o.score);
    }
}
public static void main(String[] args) {
    Player s1 = new Player("張三", 100);
    Player s2 = new Player("李四", 90);
    Player s3 = new Player("王五", 80);
    TreeSet<Player> set = new TreeSet();
    set.add(s2); set.add(s1); set.add(s3);
    System.out.println(set);
}
// [Student{name='王五', score=80}, Student{name='李四', score=90}, Student{name='張三', score=100}]

對 TreeSet 介紹了它的主要實現方式和應用場景，有幾個值得注意的點。

• TreeSet 的所有操作都會轉換為對 TreeMap 的操作，TreeMap 採用紅黑樹實現，任意操作的平均時間複雜度為 O(logN)
• TreeSet 是一個線程不安全的集合
• TreeSet 常應用於對不重複的元素定製排序，例如玩家戰力排行榜

注意:TreeSet判斷元素是否重複的方法是判斷compareTo()方法是否返回0，而不是調用 hashcode() 和 equals() 方法，如果返回 0 則認為集合內已經存在相同的元素，不會再加入到集合當中。

List 接口

List 接口和 Set 接口齊頭並進，是我們日常開發中接觸的很多的一種集合類型了。整個 List 集合的組成部分如下圖

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

AbstractList 和 AbstractSequentialList

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

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

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

Vector

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

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

public synchronized boolean add(E e);
public synchronized E get(int index);

在 JDK 1.2 時，Collection 家族出現了，它提供了大量高性能、適用於不同場合的集合，而 Vector 也是其中一員，但由於 Vector 在每個方法上都加了鎖，由於需要兼容許多老的項目，很難在此基礎上優化Vector了，所以漸漸地也就被歷史淘汰了。

現在，在線程安全的情況下，不需要選用 Vector 集合，取而代之的是 ArrayList 集合；在並發環境下，出現了 CopyOnWriteArrayList，Vector 完全被棄用了。

Stack

Stack是一種後入先出（LIFO）型的集合容器，如圖中所示，大雄是最後一個進入容器的，top指針指向大雄，那麼彈出元素時，大雄也是第一個被彈出去的。

Stack 繼承了 Vector 類，提供了棧頂的壓入元素操作（push）和彈出元素操作（pop），以及查看棧頂元素的方法（peek）等等，但由於繼承了 Vector，正所謂跟錯老大沒福報，Stack 也漸漸被淘汰了。

取而代之的是後起之秀 Deque接口，其實現有 ArrayDeque，該數據結構更加完善、可靠性更好，依靠隊列也可以實現LIFO的棧操作，所以優先選擇 ArrayDeque 實現棧。

Deque<Integer> stack = new ArrayDeque<Integer>();

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

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()出現了不同的策略

AbstractQueue 抽象類

AbstractQueue 類中提供了各個 API 的基本實現，主要針對各個不同的處理策略給出基本的方法實現，定義在這裡的作用是讓子類根據其方法規範（操作失敗時拋出異常還是返回默認值）實現具體的業務邏輯。

LinkedList

LinkedList 在上面已經詳細解釋了，它實現了 Deque 接口，提供了針對頭結點和尾結點的操作，並且每個結點都有前驅和後繼指針，具備了雙向隊列的所有特性。

ArrayDeque

使用數組實現的雙端隊列，它是無界的雙端隊列，最小的容量是8（JDK 1.8）。在 JDK 11 看到它默認容量已經是 16了。

ArrayDeque 在日常使用得不多，值得注意的是它與 LinkedList 的對比：LinkedList 採用鍊表實現雙端隊列，而 ArrayDeque 使用數組實現雙端隊列。

在文檔中作者寫到：ArrayDeque 作為棧時比 Stack 性能好，作為隊列時比 LinkedList 性能好

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

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

PriorityQueue

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

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

PriorityQueue 應用場景：元素本身具有優先級，需要按照優先級處理元素

• 例如遊戲中的VIP玩家與普通玩家，VIP 等級越高的玩家越先安排進入伺服器玩耍，減少玩家流失。

public static void main(String[] args) {
    Student vip1 = new Student("張三", 1);
    Student vip3 = new Student("洪七", 2);
    Student vip4 = new Student("老八", 4);
    Student vip2 = new Student("李四", 1);
    Student normal1 = new Student("王五", 0);
    Student normal2 = new Student("趙六", 0);
    // 根據玩家的 VIP 等級進行降序排序
    PriorityQueue<Student> queue = new PriorityQueue<>((o1, o2) ->  o2.getScore().compareTo(o1.getScore()));
    queue.add(vip1);queue.add(vip4);queue.add(vip3);
    queue.add(normal1);queue.add(normal2);queue.add(vip2);
    while (!queue.isEmpty()) {
        Student s1 = queue.poll();
        System.out.println(s1.getName() + "進入遊戲; " + "VIP等級: " + s1.getScore());
    }
}
 public static class Student implements Comparable<Student> {
     private String name;
     private Integer score;
     public Student(String name, Integer score) {
         this.name = name;
         this.score = score;
     }
     @Override
     public int compareTo(Student o) {
         return this.score.compareTo(o.getScore());
     }
 }

執行上面的代碼可以得到下面這種有趣的結果，可以看到氪金使人帶來快樂。

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

PriorityQueue 總結：

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

章節結束各集合總結：（以 JDK1.8 為例）

數據類型插入、刪除時間複雜度查詢時間複雜度底層數據結構是否線程安全VectorO(N)O(1)數組是（已淘汰）ArrayListO(N)O(1)數組否LinkedListO(1)O(N)雙向鍊表否HashSetO(1)O(1)數組+鍊表+紅黑樹否TreeSetO(logN)O(logN)紅黑樹否LinkedHashSetO(1)O(1)~O(N)數組 + 鍊表 + 紅黑樹否ArrayDequeO(N)O(1)數組否PriorityQueueO(logN)O(logN)堆（數組實現）否HashMapO(1) ~ O(N)O(1) ~ O(N)數組+鍊表+紅黑樹否TreeMapO(logN)O(logN)數組+紅黑樹否HashTableO(1) / O(N)O(1) / O(N)數組+鍊表是（已淘汰）

文末總結

這一篇文章對各個集合都有些點到即止的味道，此文的目的是對整個集合框架有一個較為整體的了解，分析了最常用的集合的相關特性，以及某些特殊集合的應用場景例如TreeSet、TreeMap這種可定製排序的集合。

• Collection 接口提供了整個集合框架最通用的增刪改查以及集合自身操作的抽象方法，讓子類去實現
• Set 接口決定了它的子類都是無序、無重複元素的集合，其主要實現有HashSet、TreeSet、LinkedHashSet。HashSet 底層採用 HashMap 實現，而 TreeSet 底層使用 TreeMap 實現，大部分 Set 集合的操作都會轉換為 Map 的操作，TreeSet 可以將元素按照規則進行排序。
• List 接口決定了它的子類都是有序、可存儲重複元素的集合，常見的實現有 ArrayList，LinkedList，VectorArrayList 使用數組實現，而 LinkedList 使用鍊表實現，所以它們兩個的使用場景幾乎是相反的，頻繁查詢的場景使用 ArrayList，而頻繁插入刪除的場景最好使用 LinkedListLinkedList 和 ArrayDeque 都可用於雙端隊列，而 Josh Bloch and Doug Lea 認為 ArrayDeque 具有比 LinkedList 更好的性能，ArrayDeque使用數組實現雙端隊列，LinkedList使用鍊表實現雙端隊列。
• Queue 接口定義了隊列的基本操作，子類集合都會擁有隊列的特性：先進先出，主要實現有：LinkedList，ArrayDequePriorityQueue 底層使用二叉堆維護的優先級隊列，而二叉堆是由數組實現的，它可以按照元素的優先級進行排序，優先級越高的元素，排在隊列前面，優先被彈出處理。
• Map接口定義了該種集合類型是以<key,value>鍵值對形式保存，其主要實現有：HashMap，TreeMap，LinkedHashMap，HashtableLinkedHashMap 底層多加了一條雙向鍊表，設置accessOrder為true並重寫方法則可以實現LRU緩存TreeMap 底層採用數組+紅黑樹實現，集合內的元素默認按照自然排序，也可以傳入Comparator定製排序

看到這裡非常不容易，感謝你願意閱讀我的文章，希望能對你有所幫助，你可以參考著文末總結的順序，每當我提到一個集合時，回想它的重要知識點是什麼，主要就是底層數據結構，線程安全性，該集合的一兩個特有性質，只要能夠回答出來個大概，我相信之後運用這些數據結構，你能夠熟能生巧。

本文對整個集合體系的所有常用的集合類都分析了，這裡並沒有對集合內部的實現深入剖析，我想先從最宏觀的角度讓大家了解每個集合的的作用，應用場景，以及簡單的對比，之後會抽時間對常見的集合進行源碼剖析，盡情期待，感謝閱讀！

最後有些話想說：這篇文章花了我半個月去寫，也是意義重大，多謝 cxuan哥一直指導我寫文章，一步一步地去打磨出一篇好的文章真的非常不容易，寫下的每一個字都能夠讓別人看得懂是一件非常難的事情，總結出最精華的知識分享給你們也是非常難的一件事情，希望能夠一直進步下去！不忘初心，熱愛分享，喜愛寫作。

大家好，我是 cxuan，我自己手寫了四本 PDF，分別是 Java基礎總結、HTTP 核心總結、計算機基礎知識，作業系統核心總結，我已經整理成為 PDF，可以關注公眾號 Java建設者 回復 PDF 領取優質資料。