實際開發(fā)中皱埠，經(jīng)常用到的 ArrayList阁簸、LinkedList爬早、HashMap、LinkedHashMap 等集合類启妹，其實涵蓋了很多數(shù)據(jù)結(jié)構(gòu)和算法筛严，每個類可以說都是精華，今天和大家一起來梳理一下饶米！

一桨啃、摘要

在 Java 中车胡，集合大致可以分為兩大體系恨搓，一個是 Collection睛榄，另一個是 Map，都位于java.util包下耸采。

• Collection ：主要由 List析命、Set主卫、Queue 接口組成，List 代表有序鹃愤、重復(fù)的集合队秩；其中 Set 代表無序、不可重復(fù)的集合昼浦；Java 5 又增加了 Queue 體系集合馍资，代表隊列集合。

• Map：則代表具有映射關(guān)系的鍵值對集合关噪。

很多書籍將 List鸟蟹、Set、Queue使兔、Map 等能存放元素的接口體系建钥，也歸納為容器，因為他們可以存放元素虐沥！

集合和容器熊经，這兩者只是在概念上定義不同，比如ArrayList是一個存放數(shù)組的對象欲险，真正用起來并不會去關(guān)心這個東西到底是集合還是容器镐依，把東西用好才是關(guān)鍵！

java.util.Collection下的接口和繼承類關(guān)系簡易結(jié)構(gòu)圖：

file

java.util.Map下的接口和繼承類關(guān)系簡易結(jié)構(gòu)圖：

file

需要注意的是天试，網(wǎng)上有些集合架構(gòu)圖將 Map 畫成繼承自 Collection槐壳，實際上 Map 并沒有繼承 Collection，Map 是單獨的一個集合體系喜每，這點需要糾正一下务唐。

file

在 Java 集合框架中，數(shù)據(jù)結(jié)構(gòu)和算法可以說在里面體現(xiàn)的淋淋盡致带兜，這一點可以從我們之前對各個集合類的分析就可以看的出來枫笛，如動態(tài)數(shù)組、鏈表刚照、紅黑樹刑巧、Set、Map、隊列海诲、棧繁莹、堆等，基本上只要出去面試特幔，集合框架的話題一定不會少咨演！

下面我們就一起來看看各大數(shù)據(jù)結(jié)構(gòu)的具體實現(xiàn)！

二蚯斯、List

List 集合的特點：存取有序薄风，可以存儲重復(fù)的元素，可以用下標(biāo)進行元素的操作拍嵌。

List 集合中遭赂，各個類繼承結(jié)構(gòu)圖：

file

從圖中可以看出，List 主要實現(xiàn)類有：ArrayList横辆、LinkedList撇他、Vector、Stack狈蚤。

2.1困肩、ArrayList

ArrayList 是一個動態(tài)數(shù)組結(jié)構(gòu)，支持隨機存取脆侮，在指定的位置插入锌畸、刪除效率低（因為要移動數(shù)組元素）；如果內(nèi)部數(shù)組容量不足則自動擴容靖避，擴容系數(shù)為原來的1.5倍潭枣，因此當(dāng)數(shù)組很大時，效率較低幻捏。

file

當(dāng)然盆犁，插入刪除也不是效率非常低，在某些場景下粘咖，比如尾部插入蚣抗、刪除侈百，因為不需要移動數(shù)組元素瓮下，所以效率也很高哦！

ArrayList 是一個非線程安全的類钝域，在多線程環(huán)境下使用迭代器遍歷元素時讽坏，會報錯，拋ConcurrentModificationException異常例证！

因此路呜，如果想要在多線程環(huán)境下使用 ArrayList，建議直接使用并發(fā)包中的CopyOnWriteArrayList！

2.2胀葱、LinkedList

LinkedList 是一個雙向鏈表結(jié)構(gòu)漠秋，在任意位置插入、刪除都很方便抵屿，但是不支持隨機取值庆锦，每次都只能從一端開始遍歷，直到找到查詢的對象轧葛，然后返回搂抒；不過，它不像 ArrayList 那樣需要進行內(nèi)存拷貝尿扯，因此相對來說效率較高求晶，但是因為存在額外的前驅(qū)和后繼節(jié)點指針，因此占用的內(nèi)存比 ArrayList 多一些衷笋。

file

LinkedList 底層通過雙向鏈表實現(xiàn)芳杏，通過first和last引用分別指向鏈表的第一個和最后一個元素，注意這里沒有所謂的啞元（某個參數(shù)如果在子程序或函數(shù)中沒有用到辟宗，那就被稱為啞元）蚜锨，當(dāng)鏈表為空的時候first和last都指向null。

