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

image.png

集合框架總覽

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

image.png

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

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

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

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

Iterator Iterable ListIterator

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

首先來(lái)看Iterator接口：

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

提供的API接口含義如下：

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

在早期疗涉，遍歷集合的方式只有一種，通過(guò)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(); }
}

再來(lái)看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接口吟秩，所以實(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);
}

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

image.png

翻譯成代碼，就和一開(kāi)始的Iterator迭代器遍歷方式基本相同了椰憋。

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

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

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

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

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

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

ListIterator 存在于 List 集合之中仰禽，通過(guò)調(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> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    // 替換當(dāng)前下標(biāo)的元素,即訪問(wèn)過(guò)的最后一個(gè)元素
    void set(E e);
    void add(E e);
}

Map 和 Collection 接口

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

是不是聽(tīng)的一頭霧水哈哈哈奸忽，舉個(gè)例子你就懂了：HashSet底層利用了HashMap堕伪，TreeSet底層用了TreeMap，LinkedHashSet底層用了LinkedHashMap栗菜。

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

image.png

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ì)分為不同的種類(lèi)：

• SortedMap接口：該類(lèi)映射可以對(duì)<key, value>按照自己的規(guī)則進(jìn)行排序翘盖，具體實(shí)現(xiàn)有 TreeMap
• AbsractMap：它為子類(lèi)提供好一些通用的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);
• 查詢(xún)集合自身信息：size() / isEmpty()
• ···

在Collection接口下凹蜂，同樣會(huì)將集合細(xì)分為不同的種類(lèi)：

• Set接口：一個(gè)不允許存儲(chǔ)重復(fù)元素的無(wú)序集合馍驯，具體實(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兩類(lèi)集合

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

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

image.png

HashMap

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

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

image.png

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

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

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

LinkedHashMap

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

image.png

LinkedHashMap 是 HashMap 的子類(lèi)由缆，所以它具備 HashMap 的所有特點(diǎn)，其次猾蒂，它在 HashMap 的基礎(chǔ)上維護(hù)了一條雙向鏈表均唉，該鏈表存儲(chǔ)了所有元素，默認(rèn)元素的順序與插入順序一致肚菠。若accessOrder屬性為true舔箭，則遍歷順序按元素的訪問(wèn)次序進(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()中炉抒，感興趣的可翻看源碼，篇幅原因這里不再展開(kāi)稚叹。

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

• 指定accessOrder = true可以設(shè)定鏈表按照訪問(wèn)順序排列，通過(guò)提供的構(gòu)造器可以設(shè)定accessOrder

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

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

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

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

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

TreeMap

TreeMap 是 SortedMap 的子類(lèi)惰许，所以它具有排序功能。它是基于紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的史辙，每一個(gè)鍵值對(duì)<key, value>都是一個(gè)結(jié)點(diǎn)汹买，默認(rèn)情況下按照key自然排序，另一種是可以通過(guò)傳入定制的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ù)實(shí)現(xiàn)耙蔑，所以里面的存儲(chǔ)結(jié)構(gòu)可以理解成下面這幅圖哦见妒。

image.png

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

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

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

由于Integer類(lèi)實(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}

通過(guò)傳入新的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)：

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

WeakHashMap

WeakHashMap 日常開(kāi)發(fā)中比較少見(jiàn)，它是基于普通的Map實(shí)現(xiàn)的捌浩，而里面Entry中的鍵在每一次的垃圾回收都會(huì)被清除掉放刨，所以非常適合用于短暫訪問(wèn)、僅訪問(wèn)一次的元素嘉栓，緩存在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開(kāi)啟GC后馋辈，如果回收掉 WeakHashMap 中的 key，會(huì)將 key 放入queue 中倍谜，在expungeStaleEntries()中遍歷 queue迈螟，把 queue 中的所有key拿出來(lái)，并在 WeakHashMap 中刪除掉尔崔，以達(dá)到同步答毫。

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

再者，需要注意 WeakHashMap 底層存儲(chǔ)的元素的數(shù)據(jù)結(jié)構(gòu)是數(shù)組 + 鏈表季春，沒(méi)有紅黑樹(shù)哦洗搂，可以換一個(gè)角度想，如果還有紅黑樹(shù)，那干脆直接繼承 HashMap 耘拇，然后再擴(kuò)展就完事了嘛撵颊，然而它并沒(méi)有這樣做：

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

}

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

image.png

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

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

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

Hashtable

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

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

image.png

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

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

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

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

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

HashTable 所有的操作都是線(xiàn)程安全的先朦。

Collection 集合體系詳解

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

該集合下可以分為三大類(lèi)集合：List喳魏，Set和Queue

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

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

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

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

image.png

Set 接口

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

image.png

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

