Java集合類主要有2大分支，Collection及Map濒募。
Collection體系如下：

image.png

image.png

Map體系如下：

image.png

** 補(bǔ)充圖**

image.png

1、List接口和Set接口都繼承自Collection接口晌姚，Collection接口繼承Iterable接口（Iterable有一個Iterator方法）挥唠，即可迭代的宝磨；Collection只能存儲引用類型唤锉，并且是單個存儲窿祥；
2晒衩、List接口存儲元素特點：有序（存進(jìn)去什么順序取出來還什么順序）浸遗，可重復(fù)跛锌；Set接口存儲元素特點：無序髓帽，不可重復(fù)
3郑藏、實現(xiàn)List接口主要的類包括ArrayList必盖，LinkedList歌粥，Vector拍埠；實現(xiàn)Set的主要類包括：hashSet枣购，另外還有一個TreeSet接口繼承它（自動排序）

List

1涩堤、ArrayList
（1）ArrayList實現(xiàn)了List接口定躏，是順序容器痊远，即元素存放的數(shù)據(jù)與放進(jìn)去的順序相同碧聪，允許放入null元素逞姿，底層通過數(shù)組實現(xiàn)滞造。除該類未實現(xiàn)同步外谒养，其余跟Vector大致相同买窟。每個ArrayList都有一個容量（capacity）瞳购，表示底層數(shù)組的實際大小学赛，容器內(nèi)存儲元素的個數(shù)不能多于當(dāng)前容量罢屈。當(dāng)向容器中添加元素時篇亭，如果容量不足，容器會自動增大底層數(shù)組的大小曼月。前面已經(jīng)提過哑芹，Java泛型只是編譯器提供的語法糖聪姿，所以這里的數(shù)組是一個Object數(shù)組末购，以便能夠容納任何類型的對象。

（2）特點：
A婴噩、查詢效率高，插入刪除效率低宅静。查找的話姨夹，直接通過下標(biāo)可以查找到洒忧，所以效率快；插入刪除的話熙侍，由于插入（刪除）位置后面的元素都需要移動榄鉴，所以效率較差。
B蛉抓、size(), isEmpty(), get(), set()方法均能在常數(shù)時間內(nèi)完成庆尘，add()方法的時間開銷跟插入位置有關(guān)，addAll()方法的時間開銷跟添加元素的個數(shù)成正比巷送。其余方法大都是線性時間驶忌。
C、add(int index, E e)需要先對元素進(jìn)行移動笑跛，然后完成插入操作几苍，也就意味著該方法有著線性的時間復(fù)雜度刽宪。

image.png

image.png

（3）數(shù)組默認(rèn)長度： 10，表示底層數(shù)組的實際大小摹菠。容器內(nèi)存儲元素的個數(shù)不能多于當(dāng)前容量。當(dāng)向容器中添加元素時洲押，如果容量不足，容器會自動增大底層數(shù)組的大小。前面已經(jīng)提過，Java泛型只是編譯器提供的語法糖，所以這里的數(shù)組是一個Object數(shù)組婴梧，以便能夠容納任何類型的對象。

image.png

（4）非線程安全。為追求效率所宰，ArrayList沒有實現(xiàn)同步（synchronized），如果需要多個線程并發(fā)訪問景描，用戶可以手動同步再扭，也可使用Vector替代。

2惭缰、LinkedList
（1）LinkedList同時實現(xiàn)了List接口和Deque接口紧憾，也就是說它既可以看作一個順序容器甸赃，又可以看作一個隊列（Queue），同時又可以看作一個棧（Stack）昌腰。這樣看來，LinkedList簡直就是個全能冠軍姜骡。當(dāng)你需要使用棧或者隊列時践叠，可以考慮使用LinkedList，一方面是因為Java官方已經(jīng)聲明不建議使用Stack類睹限，更遺憾的是秉颗，Java里根本沒有一個叫做Queue的類（它是個接口名字）。
（2）關(guān)于椃浯螅或隊列沐悦，現(xiàn)在的首選是ArrayDeque（雙端隊列）家浇，它有著比LinkedList（當(dāng)作椔簦或隊列使用時）有著更好的性能。
A晒杈、ArrayDeque內(nèi)部使用數(shù)組實現(xiàn)粪般，并且是循環(huán)數(shù)組
B、LinkedList內(nèi)部使用鏈表實現(xiàn)
具體原因參考：https://blog.csdn.net/weixin_35785121/article/details/52165457
LinkedList底層通過雙向鏈表實現(xiàn)。LinkedList的實現(xiàn)方式?jīng)Q定了所有跟下標(biāo)相關(guān)的操作都是線性時間蝠引，而在首段或者末尾刪除元素只需要常數(shù)時間。為追求效率LinkedList沒有實現(xiàn)同步（synchronized）豺鼻，如果需要多個線程并發(fā)訪問综液，可以先采用Collections.synchronizedList()方法對其進(jìn)行包裝。

