兩萬字長文讀懂 Java 集合

作者 | 小菠蘿

來源 | JAVA建設(shè)者（ID：javajianshe）

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

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

集合框架總覽

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

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

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

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

學(xué)習(xí)Set前，最好最好要先學(xué)習(xí) Map，因?yàn)?Set 的操作本質(zhì)上是對(duì) Map 的操作，往下看準(zhǔn)沒錯(cuò)

Iterator Iterable ListIterator

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

首先來看 Iterator 接口：

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

提供的 API 接口含義如下：

hasNext：判斷集合中是否存在下一個(gè)對(duì)象
next：返回集合中的下一個(gè)對(duì)象，并將訪問指針移動(dòng)一位
remove：刪除集合中調(diào)用 next 方法返回的對(duì)象

在早期，遍歷集合的方式只有一種，通過 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 接口，所以實(shí)現(xiàn)了 Iterable 接口的

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

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

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

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

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

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

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

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

關(guān)于 Iterator 和 Iterable 的講解告一段落，下面來總結(jié)一下它們的重點(diǎn)：

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

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

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

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

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

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

Map 和 Collection 接口

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

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

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

Map 接口定義了存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)是 < key, value> 形式，根據(jù) key 映射到 value，一個(gè) key 對(duì)應(yīng)一個(gè) value ，所以 key 不可重復(fù)，而 value 可重復(fù)。

在 Map 接口下會(huì)將存儲(chǔ)的方式細(xì)分為不同的種類：

SortedMap 接口：該類映射可以對(duì) <key, value> 按照自己的規(guī)則進(jìn)行排序，具體實(shí)現(xiàn)有 TreeMap
AbsractMap：它為子類提供好一些通用的 API 實(shí)現(xiàn)，所有的具體 Map 如 HashMap 都會(huì)繼承它

而 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 接口下，同樣會(huì)將集合細(xì)分為不同的種類：

Set 接口：一個(gè)不允許存儲(chǔ)重復(fù)元素的無序集合，具體實(shí)現(xiàn)有 HashSet / TreeSet···
List 接口：一個(gè)可存儲(chǔ)重復(fù)元素的有序集合，具體實(shí)現(xiàn)有 ArrayList / LinkedList···
Queue 接口：一個(gè)可存儲(chǔ)重復(fù)元素的隊(duì)列，具體實(shí)現(xiàn)有 PriorityQueue / ArrayDeque···

Map 集合體系詳解

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

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

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

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

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

HashMap

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

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

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

關(guān)于 HashMap 的簡要總結(jié)：

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

LinkedHashMap

LinkedHashMap 可以看作是 HashMap 和 LinkedList 的結(jié)合：它在 HashMap 的基礎(chǔ)上添加了一條雙向鏈表，默認(rèn)存儲(chǔ)各個(gè)元素的插入順序，但由于這條雙向鏈表，使得 LinkedHashMap 可以實(shí)現(xiàn) LRU緩存淘汰策略，因?yàn)槲覀兛梢栽O(shè)置這條雙向鏈表按照元素的訪問次序進(jìn)行排序。

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

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

利用 LinkedHashMap 可以實(shí)現(xiàn) LRU 緩存淘汰策略，因?yàn)樗峁┝艘粋€(gè)方法：

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

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

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

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

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

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

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

構(gòu)造器可以設(shè)定 accessOrder

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

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

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

關(guān)于 LinkedHashMap 主要介紹兩點(diǎn)：

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

TreeMap

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

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

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

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

關(guān)于自然排序與定制排序：

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

由于 Integer 類實(shí)現(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 時(shí)傳入新的 Comparator，不要求 key

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

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

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

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

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

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

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

關(guān)于 TreeMap 主要介紹了兩點(diǎn)：

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

WeakHashMap

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

當(dāng) Entry 被 GC 時(shí)，WeakHashMap 是如何感知到某個(gè)元素被回收的呢？

在 WeakHashMap 內(nèi)部維護(hù)了一個(gè)引用隊(duì)列 queue

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

這個(gè) queue 里包含了所有被 GC 掉的鍵，當(dāng) JVM 開啟 GC 后，如果回收掉

WeakHashMap 中的 key，會(huì)將 key 放入 queue 中，在 expungeStaleEntr

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

刪除掉，以達(dá)到同步。

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

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

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

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

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

}

所以，WeakHashMap 的數(shù)據(jù)結(jié)構(gòu)圖我也為你準(zhǔn)備好啦。

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

關(guān)于 WeakHashMap 需要注意兩點(diǎn)：

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

Hashtable

Hashtable 底層的存儲(chǔ)結(jié)構(gòu)是數(shù)組 + 鏈表，而它是一個(gè)線程安全的集合，但是因?yàn)檫@個(gè)線程安全，它就被淘汰掉了。

下面是 Hashtable 存儲(chǔ)元素時(shí)的數(shù)據(jù)結(jié)構(gòu)圖，它只會(huì)存在數(shù)組+鏈表，當(dāng)鏈表過長時(shí)，查詢的效率過低，而且會(huì)長時(shí)間鎖住 Hashtable。

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

HashTable 本質(zhì)上是 HashMap 的前輩，它被淘汰的原因也主要因?yàn)閮蓚€(gè)字：性能

HashTable 是一個(gè)線程安全的Map，它所有的方法都被加上了 synchronized 關(guān)鍵字，也是因?yàn)檫@個(gè)關(guān)鍵字，它注定成為了時(shí)代的棄兒。

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

