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

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有一個Iterator方法），即可迭代的；Collection只能存儲引用類型，并且是單個存儲；
2、List接口存儲元素特點：有序（存進去什么順序取出來還什么順序），可重復(fù)；Set接口存儲元素特點：無序，不可重復(fù)
3、實現(xiàn)List接口主要的類包括ArrayList，LinkedList，Vector；實現(xiàn)Set的主要類包括：hashSet，另外還有一個TreeSet接口繼承它（自動排序）

（1）ArrayList實現(xiàn)了List接口，是順序容器，即元素存放的數(shù)據(jù)與放進去的順序相同，允許放入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)需要先對元素進行移動，然后完成插入操作，也就意味著該方法有著線性的時間復(fù)雜度。

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

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

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

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

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

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

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

（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)作?；蜿犃惺褂脮r）有著更好的性能。
A、ArrayDeque內(nèi)部使用數(shù)組實現(xiàn)，并且是循環(huán)數(shù)組
B、LinkedList內(nèi)部使用鏈表實現(xiàn)
具體原因參考：https://blog.csdn.net/weixin_...
LinkedList底層通過雙向鏈表實現(xiàn)。LinkedList的實現(xiàn)方式?jīng)Q定了所有跟下標(biāo)相關(guān)的操作都是線性時間，而在首段或者末尾刪除元素只需要常數(shù)時間。為追求效率LinkedList沒有實現(xiàn)同步（synchronized），如果需要多個線程并發(fā)訪問，可以先采用Collections.synchronizedList()方法對其進行包裝。

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

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

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

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

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

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

（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ù)目越來越大，擴展次數(shù)多的時候，使用vector比較有優(yōu)勢。

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

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ù)。但是同一個類的對象可以放入不同的實例 。

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

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

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

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

簡單來說，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。

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

（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ù)組進行擴容，數(shù)組擴容這個操作也會出現(xiàn)在ArrayList中，這是一個常用的操作，而在HashMap數(shù)組擴容之后，最消耗性能的點就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置，并放進去，這就是resize。
那么HashMap什么時候進行擴容呢？當(dāng)HashMap中的元素個數(shù)超過數(shù)組大小loadFactor時，就會進行數(shù)組擴容，loadFactor的默認(rèn)值為0.75，這是一個折中的取值。也就是說，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)HashMap中元素個數(shù)超過160.75=12的時候，就把數(shù)組的大小擴展為 2*16=32，即擴大一倍，然后重新計算每個元素在數(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ù)用來指定自動擴容的臨界值。當(dāng)entry的數(shù)量超過capacity*load_factor時，容器將自動擴容并重新哈希。對于插入元素較多的場景，將初始容量設(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機制
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)該僅用于檢測程序錯誤。

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

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

對內(nèi)部數(shù)據(jù)使用弱引用。如果內(nèi)部的鍵值對在其他地方?jīng)]有強引用引用著它，當(dāng)系統(tǒng)內(nèi)存不夠的情況下，系統(tǒng)會自動清除該鍵值對?？梢宰鳛楹唵尉彺姹淼慕鉀Q方案（假如直接使用HashMap來存鍵值對，該鍵值對不會被GC回收）

（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類。、

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ù)。