（3）查詢效率比較低儒飒，插入谬莹、刪除效率比較高。查詢的時候桩了，每次都需要從頭開始查詢届良，查詢效率O(N)，但是插入（刪除）只需要影響到插入位置前后的元素圣猎，因此插入（刪除）效率較高

3士葫、Vector
（1）和ArrayList一樣，底層使用數(shù)組實現(xiàn)
（2）vector是線程安全的送悔，效率受到影響慢显。
（3）vector在多線程環(huán)境下也會受到線程安全問題。比如說欠啤，一個線程去刪除i位置上的元素荚藻，另外一個線程去拿i位置上的元素，就會報異常洁段。
（4）默認(rèn)長度：10

4应狱、Stack
Stack是繼承自Vector的，所以用法啊祠丝，線程安全什么的跟Vector都差不多疾呻，只是有幾個地方需要注意：

（1）add()和push()除嘹，stack是將最后一個element作為棧頂?shù)模赃@兩個方法對stack而言是沒什么區(qū)別的岸蜗，但是尉咕，它們的返回值不一樣，add()返回boolean璃岳，就是添加成功了沒有年缎；push()返回的是你添加的元素。為了可讀性以及將它跟棧有一丟丟聯(lián)系铃慷，推薦使用push单芜。

（2）peek()和pop()，這兩個方法都能得到棧頂元素犁柜，區(qū)別是peek()只是讀取洲鸠，對原棧沒有什么影響；pop()赁温，從字面上就能理解坛怪，出棧，所以原棧的棧頂元素就沒了股囊。

5袜匿、List、ArrayList , LinkedList , Vector的對比
ArrayList和Vector本質(zhì)都是用數(shù)組實現(xiàn)的稚疹，而LinkedList是用雙鏈表實現(xiàn)的居灯；所以，Arraylist和Vector在查找效率上比較高内狗，增刪效率比較低怪嫌；LinkedList則正好相反。ArrayList是線程不安全的柳沙，Vector是線程安全的岩灭，效率肯定沒有ArrayList高了。實際中一般也不怎么用Vector,可以自己做線程同步赂鲤，也可以用Collections配合ArrayList實現(xiàn)線程同步噪径。

6、適用場景
（1）查詢數(shù)據(jù)数初，適用ArrayList
（2）插入找爱、刪除適用LinkedList
（3）保證數(shù)據(jù)安全用vector
（4）因為ArrayList在內(nèi)存不夠的時候，默認(rèn)是原來的1.5倍泡孩，vector默認(rèn)是原來的2倍车摄，因此，當(dāng)元素數(shù)目越來越大，擴(kuò)展次數(shù)多的時候吮播，使用vector比較有優(yōu)勢变屁。

Set

1、HashSet
（1）不能保證元素的排列順序薄料，順序有可能發(fā)生變化
（2）不是同步的
（3）集合元素可以是null,但只能放入一個null

2敞贡、TreeSet
TreeSet是SortedSet接口的唯一實現(xiàn)類泵琳，TreeSet可以確保集合元素處于排序狀態(tài)摄职。TreeSet支持兩種排序方式，自然排序和定制排序获列，其中自然排序為默認(rèn)的排序方式谷市。向TreeSet中加入的應(yīng)該是同一個類的對象。
TreeSet判斷兩個對象不相等的方式是兩個對象通過equals方法返回false击孩，或者通過CompareTo方法比較沒有返回0
自然排序是根據(jù)集合元素的大小迫悠，以升序排列，如果要定制排序巩梢，應(yīng)該使用Comparator接口创泄，實現(xiàn) int compare(T o1,T o2)方法。

