Java 容器類的選擇

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

關(guān)鍵字：Java 容器類

Java 容器類有兩個基本的上層接口Collection 和Map，在兩種上層接口的基礎(chǔ)上，衍生了一系列的子接口以及其實(shí)現(xiàn)類。

Collection，獨(dú)立元素的序列，這些元素都服從一條或多條規(guī)則。List、Set 都是Collection 的一種，List 強(qiáng)調(diào)順序，而Set 不能有重復(fù)元素。Map 是鍵值對類型，允許用戶通過鍵來查找對象。Hash 表允許使用另一個對象來查找某個對象。所有實(shí)現(xiàn)Collection 接口的類都必須提供兩個標(biāo)準(zhǔn)的構(gòu)造函數(shù)：無參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個空的Collection，有一個Collection 參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個新的Collection，這個新的Collection 與傳入的Collection 有相同的元素。后一個構(gòu)造函數(shù)允許用戶復(fù)制一個Collection。

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

實(shí)現(xiàn)List 接口的常用類有LinkedList，ArrayList 和Vector。

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

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

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

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

Vector 也是List 接口的一個實(shí)現(xiàn)類，但是Vector 是線程安全的。

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

Set 接口的典型實(shí)現(xiàn)類，有HashSet 和TreeSet。

Map 也是一個接口，而且是需要重點(diǎn)強(qiáng)調(diào)的接口，它在實(shí)戰(zhàn)編程中使用的頻率非常高。Map 的特點(diǎn)是用鍵值對的形式來存放數(shù)據(jù)，即Key-Value。其中，key 不能重復(fù)，Value 可以重復(fù)。根據(jù)這一特點(diǎn)，在實(shí)際編碼中，經(jīng)常用Map 來完成“以鍵查值”的情況。

Map 接口有兩個典型的實(shí)現(xiàn)類，HashMap 和TreeMap。其中HashMap 的使用頻率更高一些。但HashMap 也是線程不安全的，如果涉及到并發(fā)編程，應(yīng)使用ConcurrentHashMap 代替。

數(shù)據(jù)元素在內(nèi)存中的存放有兩種方式：

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

鏈?zhǔn)酱鎯ΑＣ恳粋€數(shù)據(jù)元素，在內(nèi)存中都不要求處于相鄰的位置，每個數(shù)據(jù)元素包含它下一個元素的內(nèi)存地址。讀取一個特定位置元素的平均時間復(fù)雜度為O(n)。以鏈表為代表，比如LinkedList。

在選擇容器類的時候，對容器類的遍歷，是一個重要的考慮因素。因?yàn)椴煌谋闅v方式，會給編碼帶來不一樣的難度，同時也會影響一些執(zhí)行效率。每一個具體實(shí)現(xiàn)的數(shù)據(jù)集合，一般都需要提供相應(yīng)的Iterator。相比于傳統(tǒng)for 循環(huán)，Iterator 取締了顯式的遍歷計數(shù)器。所以基于順序存儲集合的Iterator 可以直接按位置訪問數(shù)據(jù)。而基于鏈?zhǔn)酱鎯系腎terator，正常的實(shí)現(xiàn)，都是需要保存當(dāng)前遍歷的位置。然后根據(jù)當(dāng)前位置來向前或者向后移動指針。

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

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

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

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

1、傳統(tǒng)的for 循環(huán)遍歷，基于計數(shù)器的：

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

鏈?zhǔn)酱鎯Γ簳r間復(fù)雜度太大，不適用于遍歷鏈?zhǔn)酱鎯Φ募稀?/p>

2、迭代器遍歷，Iterator：

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

鏈?zhǔn)酱鎯Γ浩骄鶗r間復(fù)雜度降為O(n)，推薦此種方式。

3、foreach 循環(huán)遍歷：

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