業内經常說的一句話是不要重複造輪子，但是有時候，隻有自己造一個輪子了，才會深刻明白什麼樣的輪子适合山路，什麼樣的輪子适合平地！ 我将會持續更新java基礎知識，歡迎關注。
往期章節：
JAVA基礎第一章-初識java JAVA基礎第二章-java三大特性：封裝、繼承、多态 JAVA基礎第三章-類與對象、抽象類、接口
說起集合架構，很多面試官在面試初級javaer的時候也是很喜歡問的一個知識點
我們先上一張圖看看
從上面的關系圖中，我們可以看到從上往下分呢~最上面的是接口，中間是抽象類，最下面就是各個具體的實作類，這個在我們上一章節中說到的抽象類與接口之間的關系的時候有提到過。
再從左往右看呢，也是大緻分三塊，Iterator，Collection，Map 三個最頂級的接口，但是最主要的部分還是Collection，Map 2個接口，而Iterator更多的像是附加産品。
Collection
我們先看看Collection接口，從這個接口往下，他的子接口有List、Set、Queue。
List
List的具體實作類有 ArrayList、LinkedList，Vector。
ArrayList
顧名思義，是一個“數組型”的集合，對于數組，我們應該知道的是，數組在定義的時候就确定了大小，不可更改。那優點就是數組的元素是通過索引通路的，效率較高，因為數組是一塊連續的存儲空間。
是以呢，ArrayList 就是在數組的基礎上，增加了可以改變大小的接口（方法），如 add 、remove 等方法，友善我們去操作修改目前集合中的資料元素，當集合中新添加的資料超過了目前的存儲空間大小時
會申請一個新的存儲空間，然後将這些已有的資料拷貝過去，再添加新的資料 ，擴容後的集合的大小等于擴容前集合的1.5倍。
當我們删除一個元素的時候，會将目前被删除元素之後的元素統一向前移動一位，然後将最後的一位元素置為null，以便于gc回收。
是以，如果我們對一個ArrayList 有頻繁的增删操作，這樣對性能是一個極大的損耗。
ArrayList 的資料存儲結構示意圖如下：
假設上圖中每一個黃色的格子都代表一個ArrayList 的存儲空間
步驟1：在我們第一次調用add方法增加一個元素1的時候，那麼list會直接擴容為預設的大小10，我們也可以在調用ArrayList 構造函數的時候傳入參數，指定初始化空間大小；
步驟2：我們再繼續添加資料，直到添加到11時，會判斷目前的存儲空間放不下要增加的資料了，這個時候會繼續擴容，之後再放入資料11；
步驟3：在這一步，我們決定删除資料2，2的下标為1（數組的下标都是從0開始），也就是調用remove方法；
注意：當我們調用size方法擷取到的是實際的存儲的資料大小，而不是整個ArrayList 獲得的存儲空間大小，例如 ，步驟2中調用size方法傳回的會是11，而不是15。
LinkedList
從這個名字上，我們也可以大概知道，link是關聯的意思。LinkedList 和ArrayList 不同的一點是，他實作了Deque接口 這是一個雙向連結清單的接口。
我們先看下存儲結構示意圖：
如上圖中所示，每一個節點都是一個Node對象，其中每個Node都有三個屬性，item 實際存儲的資料元素，如上圖中的綠色格子，next和prev，這樣就構成了一個連結清單結構。
而要注意的是next 和prev 也是一個Node對象，而Node是LinkedList 中的靜态内部類。如下圖中代碼所示：
在這個連結清單中還存在2個屬性 first 和 last，分别用于存放整個集合連結清單中的頭和尾，如果隻有一個元素，那麼first 和last就指向同一個元素。
資料的添加
當我們在連結清單中添加一個元素的時候，最後一個元素的null位置會設定引用新的Node節點，然後新添加的節點的prev會指向前一個元素的位置
我們從LinkedList 源碼中做一些簡單的分析
如上所示，從 “Appends the specified element to the end of this list.” 這句注釋中，我們就大緻可以明白其意，當我們調用add方法增加元素的時候，預設是在末尾追加資料。
這個時候add方法中會調用linkLast方法，具體代碼如下：
上述代碼中，首先會将目前的last賦給l，然後建立一個Node對象，傳入新添加的資料，以及将目前集合中的last指派給新添加節點的prev屬性。
然後将建立的對象指派給last，之後再判斷最開始的last，也就是目前的l是否為null，如果是null，也就代表集合是空的，這是第一個元素，那麼就把它賦給frist，否則，那麼就說明已經有元素存在了，讓上一個元素的next指向目前建立的對象。
最後再進行調整大小等操作。
資料添加的操作示意圖如下：
資料的删除
下面我們再來看一下，LinkedList 的删除操作，也就是我們預設調用remove方法。
源碼如下所示：
同樣，從“Retrieves and removes the head (first element) of this list.”注釋中，我們大緻可以明白，大意是檢索并移除list頭部的元素。
在這個方法中直接調用了removeFirst方法，下面我們看一下removeFirst代碼：
如上所示，在這個代碼中，直接判斷是不是存在first，也就是集合是不是空的，不是那就繼續調用unlinkFirst方法，
unlinkFirst代碼如下所示：
如上所示，從“Unlinks non-null first node f”注釋中，可知，解開非空的第一個節點的關聯。首先将first節點的f.item 以及f.next設定為null，以便于gc回收。在将f.next置為null之前指派給了臨時的next。
然後判斷next是否為null，如果是，則說明後面沒有元素了，這是集合中的唯一一個元素，将last也設定為null；否則，将next中的prev設定為null。
資料删除操作示意圖如下：
是以呢，當我們對linkedList進行增删操作的時候隻需要對2個節點進行修改，而對其他節點沒有任何影響。
Vector
這個類和ArrayList基本相似，不同的點在于他是線程安全的，也就是在同一個時刻，隻能有一個線程通路Vector；另外Vector擴容不同于ArrayList，他每次擴容預設都是按2倍，而ArrayList是1.5倍。
ArrayList、LinkedList、 Vector三者之間的異同
ArrayList與LinkedList相比查詢速度快，增删速度慢。
是以如果隻是查詢，建議用前者，反之建議用後者，因為後者再增删的時候，隻需要修改2個節點的 prev和next ，而不存在複制目前已有的元素到新的存儲空間。
Vecor和ArrayList基本相似，差別是前者是線程安全的，後者不是。但是2個底層實作都是數組，LinkedList底層實作是連結清單。
集合的周遊
經常用到有三種方式，代碼示意如下：
for循環效率高于Iterator循環，高于foreach循環，因為我們都知道他們的底層實作都是數組，而for循環是通過下标查詢是最适合的周遊方式； 而foreach循環是在Iterator基礎上進行的，是以最慢。
另外，疊代器周遊方式， 适用于連續記憶體存儲方式，比如數組、 ArrayList，Vector。 缺點是隻能從頭開始周遊， 優點是可以一邊周遊一邊删除。
for循環這種方式周遊比較靈活，可以指定位置開始周遊。性能最高，但有一個缺點就是周遊過程中不允許删除元素，否則會抛ConcurrentModificationException。
（注:但是曾經發現在删除倒數第2個元素的時候，并不會抛出異常，詳見 記一次list循環删除元素的突發事件！）
Set
Set不允許包含相同的元素，如果試圖把兩個值相同元素加入同一個集合中，add方法傳回false。
Set判斷兩個對象相同不是使用==運算符，而是根據equals方法。也就是說，隻要兩個對象用equals方法比較傳回true，Set就不會再存儲第二個元素。
set的實作類有HashSet、TreeSet、LinkedHashSet
HashSet
不能保證元素的排列順序；不是線程安全的；集合元素可以是null,但隻能放入一個null，其他相同資料也隻能有一份存在；
對于HashSet我們要知道的是，他是依靠HashMap中的key去維護存放的資料，是以HashSet的這些特性都是和HashMap的key相關的。
hashSet預設構造函數代碼如下：
如上代碼所示，他是調用了HashMap的預設構造函數。
LinkedHashSet
LinkedHashSet和HashSet的差別是前者是有序的，也就是當你插入資料的時候會按順序排放，這樣我們周遊時就可以按照之前插入的順序擷取資料。
和HashSet相似也是在構造函數中調用了LinkedHashMap構造方法，代碼如下所示：
因為LinkedHashSet繼承了HashSet，是以他調用super，就是調用的HashSet的構造器，在HashSet中再調用了LinkedHashMap，代碼如下所示：
TreeSet
TreeSet是SortedSet接口的唯一實作類，TreeSet可以確定集合元素處于排序狀态。
TreeSet支援兩種排序方式，自然排序 和定制排序，其中自然排序為預設的排序方式。向TreeSet中加入的應該是同一個類的對象。
自然排序不用多說，那定制排序的意思就是，我們可以自己通過實作Comparator接口覆寫其中比較方法，然後按照我們意願進行排序，比如自然排序是升序，我們通過覆寫這個排序方法，可以修改成降序。
TreeSet帶比較器的構造函數代碼如下：
TreeSet預設構造函數代碼如下：
從上面的源碼注釋中，我們大緻可以明白，其意是構造一個新的空的樹形set，排序按照元素的自然順序排序，所有要插入到set中的元素必須實作Comparable接口，同時，這些元素還必須是互相可以比較的。
如果使用者嘗試添加一個string類型的資料到integer類型的set中，那麼會抛出ClassCastException 異常。
關于Map接口，我們将在下一章節中做一個詳細的分析
文中若有不正之處，歡迎批評指正！
give me the ball！