（1）TreeSet 是二叉樹實現(xiàn)的,TreeSet中的數(shù)據(jù)是自動排好序的括蝠，不允許放入null值鞠抑。

（2）HashSet 是哈希表實現(xiàn)的,HashSet中的數(shù)據(jù)是無序的，可以放入null忌警，但只能放入一個null搁拙，兩者中的值都不能重復(fù)，就如數(shù)據(jù)庫中唯一約束法绵。

（3）HashSet要求放入的對象必須實現(xiàn)HashCode()方法箕速，放入的對象，是以hashcode碼作為標(biāo)識的朋譬，而具有相同內(nèi)容的 String對象盐茎，hashCode是一樣，所以放入的內(nèi)容不能重復(fù)徙赢。但是同一個類的對象可以放入不同的實例 字柠。

Map

image.png

1、HashMap
（1）HashMap的結(jié)構(gòu)：HashMap采用了鏈地址法犀忱，也就是數(shù)組+鏈表的方式處理hash沖突（HashMap主要作用是解決hash沖突）募谎。

HashMap的主干是一個Entry數(shù)組。Entry是HashMap的基本組成單元阴汇，每一個Entry包含一個key-value鍵值對数冬。

image.png

簡單來說，HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體拐纱，鏈表則是主要為了解決哈希沖突而存在的铜异，如果定位到的數(shù)組位置不含鏈表（當(dāng)前entry的next指向null）,那么對于查找，添加等操作很快秸架，僅需一次尋址即可揍庄；如果定位到的數(shù)組包含鏈表，對于添加操作东抹，其時間復(fù)雜度依然為O(1)蚂子，因為最新的Entry會插入鏈表頭部，急需要簡單改變引用鏈即可缭黔，而對于查找操作來講食茎，此時就需要遍歷鏈表，通過key對象的equals方法逐一比對查找馏谨。所以别渔，性能考慮，HashMap中的鏈表出現(xiàn)越少惧互，性能才會越好哎媚。

將對向放入到HashMap或HashSet中時，有兩個方法需要特別關(guān)心：A喊儡、hashCode()和equals()拨与。hashCode()方法決定了對象會被放到哪個bucket里，當(dāng)多個對象的哈希值沖突時管宵，equals()方法決定了這些對象是否是“同一個對象”截珍。所以，如果要將自定義的對象放入到HashMap或HashSet中箩朴，需要@Override hashCode()和equals()方法岗喉。
B、插入使用頭插法

（2）get()
get(Object key)方法根據(jù)指定的key值返回對應(yīng)的value炸庞，該方法調(diào)用了getEntry(Object key)得到相應(yīng)的entry钱床，然后返回entry.getValue()。因此getEntry()是算法的核心埠居。
算法思想是首先通過hash()函數(shù)得到對應(yīng)bucket的下標(biāo)查牌，然后依次遍歷沖突鏈表，通過key.equals(k)方法來判斷是否是要找的那個entry滥壕。

image.png

（3）put( )
當(dāng)數(shù)組長度為2的n次冪的時候纸颜，不同的key算得得index相同的幾率較小，那么數(shù)據(jù)在數(shù)組上分布就比較均勻绎橘，也就是說碰撞的幾率小胁孙，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了涮较。
當(dāng)程序試圖將一個key-value對放入HashMap中時稠鼻，程序首先根據(jù)該 key 的 hashCode() 返回值決定該 Entry 的存儲位置：如果兩個 Entry 的 key 的 hashCode() 返回值相同，那它們的存儲位置相同狂票。如果這兩個 Entry 的 key 通過 equals 比較返回 true候齿，新添加 Entry 的 value 將覆蓋集合中原有 Entry 的 value，但key不會覆蓋闺属。如果這兩個 Entry 的 key 通過 equals 比較返回 false慌盯，新添加的 Entry 將與集合中原有 Entry 形成 Entry 鏈，而且新添加的 Entry 位于 Entry 鏈的頭部（頭插法屋剑，形成hash桶）

