摘要：概述集合類主要有大分支，及。不能保證元素的排列順序，順序有可能發(fā)生變化不是同步的集合元素可以是但只能放入一個(gè)是接口的唯一實(shí)現(xiàn)類，可以確保集合元素處于排序狀態(tài)。如果這兩個(gè)的通過比較返回，新添加的將覆蓋集合中原有的，但不會(huì)覆蓋。

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

https://upload-images.jianshu...

https://upload-images.jianshu...

Map體系如下：

https://upload-images.jianshu...

Collection體系如下
https://upload-images.jianshu...

1、List接口和Set接口都繼承自Collection接口，Collection接口繼承Iterable接口（Iterable有一個(gè)Iterator方法），即可迭代的；Collection只能存儲(chǔ)引用類型，并且是單個(gè)存儲(chǔ)；
2、List接口存儲(chǔ)元素特點(diǎn)：有序（存進(jìn)去什么順序取出來還什么順序），可重復(fù)；Set接口存儲(chǔ)元素特點(diǎn)：無序，不可重復(fù)
3、實(shí)現(xiàn)List接口主要的類包括ArrayList，LinkedList，Vector；實(shí)現(xiàn)Set的主要類包括：hashSet，另外還有一個(gè)TreeSet接口繼承它（自動(dòng)排序）

（1）ArrayList實(shí)現(xiàn)了List接口，是順序容器，即元素存放的數(shù)據(jù)與放進(jìn)去的順序相同，允許放入null元素，底層通過數(shù)組實(shí)現(xiàn)。除該類未實(shí)現(xiàn)同步外，其余跟Vector大致相同。每個(gè)ArrayList都有一個(gè)容量（capacity），表示底層數(shù)組的實(shí)際大小，容器內(nèi)存儲(chǔ)元素的個(gè)數(shù)不能多于當(dāng)前容量。當(dāng)向容器中添加元素時(shí)，如果容量不足，容器會(huì)自動(dòng)增大底層數(shù)組的大小。前面已經(jīng)提過，Java泛型只是編譯器提供的語(yǔ)法糖，所以這里的數(shù)組是一個(gè)Object數(shù)組，以便能夠容納任何類型的對(duì)象。

（2）特點(diǎn)：
A、查詢效率高，插入刪除效率低。查找的話，直接通過下標(biāo)可以查找到，所以效率快；插入刪除的話，由于插入（刪除）位置后面的元素都需要移動(dòng)，所以效率較差。
B、size(), isEmpty(), get(), set()方法均能在常數(shù)時(shí)間內(nèi)完成，add()方法的時(shí)間開銷跟插入位置有關(guān)，addAll()方法的時(shí)間開銷跟添加元素的個(gè)數(shù)成正比。其余方法大都是線性時(shí)間。
C、add(int index, E e)需要先對(duì)元素進(jìn)行移動(dòng)，然后完成插入操作，也就意味著該方法有著線性的時(shí)間復(fù)雜度。

https://upload-images.jianshu...

D、數(shù)組擴(kuò)容：
從上面介紹的向ArrayList中存儲(chǔ)元素的代碼中，我們看到，每當(dāng)向數(shù)組中添加元素時(shí)，都要去檢查添加后元素的個(gè)數(shù)是否會(huì)超出當(dāng)前數(shù)組的長(zhǎng)度，如果超出，數(shù)組將會(huì)進(jìn)行擴(kuò)容，以滿足添加數(shù)據(jù)的需求。數(shù)組擴(kuò)容通過一個(gè)公開的方法ensureCapacity(int minCapacity)來實(shí)現(xiàn)。在實(shí)際添加大量元素前，我也可以使用ensureCapacity來手動(dòng)增加ArrayList實(shí)例的容量，以減少遞增式再分配的數(shù)量。ArrayList默認(rèn)擴(kuò)容1.5倍

https://upload-images.jianshu...