HashTable 默認(rèn)長度為 11，負(fù)載因子為 0.75F，即元素個(gè)數(shù)達(dá)到數(shù)組長度的 75% 時(shí)，會(huì)進(jìn)行一次擴(kuò)容，每次擴(kuò)容為原來數(shù)組長度的 2 倍

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

Collection 集合體系詳解

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

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

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

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

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

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

Set 接口

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

在 Set 集合體系中，我們需要著重關(guān)注兩點(diǎn)：

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

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

AbstractSet 抽象類

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

所有的 Set 也應(yīng)該要有相同的 hashCode 和 equals 方法，所以使用抽象類把該方法重寫后，子類無需關(guān)心這兩個(gè)方法。

public abstract class AbstractSet<E> implements Set<E> {
// 判斷兩個(gè) set 是否相等
public booleanequals(Object o) {
if (o == this) { // 集合本身
return true;
} else if (!(o instanceof Set)) { // 集合不是 set
return false;
} else {
// 比較兩個(gè)集合的元素是否全部相同
}
}
// 計(jì)算所有元素的 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 是一個(gè)接口，它在 Set 的基礎(chǔ)上擴(kuò)展了排序的行為，所以所有實(shí)現(xiàn)它的子類都會(huì)擁有排序功能。

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 結(jié)尾的 Set
SortedSet<E> tailSet(E var1);
// 獲取首個(gè)元素
E first;
// 獲取最后一個(gè)元素
E last;
}

HashSet

HashSet 底層借助 HashMap 實(shí)現(xiàn)，我們可以觀察它的多個(gè)構(gòu)造方法，本質(zhì)上都是 new 一個(gè) HashMap

這也是這篇文章為什么先講解 Map 再講解 Set 的原因！先學(xué)習(xí) 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 就是一個(gè)靜態(tài)常量：使用 PRESENT 作為 HashMap 的

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

HashMap 的 value

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

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

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

LinkedHashSet

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

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

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

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

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

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

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

image.png

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

關(guān)于 LinkedHashSet 需要注意幾個(gè)地方：

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

TreeSet

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

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

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

TreeSet 應(yīng)用場景有很多，像在游戲里的玩家戰(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}]

對(duì) TreeSet 介紹了它的主要實(shí)現(xiàn)方式和應(yīng)用場景，有幾個(gè)值得注意的點(diǎn)。

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

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

List 接口

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

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

AbstractList 和 AbstractSequentialList

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

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

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

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

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

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

Vector

vector 在現(xiàn)在已經(jīng)是一種過時(shí)的集合了，包括繼承它的 Stack 集合也如此，它們被淘汰的原因都是因?yàn)樾阅艿拖隆?/p>

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

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

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

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

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

淘汰了。

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

Stack

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

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

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

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

ArrayDeque 的數(shù)據(jù)結(jié)構(gòu)是：數(shù)組，并提供頭尾指針下標(biāo)對(duì)數(shù)組元素進(jìn)行操作。本文也會(huì)講到哦，客官請(qǐng)繼續(xù)往看，莫著急！

ArrayList

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

關(guān)于 ArrayList 有幾個(gè)重要的點(diǎn)需要注意的：

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

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

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

LinkedList

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

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

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

優(yōu)勢：LinkedList 底層沒有擴(kuò)容機(jī)制，使用雙向鏈表存儲(chǔ)元素，所以插入和刪除元素效率較高，適用于頻繁操作元素的場景
劣勢：LinkedList 不具備隨機(jī)訪問的特點(diǎn)，查找某個(gè)元素只能從 head 或 tail 指針一個(gè)一個(gè)比較，所以查找中間的元素時(shí)效率很低
查找優(yōu)化：LinkedList 查找某個(gè)下標(biāo) index 的元素時(shí)做了優(yōu)化，若 index > (size / 2)，則從 head 往后查找，否則從 tail 開始往前查找，代碼如下所示：

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

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

LinkedList 集合最讓人關(guān)注的是它的鏈表結(jié)構(gòu)，但是我們同時(shí)也要注意它是一個(gè)雙端隊(duì)列型的集合。

Deque<Object> deque = new LinkedList<>;

Queue 接口

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

Queue 中提供了兩套增加、刪除元素的 API，當(dāng)插入或刪除元素失敗時(shí)，會(huì)有兩種不同的失敗處理策略。

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

add 和 offer 對(duì)比：

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

但是它們兩個(gè)方法在插入某些不合法的元素時(shí)都會(huì)拋出三個(gè)相同的異常。

remove 和 poll 對(duì)比：

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

get 和 peek 對(duì)比：

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

Deque 接口

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

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

AbstractQueue 抽象類

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

LinkedList

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

ArrayDeque

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

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

在文檔中作者寫到：ArrayDeque 作為棧時(shí)比 Stack 性能好，作為隊(duì)列時(shí)比 LinkedList 性能好

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

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

PriorityQueue

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

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

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

例如游戲中的VIP玩家與普通玩家，VIP 等級(jí)越高的玩家越先安排進(jìn)入服務(wù)器玩耍，減少玩家流失。

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 等級(jí)進(jìn)行降序排序
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 + "進(jìn)入游戲; " + "VIP等級(jí): " + 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í)行上面的代碼可以得到下面這種有趣的結(jié)果，可以看到氪金使人帶來快樂。

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

PriorityQueue 總結(jié)：

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

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

文末總結(jié)

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

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

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

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

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