一、單列集合Collection

主要使用的是List和Set集合

1.1List接口

主要包括ArrayList、LinkedList、Vector（線程安全）、CopyOnWriteArrayList（線程安全）

1.1.1 ArrayList

ArrayList是線程不安全的，底層數據結構是可變數組，查詢快，增刪慢。
如果有參數擴容1.5倍；如果沒參數第一次擴容為10，第二次滿了擴容為1.5倍 擴容使用的是Arrays.copyOf()

1.1.2 LinkedList

LinkedList底層維護了一個雙向鏈表,沒有實現同步是線程不安全的底層數據結構是鏈表，查詢慢，增刪快。

1.1.3 Vector（線程安全）

Vector是線程同步的，即線程安全的，該類方法帶有synchronized，類似ArrayList，效率不如ArrayList
如果是無參 第一次擴容為10，第二次滿了擴容為2倍；如果指定大小，則每次按照兩倍擴容
Stack繼承Vector，也是線程安全的，支持push、pop、peek等操作

1.1.4 CopyOnWriteArrayList（線程安全）

（1）首先CopyOnWriteArrayList內部也是通過數組來實現的，在向CopyOnWriteArrayList中添加元素時，會復制一個新的數組，寫操作在新數組上進行，讀操作在原數組上進行
（2）并且，寫操作會加鎖，防止出現并發寫入丟失數據的問題
（3）寫操作結束后會把原數組指向新數組
（4）CopyOnWriteArrayList允許在寫操作時來讀取數據，大大提高了讀的性能，因此適合讀多寫少的應用場景，但是CopyOnWriteArrayList會比較占用內存，同時可能讀到的數據不是實時最新的數據，所以不適合實時性要求很高的場景

應用場景 （1）讀多寫少的場景：CopyOnWriteArrayList的讀操作不需要加鎖，因此非常適合在讀多寫少的場景中使用
（2）不需要實時更新的數據：CopyOnWriteArrayList讀取的數據可能不是最新的，因此他適合于不需要實時更新的數據

1.2 Set接口

主要包括HashSet、LinkedHashSet、CopyOnWriteArraySet
主要特點：
1）無序(添加和取出的順序不一致)，取出的順序雖然不是添加的順序，但是它的順序是固定的。
2）不允許有重復元素;可以存放null,最多包含一個null，重復add返回false
3）沒有索引，故不能使用索引的方法來獲取元素

1.2.1 HashSet

實現了set接口，本質上底層是一個HashMap
主要是hashCode和equals方法

HashSet底層數據結構是哈希表，因此具有很好的存取和查找性能。
哈希表：一個元素為鏈表的數組，綜合了鏈表（存儲速度快）和數組（查詢速度快）的優點。
1）使用HashSet添加一個元素時，會先得到hash值，然后轉成—>索引值
2）找到存儲數據表table，看這個索引位置是否已經存放的有元素。
3）沒有則直接加入，如果有，則調用equals方法進行比較
4）在Java8中，如果一條鏈表的元素個數達到TREEIFY_THRESHOLD (默認是8)，并且table的大小 >= MIN_TREEIFY_CAPACITY (默認是64)，就會進行樹化(紅黑樹),這樣又大大提高了查找的效率。

1.2.2 LinkedHashSet

1）在LinkedHashSet中維護了一個hash表和雙向鏈表(LinkedHashSet有head和tail)
2）每一個節點有before和after屬性，這樣可以形成雙向鏈表
3）在添加一個元素時，先求hash值，再求索引，確定該元素在table的位置，然后將添加的元素加入到雙向鏈表
4）遍歷LinkedHashSet，插入順序和遍歷順序一致

1.2.3 CopyOnWriteArraySet

每次調用CopyOnWriteArraySet的add方法的時候，其底層是基于CopyOnWriteArrayList的addIfAbsent方法的，
每次在addIfAbsent方法中都要對數組進行遍歷，所以CopyOnWriteArraySet的性能低于CopyOnWriteArrayList

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
//CopyOnWriteArraySet底層是基于CopyOnWriteArrayList的private final CopyOnWriteArrayList<E> al;
//add方法底層調用的還是CopyOnWriteArrayList的addIfAbsent方法public boolean add(E e) {return al.addIfAbsent(e);}

二、雙列集合Map

特點：

鍵值對映射關系

一個鍵對應一個值

鍵不能重復，值可以重復

元素存取無序

集合的遍歷（待補充代碼）

方法一：
1. 獲取所有鍵的集合。用keySet()方法實現
2. 遍歷鍵的集合，獲取到每一個鍵。用增強for實現  
3. 根據鍵去找值。用get(Object key)方法實現方法二：
1. 獲取所有鍵值對對象的集合：Set<Map.Entry<K,V>> entrySet()
2. 遍歷鍵值對對象的集合，得到每一個鍵值對對象：用增強for實現，得到每一個Map.Entry
3. 根據鍵值對對象獲取鍵和值：用getKey()得到鍵；用getValue()得到值

2.1 hashMap

HashMap首先還是會創建一個默認長度為16，默認加載因子為0.75的數組；
然后再利用put方式，就可以添加數據了，put方法的底層會先創建一個Entry對象，Entry對象里面記錄的就是要添加的鍵和值，然后利用鍵來計算哈希值，跟值無關，然后再計算出元素在數組中應存儲的位置的索引，如果該位置為null，直接添加，如果該位置不為null，它會調用equals方法比較鍵的屬性值，如果鍵的值相同，那么元素就會被覆蓋；如果比較完后不一樣，則會添加新的Entry對象；
JDK8，如果計算出來的索引相同，且鍵不一致，那么就會直接掛在當前值的下面；
此外，當鏈表長度超過8，且數組長度大于等于64的時候，鏈表就會自動轉成紅黑樹
如果鍵存儲的是自定義對象需要重寫hashCode和equals方法，值存儲不需要重寫

2.2 hashTable（線程安全）

HashTable線程安全 （他的每一個方法都加了鎖，適用于多線程并發的環境）
HashTable默認的初始大小為11 每次擴充為2n+1 加載因子0.75

2.3 LinkedHashMap

雙向鏈表
由鍵決定:
有序、不重復、無素引。
有序:保證存儲和取出的順序一致
原理:底層數據結構是依然哈希表，只是每個鍵值對元素又額外的多了一個雙鏈表的機制記錄存儲的順序

2.4 ConcurrentHashMap（線程安全）

可以理解為hashMap的升級版本，在ConcurrentHashMap中，無論是讀操作還是寫操作都能保證很高的性能：在進行讀操作時(幾乎)不需要加鎖，而在寫操作時通過鎖分段技術只對所操作的段加鎖而不影響客戶端對其它段的訪問。特別地，在理想狀態下，ConcurrentHashMap 可以支持 16 個線程執行并發寫操作（如果并發級別設為16），及任意數量線程的讀操作。
通過鎖分段技術保證并發環境下的寫操作；
通過 HashEntry的不變性、Volatile變量的內存可見性和加鎖重讀機制保證高效、安全的讀操作；
通過不加鎖和加鎖兩種方案控制跨段操作的的安全性。

2.5 TreeMap

TreeMap底層是紅黑樹結構 增刪改查性能較好
不重復 無索引 可排序
依賴自然排序或者比較器排序,對鍵進行排序
如果鍵存儲的是自定義對象,需要實現Comparable接口或者在創建TreeMap對象時候給出比較器排序規則