java collection api提供了一些列的類和接口來幫助我們存儲和管理對象集合。其實java中的集合工作起來像是一個數組，不過集合的大小是可以動态改變的，而且集合也提供了更多進階功能。有了javacollectionapi，我們就不需要自己編寫集合類了，大部分java集合類都位于<code>java.util</code>包裡面，還有一些和并發相關的集合類位于<code>java.util.concurrent</code>包中。下面就介紹一下java api 為我們提供的這些集合類。
java中的集合有兩大類，分别是：
collection類的集合可以了解為主要存放的是單個對象，而map類的集合主要存儲的是key-value類型的對象。這兩大類即可理所當然的對應着兩個接口，分别是<code>collection接口</code>和<code>map接口</code>，下面這幅圖列出了這兩個接口的繼承樹：
從上面這幅圖可以看到，collection接口又衍生了出三個分支，分别是：
而map則相對簡單，隻有一個分支。下面我們就詳細介紹java collection的每一個實作類。
注意：要把collection、collections區分開，collection是集合的一個接口，而collections是一個工具類，它提供了一些靜态方法來友善我們操作集合的執行個體，這兩個都位于<code>java.util</code>包中。
下圖是collection接口的源碼截圖，從接口中的抽象方法我們可以看出，它定義了一個通用集合常用的方法：
list接口繼承自collection接口，它的特點是其中的對象是有序的，并且每個對象都有一個唯一的index，我們可以通過這個index來搜尋某個元素，并且list中的對象允許重複，這類似于一個數組。對于list接口，java api提供了如下實作：
當然，在 <code>java.util.concurrent</code>包中也有一些實作，這些内容會在另一篇文章中詳細介紹。
arraylist是最常用的集合，其内部實作是一個數組，arraylist的大小是可以動态擴充的。對于元素的随機通路效率高，其通路的時間複雜度為<code>o(1)</code>，對于資料的插入與删除，從尾部操作效率高，時間複雜度和随機通路一樣是<code>o(1)</code>，若是從頭部操作則效率會比較低，因為從頭部插入或删除時需要移動後面所有元素，其時間複雜度為<code>o(n-i)</code>(n表示元素個數，i表示元素位置)。
linklist：從上圖可以看出，不但繼承了<code>list</code>接口，還繼承了<code>deque</code>接口（後面會介紹）。linklist是一個基于連結清單的資料結構，每個節點都儲存了上一個和下一個節點的指針。linklist對于随機通路效率是比較低的，因為它需要從頭開始索引，是以其時間複雜度為<code>o(i)</code>。但是對于元素的增删，linklist效率高，因為隻需要修改前後指針即可，其時間複雜度為<code>o(1)</code>。
vector：從vector和arraylist源碼截圖可以看出，它們繼承的接口完全一緻。是以，vector可以看做是一個線程安全的arraylist，它内部也是基于數組實作的，不過幾乎所有的集合操作都加了<code>synchronized</code>關鍵字。
stack：上面是stack類源碼截圖，我們看到stack類其實繼承自vector，stack隻是在vector的基礎上添加了幾個方法以提供棧（last in first out lifo）的特性。stack的特點是添加時新元素會被添加到頂部，移除時頂部的元素最先被移除。這種資料結構主要用作一些特殊資料加工流程，如語言編譯、xml解析等。
set和list接口一樣也是繼承自<code>collection</code>接口，同樣是對集合的一種實作，它們之間最大的差別是set中的對象不允許重複。對于<code>set</code>接口，java api提供了如下實作：
這些類的功能稍有不同，差別主要展現在對象的疊代的順序及插入、查找的效率上。
hashset的實作很簡單，其内部就是一個<code>hashmap</code>，不過它對元素的順序沒有保證。
linkedhashset的實作也很簡單，其内部用的是一個<code>linkedhashmap</code>。因為<code>linkedhashmap</code>内部維護了一個雙向連結清單以保持順序，是以<code>linkedhashset</code>的特點是它當中的元素是有序的，元素疊代的順序就是其插入的順序，元素的再次插入不會影響原有元素的順序。
treeset：從上圖的繼承關系可以看出，想要了解<code>treeset</code>就要先了解<code>navigableset</code>和<code>sortedset</code>接口。
sortedset接口
navigableset接口
從navigableset接口定義可以看到，它是sortedset的一個子接口，并且提供了一些導航方法，至于這些導航方法的含義大家可以檢視java doc。
是以，treeset的特點就是内部元素有序，并且有很多導航方法的實作。從第一部分java集合類概覽中我們知道，set有一個子接口<code>sortedset</code>，而sortedset又有一個子接口<code>navigableset</code>接口，java api對sortedset、navigableset接口的實作隻有一個，就是<code>treeset</code>。
queue接口繼承自<code>collection</code>接口，它也代表了一個有序的隊列，不過這個隊列最大的特點就是新插入的元素位于隊列的尾部，移除的對象位于隊列的頭部，這類似于超市中結賬的隊列。
我們通過第一節的java集合概覽已經知道，queue接口還有一個子接口deque，下面我們分别看一下javaapi對這兩個接口的定義：
queue接口：
deque接口：
從這兩個接口的定義我想大家已經看出些端倪，queue接口定義了一般隊列的操作方式，而deque則是一個雙端隊列。
對于<code>queue</code>接口，java api提供了兩個實作：
linkedlist：前面的list章節已經提到，它是一個标準隊列。
priorityqueue：隊列中的順序類似于treeset，取決于元素的排序規則，即元素對comparable接口的實作或者一個comparator比較器。
對于deque接口，出了linklist類之外還有一個實作：
arraydeque：從名稱可以看出，其内部實作是一個數組。
從第一部分java集合類概覽中我們知道，map不是繼承自collection接口，而是和collection接口出于并列的位置。是以，map的行為和上面介紹的collection的行為由很大不同。map的主要特點是它存放的元素為<code>key-value</code>對，我們看一下map接口的定義：
對于map接口，java api提供了如下實作：
其中，我們最常用到的是hashmap和treemap。
hashtable可以看做是hashmap的重量級實作，其中的大部分方法都加了synchronized關鍵字，是線程安全的。<code>hashtable</code>與hashmap的另一個差別是hashmap的<code>key-value</code>都允許為null，而<code>hashtable不</code>可以。
linkedhashmap也是一個hashmap，隻是内部維護了一個雙向連結清單以保持順序，<code>linkedhashset</code>内部實作就是用的linkedhashmap。
treemap中的key、value不但可以保持順序，類似于<code>treeset</code>和<code>priorityqueue</code>，treemap中key、value的疊代順序取決于它們各自的排序規則。