Java Collection API提供了一些列的類和接口來幫助我們存儲和管理對象集合。其實Java中的集合工作起來像是一個數(shù)組，不過集合的大小是可以動態(tài)改變的，而且集合也提供了更多高級功能。有了JavaCollectionAPI，我們就不需要自己編寫集合類了，大部分Java集合類都位于java.util包里面，還有一些和并發(fā)相關(guān)的集合類位于java.util.concurrent包中。下面就介紹一下Java API 為我們提供的這些集合類。

一、Java 集合概覽

Java中的集合有兩大類，分別是：

1. Collection
2. Map

Collection類的集合可以理解為主要存放的是單個對象，而Map類的集合主要存儲的是key-value類型的對象。這兩大類即可理所當然的對應(yīng)著兩個接口，分別是Collection接口和Map接口，下面這幅圖列出了這兩個接口的繼承樹：

從上面這幅圖可以看到，Collection接口又衍生了出三個分支，分別是：

1. List
2. Set
3. Queue

而Map則相對簡單，只有一個分支。下面我們就詳細介紹Java Collection的每一個實現(xiàn)類。

注意：要把Collection、Collections區(qū)分開，Collection是集合的一個接口，而Collections是一個工具類，它提供了一些靜態(tài)方法來方便我們操作集合的實例，這兩個都位于java.util包中。

二、先從Collection接口介紹

下圖是Collection接口的源碼截圖，從接口中的抽象方法我們可以看出，它定義了一個通用集合常用的方法：

- 增加刪除一個元素
- 判斷元素是否存在
- 獲得集合的大小
- 迭代一個集合

2.1 Collection的List接口

List接口繼承自Collection接口，它的特點是其中的對象是有序的，并且每個對象都有一個唯一的index，我們可以通過這個index來搜索某個元素，并且List中的對象允許重復(fù)，這類似于一個數(shù)組。對于List接口，Java API提供了如下實現(xiàn)：

- java.util.ArrayList
- java.util.LinkedList
- java.util.Vector
- java.util.Stack

當然，在 java.util.concurrent包中也有一些實現(xiàn)，這些內(nèi)容會在另一篇文章中詳細介紹。

ArrayList是最常用的集合，其內(nèi)部實現(xiàn)是一個數(shù)組，ArrayList的大小是可以動態(tài)擴充的。對于元素的隨機訪問效率高，其訪問的時間復(fù)雜度為O(1)，對于數(shù)據(jù)的插入與刪除，從尾部操作效率高，時間復(fù)雜度和隨機訪問一樣是O(1)，若是從頭部操作則效率會比較低，因為從頭部插入或刪除時需要移動后面所有元素，其時間復(fù)雜度為O(n-i)(n表示元素個數(shù)，i表示元素位置)。

LinkList：從上圖可以看出，不但繼承了List接口，還繼承了Deque接口（后面會介紹）。LinkList是一個基于鏈表的數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點都保存了上一個和下一個節(jié)點的指針。LinkList對于隨機訪問效率是比較低的，因為它需要從頭開始索引，所以其時間復(fù)雜度為O(i)。但是對于元素的增刪，LinkList效率高，因為只需要修改前后指針即可，其時間復(fù)雜度為O(1)。

Vector：從Vector和ArrayList源碼截圖可以看出，它們繼承的接口完全一致。所以，Vector可以看做是一個線程安全的ArrayList，它內(nèi)部也是基于數(shù)組實現(xiàn)的，不過幾乎所有的集合操作都加了synchronized關(guān)鍵字。

Stack：上面是Stack類源碼截圖，我們看到Stack類其實繼承自Vector，Stack只是在Vector的基礎(chǔ)上添加了幾個方法以提供棧（Last In First Out LIFO）的特性。Stack的特點是添加時新元素會被添加到頂部，移除時頂部的元素最先被移除。這種數(shù)據(jù)結(jié)構(gòu)主要用作一些特殊數(shù)據(jù)加工流程，如語言編譯、XML解析等。

2.2 Collection的Set接口

Set和List接口一樣也是繼承自Collection接口，同樣是對集合的一種實現(xiàn)，它們之間最大的區(qū)別是Set中的對象不允許重復(fù)。對于Set接口，Java API提供了如下實現(xiàn)：

- java.util.EnumSet
- java.util.HashSet
- java.util.LinkedHashSet
- java.util.TreeSet