E、在源碼中看到 int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 這里其實(shí)有點(diǎn)意思，數(shù)組的最大長(zhǎng)度為整數(shù)最大值減8。網(wǎng)上看到有人解釋： 數(shù)組作為一個(gè)對(duì)象，需要一定的內(nèi)存存儲(chǔ)對(duì)象頭信息，對(duì)象頭信息最大占用內(nèi)存不可超過8字節(jié)
參考：https://blog.csdn.net/Chinese...

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

https://upload-images.jianshu...

（4）非線程安全。為追求效率，ArrayList沒有實(shí)現(xiàn)同步（synchronized），如果需要多個(gè)線程并發(fā)訪問，用戶可以手動(dòng)同步，也可使用Vector替代。

（1）LinkedList同時(shí)實(shí)現(xiàn)了List接口和Deque接口，也就是說它既可以看作一個(gè)順序容器，又可以看作一個(gè)隊(duì)列（Queue），同時(shí)又可以看作一個(gè)棧（Stack）。這樣看來，LinkedList簡(jiǎn)直就是個(gè)全能冠軍。當(dāng)你需要使用?；蛘哧?duì)列時(shí)，可以考慮使用LinkedList，一方面是因?yàn)镴ava官方已經(jīng)聲明不建議使用Stack類，更遺憾的是，Java里根本沒有一個(gè)叫做Queue的類（它是個(gè)接口名字）。
（2）關(guān)于?；蜿?duì)列，現(xiàn)在的首選是ArrayDeque（雙端隊(duì)列），它有著比LinkedList（當(dāng)作?；蜿?duì)列使用時(shí)）有著更好的性能。
A、ArrayDeque內(nèi)部使用數(shù)組實(shí)現(xiàn)，并且是循環(huán)數(shù)組
B、LinkedList內(nèi)部使用鏈表實(shí)現(xiàn)
具體原因參考：https://blog.csdn.net/weixin_...
LinkedList底層通過雙向鏈表實(shí)現(xiàn)。LinkedList的實(shí)現(xiàn)方式?jīng)Q定了所有跟下標(biāo)相關(guān)的操作都是線性時(shí)間，而在首段或者末尾刪除元素只需要常數(shù)時(shí)間。為追求效率LinkedList沒有實(shí)現(xiàn)同步（synchronized），如果需要多個(gè)線程并發(fā)訪問，可以先采用Collections.synchronizedList()方法對(duì)其進(jìn)行包裝。

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

（1）和ArrayList一樣，底層使用數(shù)組實(shí)現(xiàn)
（2）vector是線程安全的，效率受到影響。
（3）vector在多線程環(huán)境下也會(huì)受到線程安全問題。比如說，一個(gè)線程去刪除i位置上的元素，另外一個(gè)線程去拿i位置上的元素，就會(huì)報(bào)異常。
（4）默認(rèn)長(zhǎng)度：10

Stack是繼承自Vector的，所以用法啊，線程安全什么的跟Vector都差不多，只是有幾個(gè)地方需要注意：

（1）add()和push()，stack是將最后一個(gè)element作為棧頂?shù)?，所以這兩個(gè)方法對(duì)stack而言是沒什么區(qū)別的，但是，它們的返回值不一樣，add()返回boolean，就是添加成功了沒有；push()返回的是你添加的元素。為了可讀性以及將它跟棧有一丟丟聯(lián)系，推薦使用push。

（2）peek()和pop()，這兩個(gè)方法都能得到棧頂元素，區(qū)別是peek()只是讀取，對(duì)原棧沒有什么影響；pop()，從字面上就能理解，出棧，所以原棧的棧頂元素就沒了。

ArrayList和Vector本質(zhì)都是用數(shù)組實(shí)現(xiàn)的，而LinkedList是用雙鏈表實(shí)現(xiàn)的；所以，Arraylist和Vector在查找效率上比較高，增刪效率比較低；LinkedList則正好相反。ArrayList是線程不安全的，Vector是線程安全的，效率肯定沒有ArrayList高了。實(shí)際中一般也不怎么用Vector,可以自己做線程同步，也可以用Collections配合ArrayList實(shí)現(xiàn)線程同步。

