在使用Java的時(shí)候，我們都會(huì )遇到使用集合（Collection）的時(shí)候，但是Java API提供了多種集合的實(shí)現，我在使用和面試的時(shí)候頻
頻遇到這樣的“抉擇” 。 :）（主要還是面試的時(shí)候）
久而久之，也就有了一點(diǎn)點(diǎn)的心得體會(huì )，寫(xiě)出來(lái)以供大家討論 。
總的說(shuō)來(lái)，Java API中所用的集合類(lèi)，都是實(shí)現了Collection接口，他的一個(gè)類(lèi)繼承結構如下：
Collection<--List<--Vector
Collection<--List<--ArrayList
Collection<--List<--LinkedList
Collection<--Set<--HashSet
Collection<--Set<--HashSet<--LinkedHashSet
Collection<--Set<--SortedSet<--TreeSet
Vector : 基于A(yíng)rray的List，其實(shí)就是封裝了Array所不具備的一些功能方便我們使用，它不可能走入Array的限制。性能也就不可能超越Array。所以，在可能的情況下，我們要多運用Array。另外很重要的一點(diǎn)就是Vector“sychronized”的，這個(gè)也是Vector和ArrayList的唯一的區別。ArrayList：同Vector一樣是一個(gè)基于A(yíng)rray上的鏈表，但是不同的是ArrayList不是同步的。所以在性能上要比Vector優(yōu)越一些，但是當運行到多線(xiàn)程環(huán)境中時(shí)，可需要自己在管理線(xiàn)程的同步問(wèn)題。LinkedList：LinkedList不同于前面兩種List，它不是基于A(yíng)rray的，所以不受Array性能的限制。它每一個(gè)節點(diǎn)（Node）都包含兩方面的內容：1.節點(diǎn)本身的數據（data）；2.下一個(gè)節點(diǎn)的信息（nextNode）。所以當對LinkedList做添加，刪除動(dòng)作的時(shí)候就不用像基于A(yíng)rray的List一樣，必須進(jìn)行大量的數據移動(dòng)。只要更改nextNode的相關(guān)信息就可以實(shí)現了。這就是LinkedList的優(yōu)勢。
List總結：
1. 所有的List中只能容納單個(gè)不同類(lèi)型的對象組成的表，而不是Key－Value鍵值對。例如：[ tom,1,c ]；
2. 所有的List中可以有相同的元素，例如Vector中可以有 [ tom,koo,too,koo ]；
3. 所有的List中可以有null元素，例如[ tom,null,1 ]；
4. 基于A(yíng)rray的List（Vector，ArrayList）適合查詢(xún)，而LinkedList（鏈表）適合添加，刪除操作。
HashSet：雖然Set同List都實(shí)現了Collection接口，但是他們的實(shí)現方式卻大不一樣。List基本上都是以Array為基礎。但是Set則是
在HashMap的基礎上來(lái)實(shí)現的，這個(gè)就是Set和List的根本區別。HashSet的存儲方式是把HashMap中的Key作為Set的對應存儲項?？纯?
HashSet的add（Object obj）方法的實(shí)現就可以一目了然了。
public boolean add(Object obj)
{
return map.put(obj, PRESENT) == null;
}
這個(gè)也是為什么在Set中不能像在List中一樣有重復的項的根本原因，因為HashMap的key是不能有重復的。
LinkedHashSet：HashSet的一個(gè)子類(lèi)，一個(gè)鏈表。
TreeSet：SortedSet的子類(lèi)，它不同于HashSet的根本就是TreeSet是有序的。它是通過(guò)SortedMap來(lái)實(shí)現的。
Set總結：
1. Set實(shí)現的基礎是Map（HashMap）；
2. Set中的元素是不能重復的，如果使用add(Object obj)方法添加已經(jīng)存在的對象，則會(huì )覆蓋前面的對象
為什么要使用集合類(lèi)
當你事先不知道要存放數據的個(gè)數，或者你需要一種比數組下標存取機制更靈活的方法時(shí)，你就需要用到集合類(lèi)。
理解集合類(lèi)
集合類(lèi)存放于java.util包中。
集合類(lèi)存放的都是對象的引用，而非對象本身，出于表達上的便利，我們稱(chēng)集合中的對象就是指集合中對象的引用（reference)。
集合類(lèi)型主要有3種：set(集）、list(列表）和map(映射)。
(1)集
集（set）是最簡(jiǎn)單的一種集合，它的對象不按特定方式排序，只是簡(jiǎn)單的把對象加入集合中，就像往口袋里放東西。
對集中成員的訪(fǎng)問(wèn)和操作是通過(guò)集中對象的引用進(jìn)行的，所以集中不能有重復對象。
集也有多種變體，可以實(shí)現排序等功能，如TreeSet，它把對象添加到集中的操作將變?yōu)榘凑漳撤N比較規則將其插入到有序的對象序
列中。它實(shí)現的是SortedSet接口，也就是加入了對象比較的方法。通過(guò)對集中的對象迭代，我們可以得到一個(gè)升序的對象集合。
(2)列表
列表的主要特征是其對象以線(xiàn)性方式存儲，沒(méi)有特定順序，只有一個(gè)開(kāi)頭和一個(gè)結尾，當然，它與根本沒(méi)有順序的集是不同的。
列表在數據結構中分別表現為：數組和向量、鏈表、堆棧、隊列。
關(guān)于實(shí)現列表的集合類(lèi)，是我們日常工作中經(jīng)常用到的，將在后邊的筆記詳細介紹。
(3)映射
映射與集或列表有明顯區別，映射中每個(gè)項都是成對的。映射中存儲的每個(gè)對象都有一個(gè)相關(guān)的關(guān)鍵字（Key）對象，關(guān)鍵字決定了
對象在映射中的存儲位置，檢索對象時(shí)必須提供相應的關(guān)鍵字，就像在字典中查單詞一樣。關(guān)鍵字應該是唯一的。
關(guān)鍵字本身并不能決定對象的存儲位置，它需要對過(guò)一種散列(hashing)技術(shù)來(lái)處理，產(chǎn)生一個(gè)被稱(chēng)作散列碼(hash code)的整數值，
散列碼通常用作一個(gè)偏置量，該偏置量是相對于分配給映射的內存區域起始位置的，由此確定關(guān)鍵字/對象對的存儲位置。理想情況
下，散列處理應該產(chǎn)生給定范圍內均勻分布的值，而且每個(gè)關(guān)鍵字應得到不同的散列碼。
集合類(lèi)簡(jiǎn)介
java.util中共有13個(gè)類(lèi)可用于管理集合對象，它們支持集、列表或映射等集合，以下是這些類(lèi)的簡(jiǎn)單介紹
集：
HashSet： 使用HashMap的一個(gè)集的實(shí)現。雖然集定義成無(wú)序，但必須存在某種方法能相當高效地找到一個(gè)對象。使用一個(gè)HashMap對
象實(shí)現集的存儲和檢索操作是在固定時(shí)間內實(shí)現的.
TreeSet： 在集中以升序對對象排序的集的實(shí)現。這意味著(zhù)從一個(gè)TreeSet對象獲得第一個(gè)迭代器將按升序提供對象。TreeSet類(lèi)使用
了一個(gè)TreeMap.
列表：
Vector： 實(shí)現一個(gè)類(lèi)似數組一樣的表，自動(dòng)增加容量來(lái)容納你所需的元素。使用下標存儲和檢索對象就象在一個(gè)標準的數組中一樣
。你也可以用一個(gè)迭代器從一個(gè)Vector中檢索對象。Vector是唯一的同步容器類(lèi)??當兩個(gè)或多個(gè)線(xiàn)程同時(shí)訪(fǎng)問(wèn)時(shí)也是性能良好的。
Stsck: 這個(gè)類(lèi)從Vector派生而來(lái)，并且增加了方法實(shí)現棧??一種后進(jìn)先出的存儲結構。
LinkedList: 實(shí)現一個(gè)鏈表。由這個(gè)類(lèi)定義的鏈表也可以像?；蜿犃幸粯颖皇褂?。
ArrayList: 實(shí)現一個(gè)數組，它的規?？勺儾⑶夷芟矜湵硪粯颖辉L(fǎng)問(wèn)。它提供的功能類(lèi)似Vector類(lèi)但不同步。
映射：
HashTable： 實(shí)現一個(gè)映象，所有的鍵必須非空。為了能高效的工作，定義鍵的類(lèi)必須實(shí)現hashcode()方法和equal()方法。這個(gè)類(lèi)
是前面java實(shí)現的一個(gè)繼承，并且通常能在實(shí)現映象的其他類(lèi)中更好的使用。
HashMap： 實(shí)現一個(gè)映象，允許存儲空對象，而且允許鍵是空（由于鍵必須是唯一的，當然只能有一個(gè)）。
WeakHashMap： 實(shí)現這樣一個(gè)映象：通常如果一個(gè)鍵對一個(gè)對象而言不再被引用，鍵/對象對將被舍棄。這與HashMap形成對照，映象
中的鍵維持鍵/對象對的生命周期，盡管使用映象的程序不再有對鍵的引用，并且因此不能檢索對象。
TreeMap： 實(shí)現這樣一個(gè)映象，對象是按鍵升序排列的。
Set和List都是由公共接口Collection擴展而來(lái)，所以它們都可以使用一個(gè)類(lèi)型為Collection的變量來(lái)引用。這就意味著(zhù)任何列表或
集構成的集合都可以用這種方式引用，只有映射類(lèi)除外（但也不是完全排除在外，因為可以從映射獲得一個(gè)列表。）所以說(shuō)，把一個(gè)
列表或集傳遞給方法的標準途徑是使用Collection類(lèi)型的參數。
Vector 還是ArrayList，哪一個(gè)更好，為什么？
要回答這個(gè)問(wèn)題不能一概而論，有時(shí)候使用Vector比較好；有時(shí)是ArrayList，有時(shí)候這兩個(gè)都不是最好的選擇。你別指望能夠獲得
一個(gè)簡(jiǎn)單肯定答案，因為這要看你用它們干什么。下面有4個(gè)要考慮的因素：
(1)API
(2)同步處理
(3)數據增長(cháng)性
(4)使用模式
下面針對這4個(gè)方面進(jìn)行一一探討
API
在由Ken Arnold等編著(zhù)的《Java Programming Language》(Addison-Wesley, June 2000)一書(shū)中有這樣的描述，Vector類(lèi)似于
ArrayList.。所有從API的角度來(lái)看這兩個(gè)類(lèi)非常相似。但他們之間也還是有一些主要的區別的。
同步性
Vector是同步的。這個(gè)類(lèi)中的一些方法保證了Vector中的對象是線(xiàn)程安全的。而ArrayList則是異步的，因此ArrayList中的對象并不
是線(xiàn)程安全的。因為同步的要求會(huì )影響執行的效率，所以如果你不需要線(xiàn)程安全的集合那么使用ArrayList是一個(gè)很好的選擇，這樣
可以避免由于同步帶來(lái)的不必要的性能開(kāi)銷(xiāo)。
數據增長(cháng)
從內部實(shí)現機制來(lái)講ArrayList和Vector都是使用數組(Array)來(lái)控制集合中的對象。當你向這兩種類(lèi)型中增加元素的時(shí)候，如果元素
的數目超出了內部數組目前的長(cháng)度它們都需要擴展內部數組的長(cháng)度，Vector缺省情況下自動(dòng)增長(cháng)原來(lái)一倍的數組長(cháng)度，ArrayList是
原來(lái)的50%,所以最后你獲得的這個(gè)集合所占的空間總是比你實(shí)際需要的要大。所以如果你要在集合中保存大量的數據那么使用Vector
有一些優(yōu)勢，因為你可以通過(guò)設置集合的初始化大小來(lái)避免不必要的資源開(kāi)銷(xiāo)。
使用模式
在A(yíng)rrayList和Vector中，從一個(gè)指定的位置（通過(guò)索引）查找數據或是在集合的末尾增加、移除一個(gè)元素所花費的時(shí)間是一樣的，
這個(gè)時(shí)間我們用O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花費的時(shí)間會(huì )呈線(xiàn)形增長(cháng)：O(n-i)，其中n代表集合中
元素的個(gè)數，i代表元素增加或移除元素的索引位置。為什么會(huì )這樣呢？以為在進(jìn)行上述操作的時(shí)候集合中第i和第i個(gè)元素之后的所
有元素都要執行位移的操作。這一切意味著(zhù)什么呢？
這意味著(zhù)，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，
你最好選擇其他的集合操作類(lèi)。比如，LinkList集合類(lèi)在增加或移除集合中任何位置的元素所花費的時(shí)間都是一樣的—O(1)，但它在
索引一個(gè)元素的使用缺比較慢－O(i),其中i是索引的位置.使用ArrayList也很容易，因為你可以簡(jiǎn)單的使用索引來(lái)代替創(chuàng )建iterator
對象的操作。LinkList也會(huì )為每個(gè)插入的元素創(chuàng )建對象，所有你要明白它也會(huì )帶來(lái)額外的開(kāi)銷(xiāo)。
最后，在《Practical Java》一書(shū)中Peter Haggar建議使用一個(gè)簡(jiǎn)單的數組（Array）來(lái)代替Vector或ArrayList。尤其是對于執行效
率要求高的程序更應如此。因為使用數組(Array)避免了同步、額外的方法調用和不必要的重新分配空間的操作
本文來(lái)自CSDN博客，轉載請標明出處：http://blog.csdn.net/gleams/archive/2008/07/17/2665857.aspx
聯(lián)系客服
