兩萬字長文讀懂 Java 集合

作者 | 小菠蘿

來源 | JAVA建設者（ID：javajianshe）

這篇文章歷經(jīng)過 5 次的打磨和修復，只為把最好的文章為大家分享。

集合在我們?nèi)粘ｉ_發(fā)使用的次數(shù)數(shù)不勝數(shù)， ArrayList / LinkedList / HashMap / HashSet……信手拈來，抬手就拿來用，在 IDE 上龍飛鳳舞，但是作為一名合格的優(yōu)雅的程序猿，僅僅了解怎么使用 API 是遠遠不夠的，如果在調(diào)用 API 時，知道它內(nèi)部發(fā)生了什么事情，就像開了透視外掛一樣，洞穿一切，這種感覺才真的爽，而且這樣就不是集合提供什么功能給我們使用，而是我們選擇使用它的什么功能了。

集合框架總覽

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

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

集合框架提供了兩個遍歷接口：Iterator 和 ListIterator，其中后者是前者的優(yōu)化版，支持在任意一個位置進行前后雙向遍歷。注意圖中的 Collection 應當繼承的是 Iterable 而不是 Iterator，后面會解釋 Iterable 和 Iterator 的區(qū)別。
整個集合框架分為兩個門派（類型）：Collection 和 Map，前者是一個容器，存儲一系列的對象；后者是鍵值對 <key, value>，存儲一系列的鍵值對。
在集合框架體系下，衍生出四種具體的集合類型：Map、Set、List、Queue。
Map 存儲 <key,value> 鍵值對，查找元素時通過 key 查找 value。
Set 內(nèi)部存儲一系列不可重復的對象，且是一個無序集合，對象排列順序不一。
List 內(nèi)部存儲一系列可重復的對象，是一個有序集合，對象按插入順序排列。
Queue 是一個隊列容器，其特性與 List 相同，但只能從隊頭和隊尾操作元素。
JDK 為集合的各種操作提供了兩個工具類 Collections 和 Arrays，之后會講解工具類的常用方法。
四種抽象集合類型內(nèi)部也會衍生出許多具有不同特性的集合類，不同場景下?lián)駜?yōu)使用，沒有最佳的集合。

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

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

Iterator Iterable ListIterator

在第一次看這兩個接口，真以為是一模一樣的，沒發(fā)現(xiàn)里面有啥不同，存在即合理，它們兩個還是有本質上的區(qū)別的。

首先來看 Iterator 接口：

public interface Iterator<E> {
booleanhasNext;
E next;
voidremove;
}

提供的 API 接口含義如下：

hasNext：判斷集合中是否存在下一個對象
next：返回集合中的下一個對象，并將訪問指針移動一位
remove：刪除集合中調(diào)用 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 voidforEach(Consumer<? super T> action) {
Objects.requireNon(action);
for (T t : this) {
action.accept(t);
}
}
}

可以看到 Iterable 接口里面提供了 Iterator 接口，所以實現(xiàn)了 Iterable 接口的

集合依舊可以使用迭代器遍歷和操作集合中的對象；

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

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

我們通過命令：javap -c 反編譯上面的這段代碼后，發(fā)現(xiàn)它只是 Java 中的一個語法糖，本質上還是調(diào)用 Iterator 去遍歷。

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

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

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

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

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

Iterator 是提供集合操作內(nèi)部對象的一個迭代器，它可以遍歷、移除對象，且只能夠單向移動。
Iterable 是對 Iterator 的封裝，在 JDK 1.8 時，實現(xiàn)了 Iterable 接口的集合可以使用增強 for 循環(huán)遍歷集合對象，我們通過反編譯后發(fā)現(xiàn)底層還是使用 Iterator 迭代器進行遍歷。

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

ListIterator 存在于 List 集合之中，通過調(diào)用方法可以返回起始下標為 index的迭代器：

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

ListIterator 中有幾個重要方法，大多數(shù)方法與 Iterator 中定義的含義相同，但是比 Iterator 強大的地方是可以在任意一個下標位置返回該迭代器，且可以實現(xiàn)雙向遍歷。

public interface ListIterator<E> extends Iterator<E> {
booleanhasNext;
E next;
booleanhasPrevious;
E previous;
intnextIndex;
intpreviousIndex;
voidremove;
// 替換當前下標的元素,即訪問過的最后一個元素
voidset(E e);
voidadd(E e);
}

Map 和 Collection 接口

