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

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接口存儲元素特點：有序（存進去什么順序取出來還什么順序），可重復；Set接口存儲元素特點：無序，不可重復
3、實現List接口主要的類包括ArrayList，LinkedList，Vector；實現Set的主要類包括：hashSet，另外還有一個TreeSet接口繼承它（自動排序）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）查詢數據，適用ArrayList
（2）插入、刪除適用LinkedList
（3）保證數據安全用vector
（4）因為ArrayList在內存不夠的時候，默認是原來的1.5倍，vector默認是原來的2倍，因此，當元素數目越來越大，擴展次數多的時候，使用vector比較有優勢。

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

TreeSet是SortedSet接口的唯一實現類，TreeSet可以確保集合元素處于排序狀態。TreeSet支持兩種排序方式，自然排序和定制排序，其中自然排序為默認的排序方式。向TreeSet中加入的應該是同一個類的對象。
TreeSet判斷兩個對象不相等的方式是兩個對象通過equals方法返回false，或者通過CompareTo方法比較沒有返回0
自然排序是根據集合元素的大小，以升序排列，如果要定制排序，應該使用Comparator接口，實現 int compare(T o1,T o2)方法。

（1）TreeSet 是二叉樹實現的,TreeSet中的數據是自動排好序的，不允許放入null值。

（2）HashSet 是哈希表實現的,HashSet中的數據是無序的，可以放入null，但只能放入一個null，兩者中的值都不能重復，就如數據庫中唯一約束。

（3）HashSet要求放入的對象必須實現HashCode()方法，放入的對象，是以hashcode碼作為標識的，而具有相同內容的 String對象，hashCode是一樣，所以放入的內容不能重復。但是同一個類的對象可以放入不同的實例 。

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

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

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

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

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

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

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

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

（3）put( )
當數組長度為2的n次冪的時候，不同的key算得得index相同的幾率較小，那么數據在數組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。
當程序試圖將一個key-value對放入HashMap中時，程序首先根據該 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）
當HashMap中的元素越來越多的時候，hash沖突的幾率也就越來越高，因為數組的長度是固定的。所以為了提高查詢的效率，就要對HashMap的數組進行擴容，數組擴容這個操作也會出現在ArrayList中，這是一個常用的操作，而在HashMap數組擴容之后，最消耗性能的點就出現了：原數組中的數據必須重新計算其在新數組中的位置，并放進去，這就是resize。
那么HashMap什么時候進行擴容呢？當HashMap中的元素個數超過數組大小loadFactor時，就會進行數組擴容，loadFactor的默認值為0.75，這是一個折中的取值。也就是說，默認情況下，數組大小為16，那么當HashMap中元素個數超過160.75=12的時候，就把數組的大小擴展為 2*16=32，即擴大一倍，然后重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知HashMap中元素的個數，那么預設元素的個數能夠有效的提高HashMap的性能。

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

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

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

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

迭代器的快速失敗行為不能得到保證，一般來說，存在非同步的并發修改時，不可能作出任何堅決的保證。快速失敗迭代器盡最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的做法是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用于檢測程序錯誤。

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

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

對內部數據使用弱引用。如果內部的鍵值對在其他地方沒有強引用引用著它，當系統內存不夠的情況下，系統會自動清除該鍵值對。可以作為簡單緩存表的解決方案（假如直接使用HashMap來存鍵值對，該鍵值對不會被GC回收）

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

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

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

（2）讀寫分離
讀操作get不需要加鎖，寫操作put需要在對應的segment加鎖。

（3）HashEntery 對象部分屬性設為final
降低處理鏈表時的復雜性，減少了鎖相關的操作。

（4）HashEntry 類的 value 域被聲明為 Volatile 型
保證了能被多個線程讀，而且不會讀到過期數據。