（1）查詢數(shù)據(jù)，適用ArrayList
（2）插入、刪除適用LinkedList
（3）保證數(shù)據(jù)安全用vector
（4）因?yàn)锳rrayList在內(nèi)存不夠的時(shí)候，默認(rèn)是原來的1.5倍，vector默認(rèn)是原來的2倍，因此，當(dāng)元素?cái)?shù)目越來越大，擴(kuò)展次數(shù)多的時(shí)候，使用vector比較有優(yōu)勢(shì)。

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

TreeSet是SortedSet接口的唯一實(shí)現(xiàn)類，TreeSet可以確保集合元素處于排序狀態(tài)。TreeSet支持兩種排序方式，自然排序和定制排序，其中自然排序?yàn)槟J(rèn)的排序方式。向TreeSet中加入的應(yīng)該是同一個(gè)類的對(duì)象。
TreeSet判斷兩個(gè)對(duì)象不相等的方式是兩個(gè)對(duì)象通過equals方法返回false，或者通過CompareTo方法比較沒有返回0
自然排序是根據(jù)集合元素的大小，以升序排列，如果要定制排序，應(yīng)該使用Comparator接口，實(shí)現(xiàn) int compare(T o1,T o2)方法。

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

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

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

https://upload-images.jianshu...

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

HashMap的主干是一個(gè)Entry數(shù)組。Entry是HashMap的基本組成單元，每一個(gè)Entry包含一個(gè)key-value鍵值對(duì)。

https://upload-images.jianshu...

簡(jiǎn)單來說，HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的，如果定位到的數(shù)組位置不含鏈表（當(dāng)前entry的next指向null）,那么對(duì)于查找，添加等操作很快，僅需一次尋址即可；如果定位到的數(shù)組包含鏈表，對(duì)于添加操作，其時(shí)間復(fù)雜度依然為O(1)，因?yàn)樽钚碌腅ntry會(huì)插入鏈表頭部，急需要簡(jiǎn)單改變引用鏈即可，而對(duì)于查找操作來講，此時(shí)就需要遍歷鏈表，通過key對(duì)象的equals方法逐一比對(duì)查找。所以，性能考慮，HashMap中的鏈表出現(xiàn)越少，性能才會(huì)越好。

將對(duì)向放入到HashMap或HashSet中時(shí)，有兩個(gè)方法需要特別關(guān)心：A、hashCode()和equals()。hashCode()方法決定了對(duì)象會(huì)被放到哪個(gè)bucket里，當(dāng)多個(gè)對(duì)象的哈希值沖突時(shí)，equals()方法決定了這些對(duì)象是否是“同一個(gè)對(duì)象”。所以，如果要將自定義的對(duì)象放入到HashMap或HashSet中，需要@Override hashCode()和equals()方法。
B、插入使用頭插法

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

https://upload-images.jianshu...

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

（4）HashMap的resize（rehash）
當(dāng)HashMap中的元素越來越多的時(shí)候，hash沖突的幾率也就越來越高，因?yàn)閿?shù)組的長(zhǎng)度是固定的。所以為了提高查詢的效率，就要對(duì)HashMap的數(shù)組進(jìn)行擴(kuò)容，數(shù)組擴(kuò)容這個(gè)操作也會(huì)出現(xiàn)在ArrayList中，這是一個(gè)常用的操作，而在HashMap數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去，這就是resize。
那么HashMap什么時(shí)候進(jìn)行擴(kuò)容呢？當(dāng)HashMap中的元素個(gè)數(shù)超過數(shù)組大小loadFactor時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值為0.75，這是一個(gè)折中的取值。也就是說，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)HashMap中元素個(gè)數(shù)超過160.75=12的時(shí)候，就把數(shù)組的大小擴(kuò)展為 2*16=32，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，而這是一個(gè)非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知HashMap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能。

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