（4）HashMap的resize（rehash）
當(dāng)HashMap中的元素越來越多的時候润匙，hash沖突的幾率也就越來越高诗眨，因為數(shù)組的長度是固定的唉匾。所以為了提高查詢的效率，就要對HashMap的數(shù)組進(jìn)行擴(kuò)容匠楚，數(shù)組擴(kuò)容這個操作也會出現(xiàn)在ArrayList中巍膘，這是一個常用的操作，而在HashMap數(shù)組擴(kuò)容之后芋簿，最消耗性能的點就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置峡懈，并放進(jìn)去，這就是resize与斤。
那么HashMap什么時候進(jìn)行擴(kuò)容呢肪康？當(dāng)HashMap中的元素個數(shù)超過數(shù)組大小loadFactor時，就會進(jìn)行數(shù)組擴(kuò)容撩穿，loadFactor的默認(rèn)值為0.75磷支，這是一個折中的取值。也就是說食寡，默認(rèn)情況下雾狈，數(shù)組大小為16，那么當(dāng)HashMap中元素個數(shù)超過160.75=12的時候抵皱，就把數(shù)組的大小擴(kuò)展為 2*16=32善榛，即擴(kuò)大一倍，然后重新計算每個元素在數(shù)組中的位置呻畸，而這是一個非常消耗性能的操作移盆，所以如果我們已經(jīng)預(yù)知HashMap中元素的個數(shù)，那么預(yù)設(shè)元素的個數(shù)能夠有效的提高HashMap的性能伤为。

（5）HashMap的性能參數(shù)
有兩個參數(shù)可以影響HashMap的性能：初始容量（inital capacity咒循，初始為16）和負(fù)載系數(shù)（load factor，初始為0.75）。初始容量指定了初始table的大小剑鞍，負(fù)載系數(shù)用來指定自動擴(kuò)容的臨界值昨凡。當(dāng)entry的數(shù)量超過capacity*load_factor時，容器將自動擴(kuò)容并重新哈希蚁署。對于插入元素較多的場景便脊，將初始容量設(shè)大可以減少重新哈希的次數(shù)。

HashMap 包含如下幾個構(gòu)造器：
HashMap()：構(gòu)建一個初始容量為 16光戈，負(fù)載因子為 0.75 HashMap哪痰。
HashMap(int initialCapacity)：構(gòu)建一個初始容量為 initialCapacity，負(fù)載因子為 0.75 的 HashMap久妆。
HashMap(int initialCapacity, float loadFactor)：以指定初始容量晌杰、指定的負(fù)載因子創(chuàng)建一個 HashMap。
HashMap的基礎(chǔ)構(gòu)造器HashMap(int initialCapacity, float loadFactor)帶有兩個參數(shù)筷弦，它們是初始容量initialCapacity和加載因子loadFactor肋演。
initialCapacity：HashMap的最大容量，即為底層數(shù)組的長度烂琴。
loadFactor：負(fù)載因子loadFactor定義為：散列表的實際元素數(shù)目(n)/ 散列表的容量(m)爹殊。
負(fù)載因子衡量的是一個散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高奸绷，反之愈小梗夸。對于使用鏈表法的散列表來說，查找一個元素的平均時間是O(1+a)号醉，因此如果負(fù)載因子越大反症，對空間的利用更充分，哈希沖突多畔派，然而后果是查找效率的降低铅碍；如果負(fù)載因子太小，哈希沖突少父虑，那么散列表的數(shù)據(jù)將過于稀疏该酗，對空間造成嚴(yán)重浪費。
HashMap的實現(xiàn)中士嚎，通過threshold字段來判斷HashMap的最大容量：
threshold = (int)(capacity * loadFactor)
結(jié)合負(fù)載因子的定義公式可知呜魄，threshold就是在此loadFactor和capacity對應(yīng)下允許的最大元素數(shù)目，超過這個數(shù)目就重新resize莱衩，以降低實際的負(fù)載因子爵嗅。默認(rèn)的的負(fù)載因子0.75是對空間和時間效率的一個平衡選擇。當(dāng)容量超出此最大容量時笨蚁， resize后的HashMap容量是容量的兩倍：

（6）Fail-Fast機(jī)制
java.util.HashMap不是線程安全的睹晒，因此如果在使用迭代器的過程中有其他線程修改了map趟庄，那么將拋出ConcurrentModificationException，這就是所謂fail-fast策略伪很。
這一策略在源碼中的實現(xiàn)是通過modCount域戚啥，modCount顧名思義就是修改次數(shù)，對HashMap內(nèi)容的修改都將增加這個值锉试，那么在迭代器初始化過程中會將這個值賦給迭代器的expectedModCount猫十。