2.3慢蜓、Vector

Vector 也是一個動態(tài)數(shù)組結(jié)構(gòu)亚再，一個元老級別的類，早在 jdk1.1 就引入進來了晨抡，之后在 jdk1.2 里引進 ArrayList氛悬，ArrayList 可以說是 Vector 的一個迷你版，ArrayList 大部分的方法和 Vector 比較相似耘柱！

兩者不同的是如捅，Vector 中的方法都加了synchronized，保證操作是線程安全的调煎，但是效率低镜遣，而 ArrayList 所有的操作都是非線程安全的，執(zhí)行效率高士袄，但不安全悲关！

對于 Vector，雖然可以在多線程環(huán)境下使用娄柳，但是在迭代遍歷元素的時候依然會報錯寓辱，拋ConcurrentModificationException異常！

在 JDK 中 Vector 已經(jīng)屬于過時的類赤拒，官方不建議在程序中采用秫筏，如果想要在多線程環(huán)境下使用 Vector诱鞠，建議直接使用并發(fā)包中的CopyOnWriteArrayList！

2.4这敬、Stack

Stack 是 Vector 的一個子類航夺，本質(zhì)也是一個動態(tài)數(shù)組結(jié)構(gòu)，不同的是崔涂，它的數(shù)據(jù)結(jié)構(gòu)是先進后出敷存，取名叫棧！

不過堪伍，關(guān)于 Java 中 Stack 類锚烦，有很多的質(zhì)疑聲，棧更適合用隊列結(jié)構(gòu)來實現(xiàn)帝雇，這使得 Stack 在設(shè)計上不嚴(yán)謹(jǐn)涮俄，因此，官方推薦使用 Deque 下的類來是實現(xiàn)棧尸闸！

2.5彻亲、小結(jié)

List 接口各個實現(xiàn)類性能比較，如圖：

file

• ArrayList（動態(tài)數(shù)組結(jié)構(gòu)）吮廉，查詢快（隨意訪問或順序訪問）苞尝，增刪慢，但在末尾插入刪除宦芦，速度與LinkedList相差無幾宙址，但是是非線程安全的！

• LinkedList（雙向鏈表結(jié)構(gòu)）调卑，查詢慢抡砂，增刪快，也是非線程安全的恬涧！

• Vector（動態(tài)數(shù)組結(jié)構(gòu)）注益，因為方法加了同步鎖，相比 ArrayList 執(zhí)行都慢溯捆，基本不在使用丑搔，如果需要在多線程下使用，推薦使用并發(fā)容器中的CopyOnWriteArrayList來操作提揍，效率高啤月！

• Stack（棧結(jié)構(gòu)）繼承于Vector，數(shù)據(jù)是先進后出碳锈，基本不在使用顽冶，如果要實現(xiàn)棧，推薦使用 Deque 下的 ArrayDeque售碳，效率比 Stack 高！

三、Map

Map是一個雙列集合贸人，其中保存的是鍵值對间景，鍵要求保持唯一性，值可以重復(fù)艺智。

從上文中倘要，我們了解到 Map 集合結(jié)構(gòu)體系如下：

file

從圖中可以看出，Map 的實現(xiàn)類有 HashMap十拣、LinkedHashMap封拧、TreeMap、IdentityHashMap夭问、WeakHashMap泽西、Hashtable、Properties 等等缰趋。

3.1捧杉、HashMap

關(guān)于 HashMap，相信大家都不陌生秘血，是一個使用非常頻繁的容器類味抖，繼承自 AbstractMap，它允許鍵值都放入 null 元素灰粮，但是 key 不可重復(fù)仔涩。

因為使用的是哈希表存儲元素，所以輸入的數(shù)據(jù)與輸出的數(shù)據(jù)粘舟，順序基本不一致红柱，另外，HashMap 最多只允許一條記錄的 key 為 null蓖乘。

在 jdk1.7中锤悄，HashMap 主要是由 數(shù)組+ 單向鏈表 組成，當(dāng)發(fā)生 hash 沖突的時候嘉抒，就將沖突的元素放入鏈表中零聚。

file

從 jdk1.8開始，HashMap 主要是由** 數(shù)組+單向鏈表+紅黑樹** 實現(xiàn)些侍，相比 jdk1.7 而言隶症，多了一個紅黑樹實現(xiàn)。

當(dāng)鏈表長度超過 8 的時候岗宣，就將鏈表變成紅黑樹蚂会，如圖所示。

file