Map 接口和 Collection 接口是集合框架體系的兩大門派，Collection 是存儲元素本身，而 Map 是存儲 <key, value> 鍵值對，在 Collection 門派下有一小部分弟子去偷師，利用 Map 門派下的弟子來修煉自己。

是不是聽的一頭霧水哈哈哈，舉個例子你就懂了：HashSet 底層利用了HashMa，TreeSet底層用了TreeMap，LinkedHashSet底層用了LinkedHashMap。

下面我會詳細講到各個具體集合類哦，所以在這里，我們先從整體上了解這兩個門派的特點和區(qū)別。

Map 接口定義了存儲的數(shù)據(jù)結構是 < key, value> 形式，根據(jù) key 映射到 value，一個 key 對應一個 value ，所以 key 不可重復，而 value 可重復。

在 Map 接口下會將存儲的方式細分為不同的種類：

SortedMap 接口：該類映射可以對 <key, value> 按照自己的規(guī)則進行排序，具體實現(xiàn)有 TreeMap
AbsractMap：它為子類提供好一些通用的 API 實現(xiàn)，所有的具體 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 接口：一個不允許存儲重復元素的無序集合，具體實現(xiàn)有 HashSet / TreeSet···
List 接口：一個可存儲重復元素的有序集合，具體實現(xiàn)有 ArrayList / LinkedList···
Queue 接口：一個可存儲重復元素的隊列，具體實現(xiàn)有 PriorityQueue / ArrayDeque···

Map 集合體系詳解

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

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

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

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

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

HashMap

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

HashMap 底層是用數(shù)組 + 鏈表 + 紅黑樹這三種數(shù)據(jù)結構實現(xiàn)，它是非線程安全的集合。

發(fā)送哈希沖突時，HashMap 的解決方法是將相同映射地址的元素連成一條鏈表，如果鏈表的長度大于 8 時，且數(shù)組的長度大于 64 則會轉換成紅黑樹數(shù)據(jù)結構。

關于 HashMap 的簡要總結：

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

LinkedHashMap

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

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

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

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

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

該方法可以移除最靠近鏈表頭部的一個節(jié)點，而在 get 方法中可以看到下面這段代碼，其作用是挪動結點的位置：

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

只要調(diào)用了 get 且 accessOrder=true，則會將該節(jié)點更新到鏈表尾部，具體

的邏輯在afterNodeAccess中，感興趣的可翻看源碼，篇幅原因這里不再展開。

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

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

構造器可以設定 accessOrder

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

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

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

關于 LinkedHashMap 主要介紹兩點：

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

TreeMap

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

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

TreeMap 底層使用了數(shù)組+紅黑樹實現(xiàn)，所以里面的存儲結構可以理解成下面這幅圖哦。

圖中紅黑樹的每一個節(jié)點都是一個 Entry，在這里為了圖片的簡潔性，就不標明 key 和 value 了，注意這些元素都是已經(jīng)按照 key 排好序了，整個數(shù)據(jù)結構都是保持著有序的狀態(tài)！

關于自然排序與定制排序：

自然排序：要求 key 必須實現(xiàn) Comparable 接口。

由于 Integer 類實現(xiàn)了 Comparable 接口，按照自然排序規(guī)則是按照 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

實現(xiàn) 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 比較器，可以覆蓋默認的排序規(guī)則，上面的代碼按

照key降序排序，在實際應用中還可以按照其它規(guī)則自定義排序。

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

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

（2）如果返回+1，代表前面的元素需要與后面的元素調(diào)換位置

（3）如果返回-1，代表前面的元素不需要與后面的元素調(diào)換位置

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

關于 TreeMap 主要介紹了兩點：

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

WeakHashMap

WeakHashMap 日常開發(fā)中比較少見，它是基于普通的 Map 實現(xiàn)的，而里面 Entry 中的鍵在每一次的垃圾回收都會被清除掉，所以非常適合用于短暫訪問、僅訪問一次的元素，緩存在 WeakHashMap 中，并盡早地把它回收掉。

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

在 WeakHashMap 內(nèi)部維護了一個引用隊列 queue

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

這個 queue 里包含了所有被 GC 掉的鍵，當 JVM 開啟 GC 后，如果回收掉

WeakHashMap 中的 key，會將 key 放入 queue 中，在 expungeStaleEntr

ies 中遍歷 queue，把 queue 中的所有 key 拿出來，并在 WeakHashMap

