集合類型主要有3種：set(集)、list(清單)和map(映射)。
集合接口分為：Collection和Map，list、set實作了Collection接口
List總結：
可以重複，通過索引取出加入資料，順序與插入順序一緻，可以含有null元素
ArrayList——非線程安全:底層資料結構使數組結構array，查詢速度快，增删改慢，因為是一種類似數組的形式進行存儲，是以它的随機通路速度極快；
擴容機制
ArrayList的預設大小是10個元素，當容量不夠時，則需要擴容，而擴容的大小是原來的1.5倍(JDK1.8)
Vector——線程安全：底層是數組結構array，與ArrayList相同，查詢速度快，增删改慢；初始大小10，最大容量Integer.MAX_VALUE - 8。
擴容機制
擴容為原來的兩倍
LinkedList——非線程安全:底層使用連結清單結構，增删速度快，查詢稍慢；本質是一個雙向連結清單，由于還實作了Deque接口，故還可以用作雙端隊列
由于是連結清單結構，故隻要是周遊連結清單就需要使用ListIterator
采用了索引優化，可以根據index選擇從first或者last開始周遊。
ArrayList與Vector的差別：
1.如果集合中的元素數量大于目前集合數組的長度時，Vector的增長率是目前數組長度的100%，而ArryaList增長率為目前數組長度的50%。是以，如果集合中使用資料量比較大的資料，用Vector有一定優勢
2.線程同步方面，ArrayList是線程不同步，而Vector線程安全，但是因為其每個方法都加上了synchronized，是以在效率上小于ArrayList，btw，hashtable被淘汰也是這個原因
Set總結：
資料無序且唯一,實作類都不是線程安全的類，解決方案：Set set = Collections.sysnchronizedSet(Set對象);
HashSet：是Set接口(Set接口是繼承了Collection接口的)最常用的實作類，顧名思義，底層是用了哈希表(散列/hash)算法。其底層其實也是一個數組，存在的意義是提供查詢速度，插入的速度也是比較快，但是适用于少量資料的插入操作，
判斷兩個對象是否相等的規則：
1、equals比較為true；
2、hashCode值相同。要求：要求存在在哈希表中的對象元素都得重寫equals和hashCode方法。
LinkedHashSet：
繼承了HashSet類，是以它的底層用的也是哈希表的資料結構，但因為保持資料的先後添加順序，是以又加了連結清單結構，但因為多加了一種資料結構，是以效率較低，不建議使用，如果要求一個集合急要保證元素不重複，也需要記錄元素的先後添加順序，才選擇使用LinkedHashSet
TreeSet：Set接口的實作類，也擁有set接口的一般特性，但是不同的是他也實作了SortSet接口，它底層采用的是紅黑樹算法
(紅黑樹就是滿足一下紅黑性質的二叉搜尋樹：
①每個節點是黑色或者紅色
②根節點是黑色的
③每個葉子結點是黑色的
④如果一個節點是紅色的，那麼他的兩個子節點是黑色的
⑤對每個節點，從該節點到其所有的後代葉子結點的簡單路徑上，僅包含相同數目的黑色結點，
紅黑樹是許多“平衡”搜尋樹的一種，可以保證在最壞情況下的基本操作集合的時間複雜度為O(lgn)。
普及：二叉搜尋樹的性質：它或者是一棵空樹；或者是具有下列性質的二叉樹：若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；左、右子樹也分别為二叉排序樹。若子樹為空，查找不成功。)，要注意的是在TreeSet集合中隻能存儲相同類型對象的引用。
Map總結：
java的Map(映射)是一種把鍵對象和值對象進行映射的集合，其中每一個元素都包含了鍵對象和值對象，其中值對象也可以是Map類型的資料，是以，Map支援多級映射，Map中的鍵是唯一的，但值可以不唯一，Map集合有兩種實作，一種是利用哈希表來完成的叫做HashMap，它和HashSet都是利用哈希表來完成的，差別其實就是在哈希表的每個桶中，HashSet隻有key，而HashMap在每個key上挂了一個value；另一種就是TreeMap，它實作了SortMap接口，也就是使用了紅黑樹的資料結構，和TreeSet一樣也能實作自然排序和客戶化排序兩種排序方式，而哈希表不提供排序。
HashMap：
哈希表的實作原理中，先采用一個數組表示位桶，每個位桶的實作在1.8之前都是使用連結清單，但當每個位桶的資料較多的時候，連結清單查詢的效率就會不高，是以在1.8之後，先table翻倍，至64後，當位桶的資料超過門檻值(8)的時候，就會采用紅黑樹來存儲該位桶的資料(在門檻值之前還是使用連結清單來進行存儲)，是以，哈希表的實作包括數組+連結清單+紅黑樹，在使用哈希表的集合中我們都認為他們的增删改查操作的時間複雜度都是O(1)的，不過常數項很大，因為哈希函數在進行計算的代價比較高,HashMap和Hashtable類似，不同之處在于HashMap是非同步的，并且允許null，即null value和null key。，但是将HashMap視為Collection時(values()方法可傳回Collection)，其疊代子操作時間開銷和HashMap 的容量成比例。是以，如果疊代操作的性能相當重要的話，不要将HashMap的初始化容量設得過高，或者load factor過低。
TreeMap：
TreeMap 是一個有序的key-value集合，它是通過紅黑樹實作的。TreeMap 繼承于AbstractMap，是以它是一個Map，即一個key-value集合。TreeMap 實作了NavigableMap接口，意味着它支援一系列的導航方法。比如傳回有序的key集合。TreeMap 實作了Cloneable接口，意味着它能被克隆。TreeMap 實作了java.io.Serializable接口，意味着它支援序列化。
HashTable:
Hashtable繼承Map接口，實作一個key-value映射的哈希表。任何非空(non-null)的對象都可作為key或者value，線程安全，(這裡和hashmap做對比，hashmap的鍵值都可以為null,鍵不可以重複，值可以重複)。但由于基本都用synchronized上鎖，效率很低，現在已經不再使用。
ConcurrentHashMap——線程安全
内部結構
底層數組+連結清單實作，無論key還是value都不能為null，
在JDK1.8中則是采用數組+連結清單+紅黑樹的結構，其線程安全的保證則是通過synchronized+CAS的形式。
線程安全實作機制
在JDK1.7中采用分段鎖技術，将資料分成一段一段的存儲，然後給每一段資料配一把鎖，當一個線程占用鎖通路其中一個段資料的時候，其他段的資料也能被其他線程通路，能夠實作真正的并發通路。
而在JDK1.8中則直接參考了JDK1.8中HashMap的結構，采用數組+連結清單+紅黑樹的結構，而線程安全則是通過CAS來實作。而鎖的細粒度也從JDK1.7中的segment段降低為了JDK1.8中的每個Node，且由于紅黑樹的引入，使得在當連結清單節點過多的情況下能提高查詢效率
實作線程安全的方式是在修改資料時鎖住整個HashTable，效率低，ConcurrentHashMap做了相關優化
初始size為11，擴容：newsize = olesize*2+1