HashMap 的實現(xiàn)原理耗式，算是面試必問的一個話題胁住，詳細(xì)的實現(xiàn)過程趁猴，有興趣的朋友可以閱讀小編之前寫的文章《深入分析HashMap》！

HashMap 雖然很強大彪见，但是它是非線程安全的儡司，也就是說，如果在多線程環(huán)境下使用余指，可能因為程序自動擴容操作將單向鏈表轉(zhuǎn)變成了循環(huán)鏈表捕犬，在查詢遍歷元素的時候，造成程序死循環(huán)酵镜！此時 CPU 直接會飆到 100%碉碉！

如果我們想在多線程環(huán)境下使用 HashMap，其中一個推薦的解決辦法就是使用 java 并發(fā)包下的 ConcurrentHashMap 類淮韭！

在 JDK1.7 中垢粮，ConcurrentHashMap 類采用了分段鎖的思想，將 HashMap 進行切割缸濒，把 HashMap 中的哈希數(shù)組切分成小數(shù)組（Segment）足丢，每個小數(shù)組有 n 個 HashEntry 組成，其中 Segment 繼承自ReentrantLock（可重入鎖）庇配，從而實現(xiàn)并發(fā)控制斩跌！

file

從 jdk1.8 開始，ConcurrentHashMap 類取消了 Segment 分段鎖捞慌，采用 CAS + synchronized來保證并發(fā)安全耀鸦，數(shù)據(jù)結(jié)構(gòu)跟 jdk1.8 中 HashMap 結(jié)構(gòu)保持一致，都是** 數(shù)組 + 鏈表**（當(dāng)鏈表長度大于8時啸澡，鏈表結(jié)構(gòu)轉(zhuǎn)為紅黑樹）結(jié)構(gòu)袖订。

在這里插入圖片描述

jdk1.8 中的 ConcurrentHashMap 中 synchronized 只鎖定當(dāng)前鏈表或紅黑樹的首節(jié)點，只要節(jié)點 hash 不沖突嗅虏，就不會產(chǎn)生并發(fā)洛姑，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍！

詳細(xì)的實現(xiàn)原理皮服，可以參閱小編之前寫的文章《深入分析ConcurrentHashMap》楞艾！

3.2、LinkedHashMap

LinkedHashMap 繼承自 HashMap龄广，可以認(rèn)為是 HashMap + LinkedList硫眯，它既使用 HashMap 操作數(shù)據(jù)結(jié)構(gòu)，又使用 LinkedList 維護插入元素的先后順序择同，內(nèi)部采用雙向鏈表（doubly-linked list）的形式將所有元素（ entry ）連接起來两入。

從名字上，就可以看出 LinkedHashMap 是一個 LinkedList 和 HashMap 的混合體敲才，同時滿足 HashMap 和 LinkedList 的某些特性裹纳，可將 LinkedHashMap 看作采用 Linkedlist 增強的HashMap择葡。

file

雙向鏈表頭部插入的數(shù)據(jù)為鏈表的入口，迭代器遍歷方向是從鏈表的頭部開始到鏈表尾部結(jié)束痊夭，結(jié)構(gòu)圖如下：

file

這種結(jié)構(gòu)除了可以保持迭代的順序刁岸，還有一個好處：迭代 LinkedHashMap 時不需要像 HashMap 那樣遍歷整個 table脏里，而只需要直接遍歷 header 指向的雙向鏈表即可她我，也就是說 LinkedHashMap 的迭代時間就只跟 entry 的個數(shù)相關(guān)，而跟 table 的大小無關(guān)迫横。

LinkedHashMap 繼承了 HashMap番舆，所有大部分功能特性與 HashMap 基本相同，允許放入 key 為null的元素矾踱，也允許插入 value 為null的元素恨狈。

二者唯一的區(qū)別是 LinkedHashMap 在 HashMap 的基礎(chǔ)上，采用雙向鏈表（doubly-linked list）的形式將所有 entry 連接起來呛讲，這樣是為保證元素的迭代順序跟插入順序相同禾怠。

3.3、TreeMap

TreeMap實現(xiàn)了 SortedMap 接口贝搁，也就是說會按照 key 的大小順序?qū)?Map 中的元素進行排序吗氏，key 大小的評判可以通過其本身的自然順序（natural ordering），也可以通過構(gòu)造時傳入的比較器（Comparator）雷逆。

TreeMap 底層通過紅黑樹（Red-Black tree）實現(xiàn)弦讽，所以要了解 TreeMap 就必須對紅黑樹有一定的了解。

如下為紅黑樹圖：

file