這些類的功能稍有不同，區(qū)別主要體現(xiàn)在對象的迭代的順序及插入、查找的效率上。

HashSet的實現(xiàn)很簡單，其內(nèi)部就是一個HashMap，不過它對元素的順序沒有保證。

LinkedHashSet的實現(xiàn)也很簡單，其內(nèi)部用的是一個LinkedHashMap。因為LinkedHashMap內(nèi)部維護了一個雙向鏈表以保持順序，所以LinkedHashSet的特點是它當中的元素是有序的，元素迭代的順序就是其插入的順序，元素的再次插入不會影響原有元素的順序。

TreeSet：從上圖的繼承關(guān)系可以看出，想要了解TreeSet就要先了解NavigableSet和SortedSet接口。

SortedSet接口

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的特性之外它元素在內(nèi)部是有序的。它內(nèi)部元素的順序取決于元素的排序規(guī)則，即元素順序取決于元素對comparable接口的實現(xiàn)或者一個comparator比較器，關(guān)于comparable和comparator的區(qū)別，可以參考：http://chabaoo.cn/article/93973.htm

NavigableSet接口

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的一個子接口，并且提供了一些導(dǎo)航方法，至于這些導(dǎo)航方法的含義大家可以查看Java Doc。

所以，TreeSet的特點就是內(nèi)部元素有序，并且有很多導(dǎo)航方法的實現(xiàn)。從第一部分Java集合類概覽中我們知道，Set有一個子接口SortedSet，而SortedSet又有一個子接口NavigableSet接口，Java API對SortedSet、NavigableSet接口的實現(xiàn)只有一個，就是TreeSet。

2.3 Collection的Queue接口

Queue接口繼承自Collection接口，它也代表了一個有序的隊列，不過這個隊列最大的特點就是新插入的元素位于隊列的尾部，移除的對象位于隊列的頭部，這類似于超市中結(jié)賬的隊列。

我們通過第一節(jié)的Java集合概覽已經(jīng)知道，Queue接口還有一個子接口Deque，下面我們分別看一下JavaAPI對這兩個接口的定義：

Queue接口：

public interface Queue<E> extends Collection<E> {
  boolean add(E e);
  boolean offer(E e);
  E remove();
  E poll();
  E peek();
}

Deque接口：

public interface Deque<E> extends Queue<E> {
  void addFirst(E e);
  void addLast(E e);
  E removeFirst(); 
  E removeFirst();
}

從這兩個接口的定義我想大家已經(jīng)看出些端倪，Queue接口定義了一般隊列的操作方式，而Deque則是一個雙端隊列。

對于Queue接口，Java API提供了兩個實現(xiàn)：

- java.util.LinkedList（也實現(xiàn)了Deque接口）
- java.util.PriorityQueue

LinkedList：前面的List章節(jié)已經(jīng)提到，它是一個標準隊列。
PriorityQueue：隊列中的順序類似于TreeSet，取決于元素的排序規(guī)則，即元素對comparable接口的實現(xiàn)或者一個comparator比較器。

對于Deque接口，出了LinkList類之外還有一個實現(xiàn)：

- java.util.ArrayDeque

ArrayDeque：從名稱可以看出，其內(nèi)部實現(xiàn)是一個數(shù)組。

三、Java 集合之 Map

從第一部分Java集合類概覽中我們知道，Map不是繼承自Collection接口，而是和Collection接口出于并列的位置。所以，Map的行為和上面介紹的Collection的行為由很大不同。Map的主要特點是它存放的元素為key-value對，我們看一下Map接口的定義：

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提供了如下實現(xiàn)：

- 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的內(nèi)部實現(xiàn)非常值得研究，具體請參考HashMap內(nèi)部實現(xiàn)

HashTable可以看做是HashMap的重量級實現(xiàn)，其中的大部分方法都加了synchronized關(guān)鍵字，是線程安全的。HashTable與HashMap的另一個區(qū)別是HashMap的key-value都允許為null，而HashTable不可以。

LinkedHashMap也是一個HashMap，只是內(nèi)部維護了一個雙向鏈表以保持順序，LinkedHashSet內(nèi)部實現(xiàn)就是用的LinkedHashMap。

TreeMap中的key、value不但可以保持順序，類似于TreeSet和PriorityQueue，TreeMap中key、value的迭代順序取決于它們各自的排序規(guī)則。

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論