JAVA 集合
在處理資料的過程中經常會需要一個容器來存儲某一類型的資料，Java 中的數組就是這樣一種容器。但 Java 中的數組有其局限性，定義後的數組長度不可變，超出數組長度後就不能再存放資料了。而很多時候我們并不知道資料到底有多少，是以就需要有不定長的容器來存放資料，這就是集合，Java 中的集合都采用了泛型實作，可以存入任何類型的對象資料。Java 中的數組：
Java 中的集合主要分為四類：
List 清單，有序，可重複Queue 隊列，有序，可重複Set 集合，不可重複Map 映射，無序，鍵唯一，值不唯一每種集合類型下都包含多個具體的實作類，如：
1. List 清單，有序、可重複
常用的 List 實作類有：ArrayList、LinkedList、Vector、Stack。
1.1 ArrayList 清單
ArrayList 數組清單，有序，可重複，内部是通過 Array 實作。初始化對象時，如果沒有傳大小，則清單的大小為 DEFAULT_CAPACITY 的預設值 10。當清單容量不夠時，繼續往清單中追加元素，則通過數組拷貝，對原數組進行擴容，擴容的方式為 "int newCapacity = oldCapacity + (oldCapacity >> 1)"，即新數組容量 newCapacity 為 10 + 10/2 = 15。如果一次性追加多個元素時比如 6 ，時候清單最小容量 minCapacity 需要 10 + 6 = 16，新的容量 newCapacity 小于最小容量 minCapacity 則新數組容量取最小容量值 newCapacity = minCapacity。
對數組清單進行插入、删除操作時都需要對數組進行拷貝并重排序。是以如果能知道大概存儲多少資料時，盡量初始化初始容量，提升性能。
1.2 LinkedList 雙向連結清單
LinkedList 是雙向連結清單，也即每個元素都有指向前後元素的指針。既然是連結清單那麼順序讀取的效率非常高，而随機讀取的效率較低。當随機擷取一個 index 位元素時，連結清單先比較 index 和連結清單長度 1/2 的大小，小于時從連結清單頭部查找元素，大于時就從連結清單尾部查找元素。
對比 ArrayList 如果随機讀取資料較多時使用 ArrayList 性能高，插入删除較多時使用 LinkedList 性能高。
1.3 Vector 向量，線程安全的清單
與 ArrayList 一樣也是通過數組實作的，不同的是 Vector 是線程安全的，也即同一時間下隻能有一個線程通路 Vector，線程安全的同時帶來了性能的耗損，是以一般都使用 ArrayList。Vector 的擴容也與 ArrayList 不同，可以設定擴容值，預設每次擴容原來的一倍。
1.4 Stack 棧，後進先出(LIFO)
Stack 繼承自 Vector 是以也是數組實作的，線程安全的棧。因為 Stack 繼承自 Vector 是以就擁有 Vector 中定義的方法，但作為棧資料類型，不建議使用 Vector 中與棧無關的方法，盡量隻用 Stack 中的定義的棧相關方法，這樣不會破壞棧資料類型。
1.5 ArrayQueue 數組隊列，先進後出(FIFO)
ArrayQueue 是數組實作的隊列，從隊尾加入資料，隻能隊頭删除資料，可随機讀取隊列資料。
2. Queue 隊列，有序、可重複
繼承自 Queue 的隊列有：ArrayDeque、LinkedList、PriorityQueue。
2.1 ArrayDeque 數組實作的雙端隊列
ArrayDeque 是隊列，但也可以作為棧使用，而且對比 Stack 更高效。作為雙端隊列那就可以在隊列兩端插入和删除元素。當追加元素超過容量限制時，則建立一個兩邊容量的新數組，并将原數組的内容拷貝到新數組中。
2.2 LinkedList 隊列也是雙向連結清單
上文 1.2 中已經提過，這裡就不贅述了。推薦使用 ArrayDeque。
2.3 PriorityQueue 優先隊列，數組實作的二叉樹
PriorityQueue 是一個完全二叉樹實作的小頂堆(任意一個非葉子節點的權值，都不大于其左右子節點的權值)。
3. Map 映射/字典，無序，鍵值對，鍵唯一
常用的 Map 實作有：HashMap、TreeMap、LinkedHashMap
3.1 HashMap 哈希映射/字典
HashMap就是key->value的鍵值對資料，key是唯一的，而且key和value都可以為null。HashMap和HashTable相似，HashTable實作了線程同步，在 "Object超類解析" 章節中簡單介紹過HashTable的資料存儲方式。HashMap 是個無序的字典，周遊時不保證元素順序。HashMap建立時預設會設定初始容量大小(預設16)，和裝載因子(預設0.75，擴充容量的閥值)，裝載因子=已存入元素個數/總容量大小。當然這兩個值也可以手動設定。
HashMap的資料存儲結構如下圖：
HashMap當插入一個資料時，先對key值做hash，用得到的值與容器的大小n減1做&運算得到桶的位置，即：i = (n - 1) & hash，i就是桶的位置。在桶中查找有無元素，沒有直接插入，有則比較元素key值是否相同，相同用新值替換。
桶的位置計算為什麼是 (n - 1) & hash？先看hash值的計算:
hash() 函數對 key 取值後傳回一個整數。又因為 HashMap 的容量 n 大小始終為 2 的幂(預設為 16)，那麼 n - 1 的二進制始終是最高位為 1，其它位為 0 的數，如：10...0，這個數與整數做 & 運算就得到 hash / n 的餘數，餘數的取值範圍在 0 ~ n-1，很巧妙的設計。相關源碼，這裡截取了部分：
3.2 TreeMap 紅黑樹實作的 key->value 容器，可排序
紅黑樹是一種自平衡二叉查找樹，具體檢視資料。
3.3 LinkedHashMap 連結清單映射/字典
LinkedHashMap 繼承自 HashMap 是以具有 HashMap 的所有特性。同時又實作了雙向連結清單的特性，保留了元素插入順序。
4. Set 集合，不可重複
常用的 Set 實作有：HashSet、LinkedHashSet、TreeSet、EnumSet。
4.1 HashSet 哈希集合
HashSet是基于HashMap實作的集合，對HashMap做了一些封裝。資料結構如圖：
與HashMap不同的是元素的儲存為連結清單形式，插入資料時周遊連結清單檢視是否有相同資料，有則傳回false，沒有傳回true。
4.2 LinkedHashSet 連結清單集合
繼承自 HashSet 與 LinkedHashMap 相似，是對 LinkedHashMap 的封裝。
4.3 TreeSet 紅黑樹集合
與 TreeMap 相似。是對 TreeMap 的封裝。
本文隻是對 Java 中的集合類做了個簡單介紹，詳細設計請檢視源碼了解詳情。