紅黑樹是基于平衡二叉樹實現(xiàn)的膀哲，基于平衡二叉樹的實現(xiàn)還有 AVL 算法往产，也被稱為 AVL 樹，AVL 算法要求任何節(jié)點的兩棵子樹的高度差不大于1某宪，為了保持樹的高度差不大于1仿村，主要有2中調(diào)整方式：左旋轉(zhuǎn)、右旋轉(zhuǎn)兴喂。

繞某元素右旋轉(zhuǎn)蔼囊，圖解如下：

file

繞某元素右旋轉(zhuǎn)，圖解如下：

file

雖然 AVL 算法保證了樹高度平衡瞻想，查詢效率極高压真，但是也有缺陷，在刪除某個節(jié)點時蘑险，需要多次左旋轉(zhuǎn)或右旋轉(zhuǎn)調(diào)整滴肿，紅黑樹的出現(xiàn)就是為了解決盡可能少的調(diào)整，提高平衡二叉樹的整體性能佃迄！

那么對于一棵有效的紅黑樹泼差，主要有以下規(guī)則：

1贵少、每個節(jié)點要么是紅色，要么是黑色堆缘，但根節(jié)點永遠(yuǎn)是黑色的滔灶；

2、每個紅色節(jié)點的兩個子節(jié)點一定都是黑色吼肥；

3录平、紅色節(jié)點不能連續(xù)（也即是，紅色節(jié)點的孩子和父親都不能是紅色）缀皱；

4斗这、從任一節(jié)點到其子樹中每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點；

5啤斗、所有的葉節(jié)點都是是黑色的（注意這里說葉子節(jié)點其實是上圖中的 NIL 節(jié)點）表箭；

紅黑樹為了保證樹的基本平衡，調(diào)整也有類似 AVL 算法那樣的左旋轉(zhuǎn)钮莲、右旋轉(zhuǎn)操作免钻；同時，紅黑樹因為紅色節(jié)點不能連續(xù)崔拥，因此還增加一個顏色調(diào)整操作：節(jié)點顏色轉(zhuǎn)換极舔。

file

AVL雖然可以保證平衡二叉樹高度平衡，但是在刪除某個節(jié)點的時候握童，最多需要 n 次調(diào)整姆怪，也就是左旋轉(zhuǎn)、右旋轉(zhuǎn)澡绩；而紅黑樹稽揭，雖然也是基于平衡二叉樹實現(xiàn)，但是并不像 AVL 那樣高度平衡肥卡，而是基本平衡溪掀，在刪除某個節(jié)點的時候，至多 3 次調(diào)整步鉴，效率比 AVL 高揪胃！

紅黑樹，在插入的時候氛琢，與 AVL 一樣喊递，結(jié)點最多只需要2次旋轉(zhuǎn)；在查詢方面阳似，因為不是高度平衡骚勘，紅黑樹在查詢效率方面稍遜于 AVL，但是比二叉查找樹強很多！

就整體來看俏讹，紅黑樹的性能要好于 AVL当宴，只是實現(xiàn)稍微復(fù)雜了一些，有興趣的朋友可以參閱小編之前寫的文章《3分鐘看完關(guān)于樹的故事》泽疆！

3.4户矢、IdentityHashMap

IdentityHashMap 從名字上看，感覺表示唯一的 HashMap殉疼，然后并不是梯浪，別被它的名稱所欺騙哦。

IdentityHashMap 的數(shù)據(jù)結(jié)構(gòu)很簡單株依，底層實際就是一個 Object 數(shù)組驱证，在存儲上并沒有使用鏈表來存儲延窜，而是將 K 和 V 都存放在 Object 數(shù)組上恋腕。

file

當(dāng)添加元素的時候，會根據(jù) Key 計算得到散列位置逆瑞，如果發(fā)現(xiàn)該位置上已經(jīng)有改元素荠藤，直接進行新值替換；如果沒有获高，直接進行存放哈肖。當(dāng)元素個數(shù)達(dá)到一定閾值時，Object 數(shù)組會自動進行擴容處理念秧。

IdentityHashMap 的實現(xiàn)也不同于 HashMap淤井，雖然也是數(shù)組，不過 IdentityHashMap 中沒有用到鏈表摊趾，解決沖突的方式是計算下一個有效索引币狠，并且將數(shù)據(jù) key 和 value 緊挨著存入 map 中，即table[i]=key砾层、table[i+1]=value漩绵；

IdentityHashMap 允許key、value都為null肛炮，當(dāng)key為null的時候止吐，默認(rèn)會初始化一個Object對象作為key；