• 存入可變?cè)?/strong>時(shí)市咽，必須非常小心，因?yàn)槿我鈺r(shí)候元素狀態(tài)的改變都有可能使得 Set 內(nèi)部出現(xiàn)兩個(gè)相等的元素史隆，即 o1.equals(o2) = true魂务，所以一般不要更改存入 Set 中的元素，否則將會(huì)破壞了 equals() 的作用泌射！

• Set 的最大作用就是判重，在項(xiàng)目中最大的作用也是判重鬓照！

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

AbstractSet 抽象類(lèi)

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

所有的 Set 也應(yīng)該要有相同的 hashCode() 和 equals() 方法豺裆，所以使用抽象類(lèi)把該方法重寫(xiě)后拒秘，子類(lèi)無(wú)需關(guān)心這兩個(gè)方法号显。

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

public interface SortedSet<E> extends Set<E> {
    // 元素的比較器,決定元素的排列順序
    Comparator<? super E> comparator(); 
    // 獲取 [var1, var2] 之間的 set
    SortedSet<E> subSet(E var1, E var2); 
    // 獲取以 var1 開(kāi)頭的 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 {
    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 就是一個(gè)靜態(tài)常量：使用 PRESENT 作為 HashMap 的 value 值雳刺，使用HashSet的開(kāi)發(fā)者只需關(guān)注于需要插入的 key，屏蔽了 HashMap 的 value

image.png

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

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

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

LinkedHashSet

LinkedHashSet 的代碼少的可憐岸啡，不信我給你我粘出來(lái)

image.png

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

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

發(fā)現(xiàn)父類(lèi)中 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 也就更不在話(huà)下了碰纬。

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

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

TreeSet

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

image.png

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

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

TreeSet 應(yīng)用場(chǎ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 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}]

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

• TreeSet 的所有操作都會(huì)轉(zhuǎn)換為對(duì) TreeMap 的操作羡宙，TreeMap 采用紅黑樹(shù)實(shí)現(xiàn)狸剃，任意操作的平均時(shí)間復(fù)雜度為 O(logN)
• TreeSet 是一個(gè)線(xiàn)程不安全的集合
• 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)粘ｉ_(kāi)發(fā)中接觸的很多的一種集合類(lèi)型了。整個(gè) List 集合的組成部分如下圖

image.png

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

AbstractList 和 AbstractSequentialList

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

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

AbstractSequentialList 抽象類(lèi)繼承了 AbstractList潜慎，在原基礎(chǔ)上限制了訪問(wèn)元素的順序只能夠按照順序訪問(wèn)捡多，而不支持隨機(jī)訪問(wèn)，如果需要滿(mǎn)足隨機(jī)訪問(wèn)的特性铐炫，則繼承 AbstractList垒手。子類(lèi) LinkedList 使用鏈表實(shí)現(xiàn)，所以?xún)H能支持順序訪問(wèn)驳遵，顧繼承了 AbstractSequentialList而不是 AbstractList淫奔。

Vector

image.png

Vector 在現(xiàn)在已經(jīng)是一種過(guò)時(shí)的集合了，包括繼承它的 Stack 集合也如此堤结，它們被淘汰的原因都是因?yàn)?strong>性能低下唆迁。

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

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

在 JDK 1.2 時(shí)朴恳，Collection 家族出現(xiàn)了，它提供了大量高性能允蚣、適用於不同場(chǎng)合的集合于颖，而 Vector 也是其中一員，但由于 Vector 在每個(gè)方法上都加了鎖嚷兔，由于需要兼容許多老的項(xiàng)目森渐，很難在此基礎(chǔ)上優(yōu)化Vector了，所以漸漸地也就被歷史淘汰了冒晰。

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

Stack

image.png

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

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

取而代之的是后起之秀 Deque接口，其實(shí)現(xiàn)有 ArrayDeque煎娇，該數(shù)據(jù)結(jié)構(gòu)更加完善二庵、可靠性更好贪染，依靠隊(duì)列也可以實(shí)現(xiàn)LIFO的棧操作，所以?xún)?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)以故，它是線(xiàn)程不安全的集合蜗细；具有查詢(xún)快据德、在數(shù)組中間或頭部增刪慢的特點(diǎn)，所以它除了線(xiàn)程不安全這一點(diǎn)棘利，其余可以替代Vector，而且線(xiàn)程安全的 ArrayList 可以使用 CopyOnWriteArrayList代替 Vector水援。

image.png

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

• 具備隨機(jī)訪問(wèn)特點(diǎn)蜗元，訪問(wèn)元素的效率較高系冗，ArrayList 在頻繁插入掌敬、刪除集合元素的場(chǎng)景下效率較低。