刪除掉，以達到同步。

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

再者，需要注意 WeakHashMap 底層存儲的元素的數(shù)據(jù)結構是數(shù)組 + 鏈表，沒

有紅黑樹哦，可以換一個角度想，如果還有紅黑樹，那干脆直接繼承 HashMap，

然后再擴展就完事了嘛，然而它并沒有這樣做：

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

}

所以，WeakHashMap 的數(shù)據(jù)結構圖我也為你準備好啦。

圖中被虛線標識的元素將會在下一次訪問 WeakHashMap 時被刪除掉，WeakHashMap 內(nèi)部會做好一系列的調(diào)整工作，所以記住隊列的作用就是標志那些已經(jīng)被 GC 回收掉的元素。

關于 WeakHashMap 需要注意兩點：

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

Hashtable

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

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

這幅圖是否有點眼熟哈哈哈哈，本質上就是 WeakHashMap 的底層存儲結構了。你千萬別問為什么 WeakHashMap 不繼承 Hashtable 哦，Hashtable 的性能在并發(fā)環(huán)境下非常差，在非并發(fā)環(huán)境下可以用 HashMap 更優(yōu)。

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

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

HashTable 底層采用數(shù)組+鏈表存儲鍵值對，由于被棄用，后人也沒有對它進行任何改進

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

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

Collection 集合體系詳解

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

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

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

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

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

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

Set 接口

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

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

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

接下來我們?nèi)タ此膶崿F(xiàn)類和子類：AbstractSet 和 SortedSet

AbstractSet 抽象類

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

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

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

SortedSet 接口

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

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 實現(xiàn)，我們可以觀察它的多個構造方法，本質上都是 new 一個 HashMap

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

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

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

HashMap 的。

private static final Object PRESENT = new Object;

public booleanadd(E e) {
return this.map.put(e, PRESENT) == ;
}
public booleanremove(Object o) {
return this.map.remove(o) == PRESENT;
}

我們看到 PRESENT 就是一個靜態(tài)常量：使用 PRESENT 作為 HashMap 的

value 值，使用 HashSet的開發(fā)者只需關注于需要插入的 key，屏蔽了

HashMap 的 value

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

HashSet 在 HashMap 基礎上實現(xiàn)，所以很多地方可以聯(lián)系到 HashMap：

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

LinkedHashSet

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

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

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

發(fā)現(xiàn)父類中 map 的實現(xiàn)采用 LinkedHashMap，這里注意不是 HashMap，而

LinkedHashMap 底層又采用 HashMap + 雙向鏈表實現(xiàn)的，所以本質上

LinkedHashSet 還是使用 HashMap 實現(xiàn)的。

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

image.png

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

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

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

TreeSet

TreeSet 是基于 TreeMap 的實現(xiàn)，所以存儲的元素是有序的，底層的數(shù)據(jù)結構是數(shù)組 + 紅黑樹。

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

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

TreeSet 應用場景有很多，像在游戲里的玩家戰(zhàn)斗力排行榜

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 voidmain(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 介紹了它的主要實現(xiàn)方式和應用場景，有幾個值得注意的點。

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

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

List 接口

List 接口和 Set 接口齊頭并進，是我們?nèi)粘ｉ_發(fā)中接觸的很多的一種集合類型了。整個 List 集合的組成部分如下圖：

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

AbstractList 和 AbstractSequentialList

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

// 查找元素 o 第一次出現(xiàn)的索引位置
public intindexOf(Object o)
// 查找元素 o 最后一次出現(xiàn)的索引位置
public intlastIndexOf(Object o)
//···

AbstractSequentialList 抽象類繼承了 AbstractList，在原基礎上限制了訪問

元素的順序只能夠按照順序訪問，而不支持隨機訪問，如果需要滿足隨機訪問的

特性，則繼承 AbstractList。子類 LinkedList 使用鏈表實現(xiàn)，所以僅能支持順

序訪問，繼承了 AbstractSequentialList而不是 AbstractList。

Vector

vector 在現(xiàn)在已經(jīng)是一種過時的集合了，包括繼承它的 Stack 集合也如此，它們被淘汰的原因都是因為性能低下。

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

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

在 JDK 1.2 時，Collection 家族出現(xiàn)了，它提供了大量高性能、適用於不同場合

的集合，而 Vector 也是其中一員，但由于 Vector 在每個方法上都加了鎖，由于

需要兼容許多老的項目，很難在此基礎上優(yōu)化Vector了，所以漸漸地也就被歷史