3.5侨糟、WeakHashMap

WeakHashMap 是 Map 體系中一個很特殊的成員碍扔，它的特殊之處在于 WeakHashMap 里的元素可能會被 GC 自動刪除，即使程序員沒有顯示調(diào)用 remove() 或者 clear() 方法秕重。

換言之不同，當(dāng)向 WeakHashMap 中添加元素的時候，再次遍歷獲取元素悲幅，可能發(fā)現(xiàn)它已經(jīng)不見了套鹅，我們來看看下面這個例子站蝠。

public static void main(String[] args) {
        Map weakHashMap = new WeakHashMap();
        //向weakHashMap中添加3個元素
        weakHashMap.put("key-1", "value-1");
        weakHashMap.put("key-2", "value-2");
        weakHashMap.put("key-3", "value-3");
        //輸出添加的元素
        System.out.println("數(shù)組長度："+weakHashMap.size() + "，輸出結(jié)果：" + weakHashMap);
        //主動觸發(fā)一次GC
        System.gc();
        //再輸出添加的元素
        System.out.println("數(shù)組長度："+weakHashMap.size() + "卓鹿，輸出結(jié)果：" + weakHashMap);
}

輸出結(jié)果：
數(shù)組長度：3菱魔，輸出結(jié)果：{key-2=value-2, key-1=value-1, key-0=value-0}
數(shù)組長度：3，輸出結(jié)果：{}
當(dāng)主動調(diào)用 GC 回收器的時候吟孙，再次查詢 WeakHashMap 里面的數(shù)據(jù)的時候澜倦，數(shù)據(jù)已經(jīng)被 GC 收集了，內(nèi)容為空杰妓。

這是因為 WeakHashMap 的 key 使用了弱引用類型藻治，在垃圾回收器線程掃描它所管轄的內(nèi)存區(qū)域的過程中，一旦發(fā)現(xiàn)了只具有弱引用的對象巷挥，不管當(dāng)前內(nèi)存空間足夠與否桩卵，都會回收它的內(nèi)存。

不過倍宾，由于垃圾回收器是一個優(yōu)先級很低的線程雏节，因此不一定會很快發(fā)現(xiàn)那些只具有弱引用的對象。

WeakHashMap 跟普通的 HashMap 不同高职，在存儲數(shù)據(jù)時钩乍，key 被設(shè)置為弱引用類型，而弱引用類型在 java 中怔锌，可能隨時被 jvm 的 gc 回收寥粹，所以再次通過獲取對象時，可能得到空值埃元，而 value 是在訪問數(shù)組內(nèi)容的時候涝涤，進行清除。

可能很多人覺得這樣做很奇葩亚情，其實不然妄痪，WeekHashMap 的這個特點特別適用于需要緩存的場景。

在緩存場景下楞件，由于系統(tǒng)內(nèi)存是有限的买优，不能緩存所有對象措拇，可以使用 WeekHashMap 進行緩存對象，即使緩存丟失，也可以通過重新計算得到沉噩，不會造成系統(tǒng)錯誤扯躺。

比較典型的例子舱痘，Tomcat 中的 ConcurrentCache 類就使用了 WeekHashMap 來實現(xiàn)數(shù)據(jù)緩存钓觉。

3.6、Hashtable

Hashtable 一個元老級的集合類，早在 JDK 1.0 就誕生了墓阀，而 HashMap 誕生于 JDK 1.2毡惜。

在實現(xiàn)上，HashMap 可以看作是 Hashtable 的一個迷你版斯撮，雖然二者的底層數(shù)據(jù)結(jié)構(gòu)都是 數(shù)組 + 鏈表 結(jié)構(gòu)经伙，具有查詢、插入勿锅、刪除快的特點帕膜，但是二者又有很多的不同。

• 雖然 HashMap 和 Hashtable 都實現(xiàn)了 Map 接口溢十，但 Hashtable 繼承于 Dictionary 類垮刹，而 HashMap 是繼承于 AbstractMap；

• HashMap 可以允許存在一個為 null 的 key 和任意個為 null 的 value张弛，但是 HashTable 中的 key 和 value 都不允許為 null荒典；

• Hashtable 的方法是同步的，因為在方法上加了 synchronized 同步鎖乌庶，而 HashMap 是非線程安全的种蝶；

雖然 Hashtable 是 HashMap 線程安全的一個版本，但是官方已經(jīng)不推薦使用 HashTable了瞒大，因為歷史遺留原因，并沒有移除此類搪桂，如果需要在線程安全的環(huán)境下使用 HashMap透敌，那么推薦使用 ConcurrentHashMap。在上文中已經(jīng)有所提到踢械！

