java collection api提供了一些列的類和接口來幫助我們存儲和管理對象集合。其實java中的集合工作起來像是一個數組，不過集合的大小是可以動態改變的，而且集合也提供了更多高級功能。有了javacollectionapi，我們就不需要自己編寫集合類了，大部分java集合類都位于java.util包里面，還有一些和并發相關的集合類位于java.util.concurrent包中。下面就介紹一下java api 為我們提供的這些集合類。
一、java 集合概覽
java中的集合有兩大類，分別是：
1. collection
2. map
collection類的集合可以理解為主要存放的是單個對象，而map類的集合主要存儲的是key-value類型的對象。這兩大類即可理所當然的對應著兩個接口，分別是collection接口和map接口，下面這幅圖列出了這兩個接口的繼承樹：
從上面這幅圖可以看到，collection接口又衍生了出三個分支，分別是：
1. list
2. set
3. queue
而map則相對簡單，只有一個分支。下面我們就詳細介紹java collection的每一個實現類。
注意：要把collection、collections區分開，collection是集合的一個接口，而collections是一個工具類，它提供了一些靜態方法來方便我們操作集合的實例，這兩個都位于java.util包中。
二、先從collection接口介紹
下圖是collection接口的源碼截圖，從接口中的抽象方法我們可以看出，它定義了一個通用集合常用的方法：
- 增加刪除一個元素
- 判斷元素是否存在
- 獲得集合的大小
- 迭代一個集合
2.1 collection的list接口
list接口繼承自collection接口，它的特點是其中的對象是有序的，并且每個對象都有一個唯一的index，我們可以通過這個index來搜索某個元素，并且list中的對象允許重復，這類似于一個數組。對于list接口，java api提供了如下實現：
- java.util.arraylist
- java.util.linkedlist
- java.util.vector
- java.util.stack
當然，在 java.util.concurrent包中也有一些實現，這些內容會在另一篇文章中詳細介紹。
arraylist是最常用的集合，其內部實現是一個數組，arraylist的大小是可以動態擴充的。對于元素的隨機訪問效率高，其訪問的時間復雜度為o(1)，對于數據的插入與刪除，從尾部操作效率高，時間復雜度和隨機訪問一樣是o(1)，若是從頭部操作則效率會比較低，因為從頭部插入或刪除時需要移動后面所有元素，其時間復雜度為o(n-i)(n表示元素個數，i表示元素位置)。
linklist：從上圖可以看出，不但繼承了list接口，還繼承了deque接口（后面會介紹）。linklist是一個基于鏈表的數據結構，每個節點都保存了上一個和下一個節點的指針。linklist對于隨機訪問效率是比較低的，因為它需要從頭開始索引，所以其時間復雜度為o(i)。但是對于元素的增刪，linklist效率高，因為只需要修改前后指針即可，其時間復雜度為o(1)。
vector：從vector和arraylist源碼截圖可以看出，它們繼承的接口完全一致。所以，vector可以看做是一個線程安全的arraylist，它內部也是基于數組實現的，不過幾乎所有的集合操作都加了synchronized關鍵字。
stack：上面是stack類源碼截圖，我們看到stack類其實繼承自vector，stack只是在vector的基礎上添加了幾個方法以提供棧（last in first out lifo）的特性。stack的特點是添加時新元素會被添加到頂部，移除時頂部的元素最先被移除。這種數據結構主要用作一些特殊數據加工流程，如語言編譯、xml解析等。
2.2 collection的set接口
set和list接口一樣也是繼承自collection接口，同樣是對集合的一種實現，它們之間最大的區別是set中的對象不允許重復。對于set接口，java api提供了如下實現：
- java.util.enumset
- java.util.hashset
- java.util.linkedhashset
- java.util.treeset
這些類的功能稍有不同，區別主要體現在對象的迭代的順序及插入、查找的效率上。
hashset的實現很簡單，其內部就是一個hashmap，不過它對元素的順序沒有保證。
linkedhashset的實現也很簡單，其內部用的是一個linkedhashmap。因為linkedhashmap內部維護了一個雙向鏈表以保持順序，所以linkedhashset的特點是它當中的元素是有序的，元素迭代的順序就是其插入的順序，元素的再次插入不會影響原有元素的順序。
treeset：從上圖的繼承關系可以看出，想要了解treeset就要先了解navigableset和sortedset接口。
sortedset接口
|
1
2
3
4
5
6
7
|
public interface sortedset<e> extends set<e> { comparator<? super e> comparator(); sortedset<e> subset(e fromelement, e toelement); sortedset<e> headset(e toelement); sortedset<e> tailset(e fromelement); e first(); } |
從上面接口定義看，sortedset接口是set的一個子接口，它除了有一般set的特性之外它元素在內部是有序的。它內部元素的順序取決于元素的排序規則，即元素順序取決于元素對comparable接口的實現或者一個comparator比較器，關于comparable和comparator的區別，可以參考：
navigableset接口
|
1
2
3
4
5
6
7
8
9
|
public interface navigableset<e> extends sortedset<e> { navigableset<e> descendingset(); iterator<e> descendingiterator(); sortedset<e> headset(e toelement); sortedset<e> tailset(e fromelement); sortedset<e> subset(e fromelement, e toelement); ceiling(), floor(), higher(), and lower() ...} |
從navigableset接口定義可以看到，它是sortedset的一個子接口，并且提供了一些導航方法，至于這些導航方法的含義大家可以查看java doc。
所以，treeset的特點就是內部元素有序，并且有很多導航方法的實現。從第一部分java集合類概覽中我們知道，set有一個子接口sortedset，而sortedset又有一個子接口navigableset接口，java api對sortedset、navigableset接口的實現只有一個，就是treeset。
2.3 collection的queue接口
queue接口繼承自collection接口，它也代表了一個有序的隊列，不過這個隊列最大的特點就是新插入的元素位于隊列的尾部，移除的對象位于隊列的頭部，這類似于超市中結賬的隊列。
我們通過第一節的java集合概覽已經知道，queue接口還有一個子接口deque，下面我們分別看一下javaapi對這兩個接口的定義：
queue接口：
|
1
2
3
4
5
6
7
|
public interface queue<e> extends collection<e> { boolean add(e e); boolean offer(e e); e remove(); e poll(); e peek();} |
deque接口：
|
1
2
3
4
5
6
|
public interface deque<e> extends queue<e> { void addfirst(e e); void addlast(e e); e removefirst(); e removefirst();} |
從這兩個接口的定義我想大家已經看出些端倪，queue接口定義了一般隊列的操作方式，而deque則是一個雙端隊列。
對于queue接口，java api提供了兩個實現：
- java.util.linkedlist（也實現了deque接口）
- java.util.priorityqueue
linkedlist：前面的list章節已經提到，它是一個標準隊列。
priorityqueue：隊列中的順序類似于treeset，取決于元素的排序規則，即元素對comparable接口的實現或者一個comparator比較器。
對于deque接口，出了linklist類之外還有一個實現：
- java.util.arraydeque
arraydeque：從名稱可以看出，其內部實現是一個數組。
三、java 集合之 map
從第一部分java集合類概覽中我們知道，map不是繼承自collection接口，而是和collection接口出于并列的位置。所以，map的行為和上面介紹的collection的行為由很大不同。map的主要特點是它存放的元素為key-value對，我們看一下map接口的定義：
|
1
2
3
4
5
6
7
8
|
public interface map<k,v> { v put(k key, v value); boolean containskey(object key); set<map.entry<k, v>> entryset(); int hashcode(); v get(object key); set<k> keyset(); ... ...} |
對于map接口，java api提供了如下實現：
- java.util.hashmap
- java.util.hashtable
- java.util.enummap
- java.util.identityhashmap
- java.util.linkedhashmap
- java.util.properties
- java.util.treemap
- java.util.weakhashmap
其中，我們最常用到的是hashmap和treemap。
hashmap中的key、value都是無序的。hashmap的內部實現非常值得研究，具體請參考hashmap內部實現
hashtable可以看做是hashmap的重量級實現，其中的大部分方法都加了synchronized關鍵字，是線程安全的。hashtable與hashmap的另一個區別是hashmap的key-value都允許為null，而hashtable不可以。
linkedhashmap也是一個hashmap，只是內部維護了一個雙向鏈表以保持順序，linkedhashset內部實現就是用的linkedhashmap。
treemap中的key、value不但可以保持順序，類似于treeset和priorityqueue，treemap中key、value的迭代順序取決于它們各自的排序規則。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/suifeng3051/article/details/49250819