淘汰了。

現(xiàn)在，在線程安全的情況下，不需要選用 Vector 集合，取而代之的是 ArrayList 集合；在并發(fā)環(huán)境下，出現(xiàn)了 CopyOnWriteArrayList，Vector 完全被棄用了。

Stack

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

Stack 繼承了 Vector 類，提供了棧頂?shù)膲喝朐夭僮鳎╬ush）和彈出元素操作（pop），以及查看棧頂元素的方法（peek）等等，但由于繼承了 Vector，正所謂跟錯老大沒福報，Stack 也漸漸被淘汰了。

取而代之的是后起之秀 Deque 接口，其實現(xiàn)有 ArrayDeque，該數(shù)據(jù)結構更加完善、可靠性更好，依靠隊列也可以實現(xiàn) LIFO 的棧操作，所以優(yōu)先選擇 ArrayDeque 實現(xiàn)棧。

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

ArrayDeque 的數(shù)據(jù)結構是：數(shù)組，并提供頭尾指針下標對數(shù)組元素進行操作。本文也會講到哦，客官請繼續(xù)往看，莫著急！

ArrayList

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

關于 ArrayList 有幾個重要的點需要注意的：

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

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

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

LinkedList

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

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

關于 LinkedList，除了它是以鏈表實現(xiàn)的集合外，還有一些特殊的特性需要注意的。

優(yōu)勢：LinkedList 底層沒有擴容機制，使用雙向鏈表存儲元素，所以插入和刪除元素效率較高，適用于頻繁操作元素的場景
劣勢：LinkedList 不具備隨機訪問的特點，查找某個元素只能從 head 或 tail 指針一個一個比較，所以查找中間的元素時效率很低
查找優(yōu)化：LinkedList 查找某個下標 index 的元素時做了優(yōu)化，若 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 { // 查找的下標處于數(shù)組的后半部分則從尾開始找
x = this.last;
for(i = this.size - 1; i > index; --i) { x = x.prev; }
return x;
}
}

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

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

Deque<Object> deque = new LinkedList<>;

Queue 接口

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

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

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

add 和 offer 對比：

在隊列長度大小確定的場景下，隊列放滿元素后，添加下一個元素時，add 會拋出 IllegalStateException 異常，而 offer 會返回 false 。

但是它們兩個方法在插入某些不合法的元素時都會拋出三個相同的異常。

remove 和 poll 對比：

在隊列為空的場景下， remove 會拋出 NoSuchElementException 異常，而 poll 則返回。

get 和 peek 對比：

在隊列為空的情況下，get 會拋出 NoSuchElementException 異常，而 peek 則返回。

Deque 接口

Deque 接口的實現(xiàn)非常好理解：從單向隊列演變?yōu)殡p向隊列，內(nèi)部額外提供雙向隊列的操作方法即可：

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

AbstractQueue 抽象類

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

LinkedList

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

ArrayDeque

使用數(shù)組實現(xiàn)的雙端隊列，它是無界的雙端隊列，最小的容量是8（JDK 1.8）。在 JDK 11 看到它默認容量已經(jīng)是 16了。

ArrayDeque 在日常使用得不多，值得注意的是它與 LinkedList 的對比：LinkedList 采用鏈表實現(xiàn)雙端隊列，而 ArrayDeque 使用數(shù)組實現(xiàn)雙端隊列。

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

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

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

PriorityQueue

PriorityQueue 基于優(yōu)先級堆實現(xiàn)的優(yōu)先級隊列，而堆是采用數(shù)組實現(xiàn)：

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

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

例如游戲中的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);
// 根據(jù)玩家的 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;
publicStudent(String name, Integer score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Student o) {
return this.score.compareTo(o.getScore);
}
}

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

VIP 等級越高（優(yōu)先級越高）就越優(yōu)先安排進入游戲（優(yōu)先處理），類似這種有優(yōu)先級的場景還有非常多，各位可以發(fā)揮自己的想象力。

PriorityQueue 總結：

PriorityQueue 是基于優(yōu)先級堆實現(xiàn)的優(yōu)先級隊列，而堆是用數(shù)組維護的
PriorityQueue 適用于元素按優(yōu)先級處理的業(yè)務場景，例如用戶在請求人工客服需要排隊時，根據(jù)用戶的VIP等級進行插隊處理，等級越高，越先安排客服。

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

文末總結

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

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

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

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