3.7酗电、Properties

在 Java 中，其實還有一個非常重要的類 Properties内列，它繼承自 Hashtable撵术，主要用于讀取配置文件。

Properties 類是 java 工具包中非常重要的一個類话瞧，比如在實際開發(fā)中嫩与，有些變量，我們可以直接硬寫入到自定義的 java 枚舉類中交排。

但是有些變量划滋，在測試環(huán)境、預(yù)生產(chǎn)環(huán)境埃篓、生產(chǎn)環(huán)境处坪，變量所需要取的值都不一樣，這個時候，我們可以通過使用 properties 文件來加載程序需要的配置信息同窘，以達(dá)到一行代碼玄帕，多處環(huán)境都可以運行的效果！

比如想邦，最常見的 JDBC 數(shù)據(jù)源配置文件桨仿，properties文件以.properties作為后綴，文件內(nèi)容以鍵=值格式書寫案狠，左邊是變量名稱服傍，右邊是變量值，用#做注釋骂铁，新建一個jdbc.properties文件吹零，內(nèi)容如下：

file

Properties 繼承自 Hashtable，大部分方法都復(fù)用于 Hashtable拉庵，與 Hashtable 不同的是灿椅， Properties 中的 key 和 value 都是字符串。

實際開發(fā)中钞支，Properties 主要用于讀取配置文件茫蛹，尤其是在不同的環(huán)境下，變量值需要不一樣的情況烁挟，可以通過讀取配置文件來避免將變量值寫死在 java 的枚舉類中婴洼，以達(dá)到一行代碼，多處運行的目的撼嗓！

四柬采、Set

Set集合的特點：元素不重復(fù)，存取無序且警，無下標(biāo)粉捻。

Set 集合，在元素存儲方面斑芜，注重獨立無二的特性肩刃，如果某個元素在集合中已經(jīng)存在，不會存儲重復(fù)的元素杏头，同時盈包，集合存儲的是元素，不像 Map 集合那樣存儲的是鍵值對大州。

Set 集合中续语，各個類繼承結(jié)構(gòu)圖：

file

從圖中可以看出，Set 集合主要實現(xiàn)類有： HashSet厦画、LinkedHashSet 疮茄、TreeSet 滥朱、EnumSet（ RegularEnumSet、JumboEnumSet ）等等

4.1力试、HashSet

HashSet 是一個輸入輸出無序的集合徙邻，底層基于 HashMap 來實現(xiàn)，HashSet 利用 HashMap 中的 key 元素來存放元素畸裳，這一點我們可以從源碼上看出來缰犁，源碼定義如下：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable{
    // HashMap 變量
    private transient HashMap<E,Object> map;
    /**HashSet 初始化*/
    public HashSet() {
        //默認(rèn)實例化一個 HashMap
        map = new HashMap<>();
    }
}

因為 HashMap 允許 key 為空為null，所以 HashSet 也允許添加為null的元素怖糊。

4.2帅容、LinkedHashSet

LinkedHashSet 是一個輸入輸出有序的集合，繼承自 HashSet伍伤，但是底層基于 LinkedHashMap 來實現(xiàn)并徘。

LinkedHashSet 的源碼，類定義如下：

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    public LinkedHashSet() {
        //調(diào)用 HashSet 的方法
        super(16, .75f, true);
    }
}

查詢源碼扰魂，super調(diào)用的方法麦乞，源碼如下：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        //初始化一個 LinkedHashMap
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

LinkedHashSet 與 HashSet 相比，LinkedHashSet 保證了元素輸入輸出有序劝评！

4.3姐直、TreeSet

TreeSet 是一個排序的集合，實現(xiàn)了NavigableSet蒋畜、SortedSet声畏、Set接口，底層基于 TreeMap 來實現(xiàn)百侧。

TreeSet 利用 TreeMap 中的 key 元素來存放元素砰识，這一點我們也可以從源碼上看出來，閱讀源碼佣渴，類定義如下：

public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
    //TreeSet 使用NavigableMap接口作為變量
    private transient NavigableMap<E,Object> m;
    /**對象初始化*/
    public TreeSet() {
        //默認(rèn)實例化一個 TreeMap 對象
        this(new TreeMap<E,Object>());
    }
    //對象初始化調(diào)用的方法
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
}

new TreeSet<>()對象實例化的時候，表達(dá)的意思初斑，可以簡化為如下：

NavigableMap<E,Object> m = new TreeMap<E,Object>();