• 底層數(shù)據(jù)結(jié)構(gòu)：ArrayList 底層使用數(shù)組作為存儲(chǔ)結(jié)構(gòu)楷兽，具備查找快芯杀、增刪慢的特點(diǎn)

• 線(xiàn)程安全性：ArrayList 是線(xiàn)程不安全的集合

• ArrayList 首次擴(kuò)容后的長(zhǎng)度為 10揭厚，調(diào)用 add() 時(shí)需要計(jì)算容器的最小容量『顺ィ可以看到如果數(shù)組elementData為空數(shù)組诚欠，會(huì)將最小容量設(shè)置為10顽染，之后會(huì)將數(shù)組長(zhǎng)度完成首次擴(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)該滿(mǎn)足的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

• 集合從第二次擴(kuò)容開(kāi)始左腔，數(shù)組長(zhǎng)度將擴(kuò)容為原來(lái)的 1.5 倍液样，即：newLength = oldLength * 1.5

image.png

LinkedList

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

image.png

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

image.png

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

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

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ù)組的后半部分則從尾開(kāi)始找
        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ì)列的特性箕母。

image.png

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

Deque<Object> deque = new LinkedList<>();   
復(fù)制代碼

Queue接口

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

image.png

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

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

add() 和 offer() 對(duì)比：

在隊(duì)列長(zhǎng)度大小確定的場(chǎng)景下，隊(duì)列放滿(mǎn)元素后毡鉴，添加下一個(gè)元素時(shí)猪瞬，add() 會(huì)拋出 IllegalStateException異常陈瘦，而 offer() 會(huì)返回 false 痊项。

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

image.png

remove() 和 poll() 對(duì)比：

在隊(duì)列為空的場(chǎng)景下咖驮， remove() 會(huì)拋出 NoSuchElementException異常游沿，而 poll() 則返回 null 。

get()和peek()對(duì)比：

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

Deque 接口

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

image.png

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

AbstractQueue 抽象類(lèi)

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

image.png

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ì)列，它是無(wú)界的雙端隊(duì)列昔园，最小的容量是8（JDK 1.8）默刚。在 JDK 11 看到它默認(rèn)容量已經(jīng)是 16了荤西。

image.png

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

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

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

個(gè)人觀點(diǎn)：鏈表的插入鼠锈、刪除操作涉及到指針的操作购笆，我個(gè)人認(rèn)為作者是覺(jué)得數(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)：

image.png

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

PriorityQueue 應(yīng)用場(chǎ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;
     public Student(String name, Integer score) {
         this.name = name;
         this.score = score;
     }
     @Override
     public int compareTo(Student o) {
         return this.score.compareTo(o.getScore());
     }
 }

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

image.png

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

PriorityQueue 總結(jié)：

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

• PriorityQueue 適用于元素按優(yōu)先級(jí)處理的業(yè)務(wù)場(chǎng)景，例如用戶(hù)在請(qǐng)求人工客服需要排隊(duì)時(shí)迄委，根據(jù)用戶(hù)的VIP等級(jí)進(jìn)行 插隊(duì) 處理，等級(jí)越高叙身，越先安排客服渔扎。

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

文末總結(jié)

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

• Collection 接口提供了整個(gè)集合框架最通用的增刪改查以及集合自身操作的抽象方法世剖，讓子類(lèi)去實(shí)現(xiàn)

• Set 接口決定了它的子類(lèi)都是無(wú)序定罢、無(wú)重復(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 接口決定了它的子類(lèi)都是有序稠屠、可存儲(chǔ)重復(fù)元素的集合峦睡，常見(jiàn)的實(shí)現(xiàn)有 ArrayList，LinkedList权埠，Vector

  • ArrayList 使用數(shù)組實(shí)現(xiàn)榨了，而 LinkedList 使用鏈表實(shí)現(xiàn)，所以它們兩個(gè)的使用場(chǎng)景幾乎是相反的攘蔽，頻繁查詢(xún)的場(chǎng)景使用 ArrayList龙屉，而頻繁插入刪除的場(chǎng)景最好使用 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ì)列的基本操作唆垃，子類(lèi)集合都會(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接口定義了該種集合類(lèi)型是以<key,value>鍵值對(duì)形式保存涡戳，其主要實(shí)現(xiàn)有：HashMap结蟋，TreeMap，LinkedHashMap渔彰，Hashtable

  • LinkedHashMap 底層多加了一條雙向鏈表嵌屎，設(shè)置accessOrder為true并重寫(xiě)方法則可以實(shí)現(xiàn)LRU緩存
  • TreeMap 底層采用數(shù)組+紅黑樹(shù)實(shí)現(xiàn)，集合內(nèi)的元素默認(rèn)按照自然排序恍涂，也可以傳入Comparator定制排序

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

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