Java 容器類的選擇

韓慶安 珠海世紀鼎利科技股份有限公司

關鍵字：Java 容器類

Java 容器類有兩個基本的上層接口Collection 和Map，在兩種上層接口的基礎上，衍生了一系列的子接口以及其實現類。

Collection，獨立元素的序列，這些元素都服從一條或多條規則。List、Set 都是Collection 的一種，List 強調順序，而Set 不能有重復元素。Map 是鍵值對類型，允許用戶通過鍵來查找對象。Hash 表允許使用另一個對象來查找某個對象。所有實現Collection 接口的類都必須提供兩個標準的構造函數：無參數的構造函數用于創建一個空的Collection，有一個Collection 參數的構造函數用于創建一個新的Collection，這個新的Collection 與傳入的Collection 有相同的元素。后一個構造函數允許用戶復制一個Collection。

List 是有序的Collection，使用此接口能夠精確的控制每個元素插入的位置。用戶能夠使用索引來訪問List 中的元素，除了具有Collection 接口必備的iterator()方法外，List 還提供一個listIterator()方法，返回一個ListIterator 接口，和標準的Iterator接口相比，ListIterator 多了一些add()之類的方法，允許添加，刪除，設定元素，還能向前或向后遍歷。

實現List 接口的常用類有LinkedList，ArrayList 和Vector。

ArrayList 實現了可變大小的數組。它允許所有元素，包括null。ArrayList 沒有同步。size，isEmpty，get，set 方法運行時間為常數。但是add 方法開銷為分攤的常數，添加n 個元素需要O(n)的時間。其他的方法運行時間為線性。

每個ArrayList 實例都有一個容量（Capacity），即用于存儲元素的數組的大小。這個容量可隨著不斷添加新元素而自動增加，但是增長算法并沒有定義。當需要插入大量元素時，在插入前可以調用ensureCapacity 方法來增加ArrayList 的容量以提高插入效率。

LinkedList 實現了List 接口，允許null 元素。此外LinkedList提供額外的get，remove，insert 方法在LinkedList 的首部或尾部。這些操作使LinkedList 可被用作堆棧（stack），隊列（queue）或雙向隊列（deque）。

注意，ArrayList 和LinkedList 都是線程不安全的。如果遇到多線程的環境，則必須自己實現訪問同步。例如：List list =Collections.synchronizedList(new LinkedList(...))；

Vector 也是List 接口的一個實現類，但是Vector 是線程安全的。

Set 是Collection 的另一個子接口，它不允許放入重復的元素，即任意的兩個元素e1 和e2 都有e1.equals(e2)=false，關于null 元素，Set 接口的實現類也只能允許存入一次。

Set 接口的典型實現類，有HashSet 和TreeSet。

Map 也是一個接口，而且是需要重點強調的接口，它在實戰編程中使用的頻率非常高。Map 的特點是用鍵值對的形式來存放數據，即Key-Value。其中，key 不能重復，Value 可以重復。根據這一特點，在實際編碼中，經常用Map 來完成“以鍵查值”的情況。

Map 接口有兩個典型的實現類，HashMap 和TreeMap。其中HashMap 的使用頻率更高一些。但HashMap 也是線程不安全的，如果涉及到并發編程，應使用ConcurrentHashMap 代替。

數據元素在內存中的存放有兩種方式：

順序存儲。相鄰的數據元素存放于相鄰的內存地址中，整塊內存地址是連續的。可以根據元素的位置直接計算出內存地址，直接進行讀取。讀取一個特定位置元素的平均時間復雜度為O(1)。基于數組實現的集合，才有這種特性。比如ArrayList。

鏈式存儲。每一個數據元素，在內存中都不要求處于相鄰的位置，每個數據元素包含它下一個元素的內存地址。讀取一個特定位置元素的平均時間復雜度為O(n)。以鏈表為代表，比如LinkedList。

在選擇容器類的時候，對容器類的遍歷，是一個重要的考慮因素。因為不同的遍歷方式，會給編碼帶來不一樣的難度，同時也會影響一些執行效率。每一個具體實現的數據集合，一般都需要提供相應的Iterator。相比于傳統for 循環，Iterator 取締了顯式的遍歷計數器。所以基于順序存儲集合的Iterator 可以直接按位置訪問數據。而基于鏈式存儲集合的Iterator，正常的實現，都是需要保存當前遍歷的位置。然后根據當前位置來向前或者向后移動指針。

迭代器是容器類對其數據通用的遍歷方式，除Set 接口下的容器必須是用迭代器遍歷之外，其他容器并不推薦使用這種方式。目前比較流行的是foreach 循環，寫法簡單，執行起來也比較快。foreach內部也是采用了Iterator 的方式實現，只不過Java 編譯器幫我們生成了這些代碼。

除foreach 循環之外，使用傳統的for 循環也是一種選擇，寫法上比foreach 循環稍麻煩一些。傳統的for 循環遍歷，基于計數器的。遍歷者自己在集合外部維護一個計數器，然后依次讀取每一個位置的元素，當讀取到最后一個元素后，停止。主要就是需要按元素的位置來讀取元素。

對于Map 的遍歷，首先可以獲取所有的key，按照key 來遍歷，也就是通過key 來尋找value。其次，也可以通過迭代器來遍歷，即申請一個Map 類型的Iterator，比如Iterator＜Map.Entry＜Integer,String＞＞ it，然后去遍歷這個it。

各遍歷方式的適用于什么場合？

1、傳統的for 循環遍歷，基于計數器的：

順序存儲：讀取性能比較高。適用于遍歷順序存儲集合。

鏈式存儲：時間復雜度太大，不適用于遍歷鏈式存儲的集合。

2、迭代器遍歷，Iterator：

順序存儲：如果不是太在意時間，可以使用此方式。

鏈式存儲：平均時間復雜度降為O(n)，推薦此種方式。

3、foreach 循環遍歷：

foreach 只是讓代碼更加簡潔了，但是他有一些缺點，就是遍歷過程中不能操作數據集合（刪除等），所以有些場合不使用。