因為TreeMap實現(xiàn)了NavigableMap接口辛润，所以沒啥問題。

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
    ......
}

TreeSet 是一個排序的 Set 集合见秤，元素不可重復(fù)砂竖，底層基于 TreeMap 的 key 來實現(xiàn)，元素不可以為空鹃答，默認(rèn)按照自然排序來存放元素乎澄，也可以使用 Comparable和 Comparator 接口來比較大小，實現(xiàn)自定義排序测摔。

4.4置济、EnumSet

EnumSet 是一個與枚舉類型搭配使用的專用 Set 集合解恰，在 jdk1.5 中加入。

與 HashSet浙于、LinkedHashSet 护盈、TreeSet 不同的是，EnumSet 元素必須是Enum的類型羞酗，并且所有元素都必須來自同一個枚舉類型腐宋。

新建一個EnumEntity的枚舉類型，定義2個參數(shù)檀轨。

public enum EnumEntity {
    WOMAN,MAN;
}

創(chuàng)建一個 EnumSet胸竞，并將枚舉類型的元素全部添加進去！

//創(chuàng)建一個 EnumSet参萄，將EnumEntity 元素內(nèi)容添加到EnumSet中
EnumSet<EnumEntity> allSet = EnumSet.allOf(EnumEntity.class);
System.out.println(allSet);

輸出結(jié)果：
[WOMAN, MAN]

在 Java 中卫枝，EnumSet 是一個虛類，有2個實現(xiàn)類 RegularEnumSet拧揽、JumboEnumSet剃盾，不能顯式的實例化改類，EnumSet 會動態(tài)決定使用哪一個實現(xiàn)類淤袜，當(dāng)元素個數(shù)小于等于64的時候痒谴，使用 RegularEnumSet；大于 64的時候铡羡，使用JumboEnumSet類积蔚。

EnumSet 其內(nèi)部使用位向量實現(xiàn)，擁有極高的時間和空間性能烦周，如果元素是枚舉類型尽爆，推薦使用 EnumSet。

4.5读慎、小結(jié)

file

五漱贱、Queue

在 jdk1.5 中，新增了 Queue 接口夭委，代表一種隊列集合的實現(xiàn)幅狮。

Queue 接口是由大名鼎鼎的 Doug Lea 創(chuàng)建，中文名為道格·利株灸，翻開 JDK1.8 源代碼崇摄，可以將 Queue 接口旗下的實現(xiàn)類抽象成如下結(jié)構(gòu)圖：

file

從上圖可以看出，Queue 接口主要實現(xiàn)類有：ArrayDeque慌烧、LinkedList逐抑、PriorityQueue。

5.1屹蚊、ArrayDeque

ArrayQueue 是一個基于數(shù)組實現(xiàn)的雙端隊列厕氨，可以想象进每，在隊列中存在兩個指針，一個指向頭部腐巢，一個指向尾部品追，因此它具有FIFO隊列及LIFO棧的方法特性。

其中隊列（FIFO）表示先進先出冯丙，比如水管肉瓦，先進去的水先出來；棧（LIFO）表示先進后出胃惜，比如泞莉，手槍彈夾，最后進去的子彈船殉，最先出來鲫趁。

如下為 ArrayDeque 數(shù)據(jù)結(jié)構(gòu)圖，head 表示頭部指針利虫，tail表示尾部指針：

file

在上文中挨厚，我們也說到 Stack 也可以作為棧使用，但是 ArrayDeque 的效率要高于 Stack 類糠惫，并且功能也比 Stack 類豐富的多疫剃，當(dāng)需要使用棧時，Java 已不推薦使用 Stack硼讽，而是推薦使用更高效的 ArrayDeque巢价。

5.2、LinkedList

LinkedList 是一個基于鏈表實現(xiàn)的雙端隊列固阁，在上文中我們也說到 LinkedList 實現(xiàn)自 List壤躲，作為一個雙向鏈表時，增加或刪除元素的效率較高备燃，如果查找的話需要遍歷整個鏈表碉克，效率較低！

file

于此同時并齐，LinkedList 也實現(xiàn)了 Deque 接口棉胀，既可以作隊列使用也可以作為棧使用。

從上圖中可以得出冀膝，ArrayDeque 和 LinkedList 都是 Deque 接口的實現(xiàn)類，都具備既可以作為隊列霎挟，又可以作為棧來使用的特性窝剖，兩者主要區(qū)別在于底層數(shù)據(jù)結(jié)構(gòu)的不同。