HashMap 包含如下幾個(gè)構(gòu)造器：
HashMap()：構(gòu)建一個(gè)初始容量為 16，負(fù)載因子為 0.75 HashMap。
HashMap(int initialCapacity)：構(gòu)建一個(gè)初始容量為 initialCapacity，負(fù)載因子為 0.75 的 HashMap。
HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的負(fù)載因子創(chuàng)建一個(gè) HashMap。
HashMap的基礎(chǔ)構(gòu)造器HashMap(int initialCapacity, float loadFactor)帶有兩個(gè)參數(shù)，它們是初始容量initialCapacity和加載因子loadFactor。
initialCapacity：HashMap的最大容量，即為底層數(shù)組的長(zhǎng)度。
loadFactor：負(fù)載因子loadFactor定義為：散列表的實(shí)際元素?cái)?shù)目(n)/ 散列表的容量(m)。
負(fù)載因子衡量的是一個(gè)散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。對(duì)于使用鏈表法的散列表來說，查找一個(gè)元素的平均時(shí)間是O(1+a)，因此如果負(fù)載因子越大，對(duì)空間的利用更充分，哈希沖突多，然而后果是查找效率的降低；如果負(fù)載因子太小，哈希沖突少，那么散列表的數(shù)據(jù)將過于稀疏，對(duì)空間造成嚴(yán)重浪費(fèi)。
HashMap的實(shí)現(xiàn)中，通過threshold字段來判斷HashMap的最大容量：
threshold = (int)(capacity * loadFactor)
結(jié)合負(fù)載因子的定義公式可知，threshold就是在此loadFactor和capacity對(duì)應(yīng)下允許的最大元素?cái)?shù)目，超過這個(gè)數(shù)目就重新resize，以降低實(shí)際的負(fù)載因子。默認(rèn)的的負(fù)載因子0.75是對(duì)空間和時(shí)間效率的一個(gè)平衡選擇。當(dāng)容量超出此最大容量時(shí)， resize后的HashMap容量是容量的兩倍：

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

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

迭代器的快速失敗行為不能得到保證，一般來說，存在非同步的并發(fā)修改時(shí)，不可能作出任何堅(jiān)決的保證?？焖偈〉鞅M最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的做法是錯(cuò)誤的，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測(cè)程序錯(cuò)誤。

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

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

對(duì)內(nèi)部數(shù)據(jù)使用弱引用。如果內(nèi)部的鍵值對(duì)在其他地方?jīng)]有強(qiáng)引用引用著它，當(dāng)系統(tǒng)內(nèi)存不夠的情況下，系統(tǒng)會(huì)自動(dòng)清除該鍵值對(duì)?？梢宰鳛楹?jiǎn)單緩存表的解決方案（假如直接使用HashMap來存鍵值對(duì)，該鍵值對(duì)不會(huì)被GC回收）

（1）HashMap不是線程安全的；HashTable是線程安全的，其線程安全是通過Sychronized實(shí)現(xiàn)。由于上述原因，HashMap效率高于HashTable。
（2）HashMap的鍵可以為null（key和value都可以），HashTable不可以（key和value都不可以）。
（3）多線程環(huán)境下，通常也不是用HashTable，因?yàn)樾实?。HashMap配合Collections工具類使用實(shí)現(xiàn)線程安全。同時(shí)還有ConcurrentHashMap可以選擇，該類的線程安全是通過Lock的方式實(shí)現(xiàn)的，所以效率高于Hashtable。
（4）Hashtable多了一個(gè)elements()方法，返回一個(gè)Enumeration對(duì)象，但是不能用iterator遍歷。
（5）Hashtable數(shù)組默認(rèn)大小為11，Hashmap為16，且一定是2的指數(shù)。
（6）Hashtable基于Dictionary類，Hashmap基于AbstractMap類。、

HashMap是線程不安全的，ConcurrentHashMap是線程安全的。

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

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

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

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