在迭代過程中，判斷modCount跟expectedModCount是否相等呆盖，如果不相等就表示已經(jīng)有其他線程修改了Map (注意到modCount聲明為volatile拖云，保證線程之間修改的可見性。)

迭代器的快速失敗行為不能得到保證应又，一般來說宙项，存在非同步的并發(fā)修改時，不可能作出任何堅決的保證株扛∮瓤穑快速失敗迭代器盡最大努力拋出 ConcurrentModificationException。因此席里，編寫依賴于此異常的程序的做法是錯誤的叔磷，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測程序錯誤。

2奖磁、LinkedHashMap
（1）繼承自HashMap
（2）能夠按插入的順序進(jìn)行遍歷。
（3）內(nèi)部使用雙向鏈表實現(xiàn)繁疤。默認(rèn)按插入元素的順序排序咖为，也可以更換成按照訪問順序排序。

3稠腊、TreeMap
紅黑樹算法的實現(xiàn)躁染，說下紅黑樹的幾種特征
（1）顏色特征：節(jié)點永遠(yuǎn)是紅色或者黑色
（2）根特征：根節(jié)點永遠(yuǎn)是黑色
（3）外部特征：擴(kuò)充外部節(jié)點都是 空的 黑色節(jié)點
（4）內(nèi)部特征：“紅色節(jié)點”的兩個子節(jié)點都是 黑色的
（5）深度特征：任何節(jié)點到其子孫外部節(jié)點的路徑，都包含相同數(shù)目的“黑色”節(jié)點架忌。

4吞彤、WeakHashMap
對內(nèi)部數(shù)據(jù)使用弱引用。如果內(nèi)部的鍵值對在其他地方?jīng)]有強(qiáng)引用引用著它叹放，當(dāng)系統(tǒng)內(nèi)存不夠的情況下饰恕，系統(tǒng)會自動清除該鍵值對【觯可以作為簡單緩存表的解決方案（假如直接使用HashMap來存鍵值對埋嵌，該鍵值對不會被GC回收）

5、HashMap和Hashtable對比
（1）HashMap不是線程安全的俱恶；HashTable是線程安全的雹嗦，其線程安全是通過Sychronized實現(xiàn)范舀。由于上述原因，HashMap效率高于HashTable了罪。
（2）HashMap的鍵可以為null（key和value都可以）锭环，HashTable不可以（key和value都不可以）。
（3）多線程環(huán)境下泊藕，通常也不是用HashTable田藐，因為效率低。HashMap配合Collections工具類使用實現(xiàn)線程安全吱七。同時還有ConcurrentHashMap可以選擇汽久，該類的線程安全是通過Lock的方式實現(xiàn)的，所以效率高于Hashtable踊餐。
（4）Hashtable多了一個elements()方法景醇，返回一個Enumeration對象，但是不能用iterator遍歷吝岭。
（5）Hashtable數(shù)組默認(rèn)大小為11三痰，Hashmap為16，且一定是2的指數(shù)窜管。
（6）Hashtable基于Dictionary類散劫，Hashmap基于AbstractMap類。幕帆、

6获搏、ConcurrentHashMap高并發(fā)原理總結(jié)
HashMap是線程不安全的，ConcurrentHashMap是線程安全的失乾。

（1）采用鎖分段技術(shù)
HashEntry為基本鍵值對存儲單元常熙，構(gòu)成HashEntry數(shù)組。Segement繼承自可重入鎖ReentrantLock碱茁，充當(dāng)了鎖角色裸卫。ConcurrentHashMap將數(shù)組分段，每段由一個segment以及它的鎖負(fù)責(zé)纽竣。減小鎖的粒度能讓并發(fā)性能更好墓贿。當(dāng)一個線程獲得一個segment鎖、能夠訪問其中一段數(shù)據(jù)的時候蜓氨，其他分段也能被其他線程正常訪問聋袋，是互不干擾的。

（2）讀寫分離
讀操作get不需要加鎖语盈，寫操作put需要在對應(yīng)的segment加鎖舱馅。

（3）HashEntery 對象部分屬性設(shè)為final
降低處理鏈表時的復(fù)雜性，減少了鎖相關(guān)的操作刀荒。

（4）HashEntry 類的 value 域被聲明為 Volatile 型
保證了能被多個線程讀代嗤，而且不會讀到過期數(shù)據(jù)棘钞。