ArrayDeque 底層數(shù)據(jù)結(jié)構(gòu)是以循環(huán)數(shù)組為基礎(chǔ)酥夭，而 LinkedList 底層數(shù)據(jù)結(jié)構(gòu)是以循環(huán)鏈表為基礎(chǔ)赐纱。

理論上脊奋，鏈表在添加、刪除方面性能高于數(shù)組結(jié)構(gòu)疙描，在查詢方面數(shù)組結(jié)構(gòu)性能高于鏈表結(jié)構(gòu)诚隙，但是對于數(shù)組結(jié)構(gòu)，如果不進行數(shù)組移動起胰，在添加方面效率也很高久又。

下面，分別以10萬條數(shù)據(jù)為基礎(chǔ)效五，通過添加地消、刪除，來測試兩者作為隊列畏妖、棧使用時所消耗的時間脉执，測試結(jié)果如下圖：

file

從數(shù)據(jù)上可以看出，在 10 萬條數(shù)據(jù)下戒劫，兩者性能都差不多半夷，當(dāng)達(dá)到 100 萬條、1000 萬條數(shù)據(jù)的時候迅细，兩者的差別就比較明顯了巫橄，ArrayDeque 無論是作為隊列還是作為棧使用，性能均高于 LinkedList 疯攒。

為什么 ArrayDeque 性能嗦随，在大數(shù)據(jù)量的時候，明顯高于 LinkedList敬尺？

個人分析枚尼，LinkedList 底層是以循環(huán)鏈表來實現(xiàn)的，每一個節(jié)點都有一個前驅(qū)砂吞、后繼的變量署恍，也就是說，每個節(jié)點上都存放有它上一個節(jié)點的指針和它下一個節(jié)點的指針蜻直，同時還包括它自己的元素盯质，每次插入或刪除節(jié)點時需要修改前驅(qū)、后繼節(jié)點變量概而，在同等的數(shù)據(jù)量情況下呼巷，鏈表的內(nèi)存開銷要明顯大于數(shù)組，同時因為 ArrayDeque 底層是數(shù)組結(jié)構(gòu)赎瑰，天然在查詢方面占優(yōu)勢王悍，在插入、刪除方面餐曼，只需要移動一下頭部或者尾部變量压储，時間復(fù)雜度是 O（1）鲜漩。

所以，在大數(shù)據(jù)量的時候集惋，LinkedList 的內(nèi)存開銷明顯大于 ArrayDeque孕似，在插入、刪除方面刮刑，都要頻發(fā)修改節(jié)點的前驅(qū)喉祭、后繼變量；而 ArrayDeque 在插入为朋、刪除方面依然保存高性能臂拓。

如果對于小數(shù)據(jù)量，ArrayDeque 和 LinkedList 在效率方面相差不大习寸，但是對于大數(shù)據(jù)量胶惰，推薦使用 ArrayDeque。

5.3霞溪、PriorityQueue

PriorityQueue 并沒有直接實現(xiàn) Queue接口孵滞，而是通過繼承 AbstractQueue 類來實現(xiàn) Queue 接口一些方法，在 Java 定義中鸯匹，PriorityQueue 是一個基于優(yōu)先級的無界優(yōu)先隊列坊饶。

通俗的說，添加到 PriorityQueue 隊列里面的元素都經(jīng)過了排序處理殴蓬，默認(rèn)按照自然順序匿级，也可以通過 Comparator 接口進行自定義排序。

優(yōu)先隊列的作用是保證每次取出的元素都是隊列中權(quán)值最小的染厅。

PriorityQueue 排序?qū)崿F(xiàn)與上文中說到的 TreeMap 類似痘绎。

file

在 Java 中 PriorityQueue 是一個使用數(shù)組結(jié)構(gòu)來存儲元素的優(yōu)先隊列，雖然它也實現(xiàn)了Queue接口肖粮，但是元素存取并不是先進先出孤页，而是通過一個二叉小頂堆實現(xiàn)的，默認(rèn)底層使用自然排序規(guī)則給插入的元素進行排序涩馆，也可以使用自定義比較器來實現(xiàn)排序行施，每次取出的元素都是隊列中權(quán)值最小的。

同時需要注意的是魂那，PriorityQueue 不能插入null蛾号，否則報空指針異常！

六涯雅、總結(jié)

以上主要是對 java 集合往期文章內(nèi)容做了一個簡單的總結(jié)须教，有興趣的可以參閱各篇詳細(xì)內(nèi)容，如果有理解不當(dāng)之處，歡迎指正轻腺！

轉(zhuǎn)自：https://blog.csdn.net/javageektech/article/details/104104086