JAVA集合類(介紹)
在使用Java的時候，我們都會遇到使用集合（Collection）的時候，但是Java API提供了多種集合的實現，我在使用和面試的時候頻頻遇到這樣的“抉擇”。:）（主要還是面試的時候）久而久之，也就有了一點點的心得體會，寫出來以供大家讨論。
總的說來，Java API中所用的集合類，都是實現了Collection接口，他的一個類繼承結構如下：
Collection<--List<--Vector
Collection<--List<--ArrayList
Collection<--List<--LinkedList
Collection<--Set<--HashSet
Collection<--Set<--HashSet<--LinkedHashSet
Collection<--Set<--SortedSet<--TreeSet
Vector:基于Array的List，其實就是封裝了Array所不具備的一些功能方便我們使用，它不可能走入Array的限制。性能也就不可能超越Array。所以，在可能的情況下，我們要多運用Array。另外很重要的一點就是Vector“synchronized”的，這個也是Vector和ArrayList的唯一的區别。ArrayList：同Vector一樣是一個基于Array上的鍊表，但是不同的是ArrayList不是同步的。所以在性能上要比Vector優越一些，但是當運行到多線程環境中時，可需要自己在管理線程的同步問題。LinkedList：LinkedList不同于前面兩種List，它不是基于Array的，所以不受Array性能的限制。它每一個節點（Node）都包含兩方面的内容：1.節點本身的數據（data）；2.下一個節點的信息（nextNode）。所以當對LinkedList做添加，删除動作的時候就不用像基于Array的List一樣，必須進行大量的數據移動。隻要更改nextNode的相關信息就可以實現了。這就是LinkedList的優勢。
List總結
1.所有的List中隻能容納單個不同類型的對象組成的表，而不是Key－Value鍵值對。例如：[tom,1,c]；
2.所有的List中可以有相同的元素，例如Vector中可以有[tom,koo,too,koo]；
3.所有的List中可以有null元素，例如[tom,null,1]；
4.基于Array的List（Vector，ArrayList）适合查詢，而LinkedList（鍊表）适合添加，删除操作。
HashSet：雖然Set同List都實現了Collection接口，但是他們的實現方式卻大不一樣。List基本上都是以Array為基礎。但是Set則是在HashMap的基礎上來實現的，這個就是Set和List的根本區别。HashSet的存儲方式是把HashMap中的Key作為Set的對應存儲項。看看HashSet的add（Object obj）方法的實現就可以一目了然了。
public boolean add(Object obj)
{
return map.put(obj, PRESENT)==null;
}
這個也是為什麼在Set中不能像在List中一樣有重複的項的根本原因，因為HashMap的key是不能有重複的。
LinkedHashSet：HashSet的一個子類，一個鍊表。
TreeSet：SortedSet的子類，它不同于HashSet的根本就是TreeSet是有序的。它是通過SortedMap來實現的。（HashSet和TreeSet均為有序的順序由小到大）
Set總結
1.Set實現的基礎是Map（HashMap）；
2.Set中的元素是不能重複的，如果使用add(Object obj)方法添加已經存在的對象，則會複蓋前面的對象
為什麼要使用集合類
當你事先不知道要存放數據的個數，或者你需要一種比數組下标存取機制更靈活的方法時，你就需要用到集合類。
理解集合類
集合類存放于java.util包中。
集合類存放的都是對象的引用，而非對象本身，出于表達上的便利，我們稱集合中的對象就是指集合中對象的引用（reference)。
集合類型主要有3種：set(集）、list(列表）和map(映射)。
(1)集
集（set）是最簡單的一種集合，它的對象不按特定方式排序，隻是簡單的把對象加入集合中，就像往口袋裡放東西。
對集中成員的訪問和操作是通過集中對象的引用進行的，所以集中不能有重複對象。
集也有多種變體，可以實現排序等功能，如TreeSet，它把對象添加到集中的操作将變為按照某種比較規則将其插入到有序的對象序列中。它實現的是SortedSet接口，也就是加入了對象比較的方法。通過對集中的對象叠代，我們可以得到一個升序的對象集合。
(2)列表
列表的主要特征是其對象以線性方式存儲，沒有特定順序，隻有一個開頭和一個結尾，當然，它與根本沒有順序的集是不同的。
列表在數據結構中分别表現為：數組和向量、鍊表、堆棧、隊列。
關于實現列表的集合類，是我們日常工作中經常用到的，将在後邊的筆記詳細介紹。
(3)映射
映射與集或列表有明顯區别，映射中每個項都是成對的。映射中存儲的每個對象都有一個相關的關鍵字（Key）對象，關鍵字決定了對象在映射中的存儲位置，檢索對象時必須提供相應的關鍵字，就像在字典中查單詞一樣。關鍵字應該是唯一的。
關鍵字本身并不能決定對象的存儲位置，它需要對過一種散列(hashing)技術來處理，産生一個被稱作散列碼(hash code)的整數值，散列碼通常用作一個偏置量，該偏置量是相對于分配給映射的内存區域起始位置的，由此确定關鍵字/對象對的存儲位置。理想情況下，散列處理應該産生給定範圍内均勻分布的值，而且每個關鍵字應得到不同的散列碼。
集合類簡介
java.util中共有13個類可用于管理集合對象，它們支持集、列表或映射等集合，以下是這些類的簡單介紹
集：
HashSet：使用HashMap的一個集的實現。雖然集定義成無序，但必須存在某種方法能相當高效地找到一個對象。使用一個HashMap對象實現集的存儲和檢索操作是在固定時間内實現的.
TreeSet：在集中以升序對對象排序的集的實現。這意味着從一個TreeSet對象獲得第一個叠代器将按升序提供對象。TreeSet類使用了一個TreeMap.
列表：
Vector：實現一個類似數組一樣的表，自動增加容量來容納你所需的元素。使用下标存儲和檢索對象就象在一個标準的數組中一樣。你也可以用一個叠代器從一個Vector中檢索對象。Vector是唯一的同步容器類?當兩個或多個線程同時訪問時也是性能良好的。
Stack:這個類從Vector派生而來，并且增加了方法實現棧?一種後進先出的存儲結構。
LinkedList:實現一個鍊表。由這個類定義的鍊表也可以像棧或隊列一樣被使用。
ArrayList:實現一個數組，它的規模可變并且能像鍊表一樣被訪問。它提供的功能類似Vector類但不同步。
映射：
HashTable：實現一個映象，所有的鍵必須非空。為了能高效的工作，定義鍵的類必須實現hashcode()方法和equal()方法。這個類是前面java實現的一個繼承，并且通常能在實現映象的其他類中更好的使用。
HashMap：實現一個映象，允許存儲空對象，而且允許鍵是空（由于鍵必須是唯一的，當然隻能有一個）。
WeakHashMap：實現這樣一個映象：通常如果一個鍵對一個對象而言不再被引用，鍵/對象對将被舍棄。這與HashMap形成對照，映象中的鍵維持鍵/對象對的生命周期，盡管使用映象的程序不再有對鍵的引用，并且因此不能檢索對象。
TreeMap：實現這樣一個映象，對象是按鍵升序排列的。
Set和List都是由公共接口Collection擴展而來，所以它們都可以使用一個類型為Collection的變量來引用。這就意味着任何列表或集構成的集合都可以用這種方式引用，隻有映射類除外（但也不是完全排除在外，因為可以從映射獲得一個列表。）所以說，把一個
列表或集傳遞給方法的标準途徑是使用Collection類型的參數。
Vector還是ArrayList，哪一個更好，為什麼？
要回答這個問題不能一概而論，有時候使用Vector比較好；有時是ArrayList，有時候這兩個都不是最好的選擇。你别指望能夠獲得一個簡單肯定答案，因為這要看你用它們幹什麼。下面有4個要考慮的因素：
(1)API
(2)同步處理
(3)數據增長性
(4)使用模式
下面針對這4個方面進行一一探讨
API
在由Ken Arnold等編着的《Java Programming Language》(Addison-Wesley, June 2000)一書中有這樣的描述，Vector類似于ArrayList.。所有從API的角度來看這兩個類非常相似。但他們之間也還是有一些主要的區别的。
同步性
Vector是同步的。這個類中的一些方法保證了Vector中的對象是線程安全的。而ArrayList則是異步的，因此ArrayList中的對象并不是線程安全的。因為同步的要求會影響執行的效率，所以如果你不需要線程安全的集合那麼使用ArrayList是一個很好的選擇，這樣可以避免由于同步帶來的不必要的性能開銷。
數據增長
從内部實現機制來講ArrayList和Vector都是使用數組(Array)來控制集合中的對象。當你向這兩種類型中增加元素的時候，如果元素的數目超出了内部數組目前的長度它們都需要擴展内部數組的長度，Vector缺省情況下自動增長原來一倍的數組長度ArrayList是原來的50%,所以最後你獲得的這個集合所占的空間總是比你實際需要的要大。所以如果你要在集合中保存大量的數據那麼使用Vector有一些優勢，因為你可以通過設置集合的初始化大小來避免不必要的資源開銷。
使用模式
在ArrayList和Vector中，從一個指定的位置（通過索引）查找數據或是在集合的末尾增加、移除一個元素所花費的時間是一樣的，這個時間我們用O(1)表示。但是，如果在集合的其他位置增加或移除元素那麼花費的時間會呈線形增長：O(n-i)，其中n代表集合中元素的個數，i代表元素增加或移除元素的索引位置。為什麼會這樣呢？以為在進行上述操作的時候集合中第i和第i個元素之後的所有元素都要執行位移的操作。這一切意味着什麼呢？
這意味着，你隻是查找特定位置的元素或隻在集合的末端增加、移除元素，那麼使用Vector或ArrayList都可以。如果是其他操作，你最好選擇其他的集合操作類。比如，LinkList集合類在增加或移除集合中任何位置的元素所花費的時間都是一樣的—O(1)，但它在索引一個元素的使用缺比較慢－O(i),其中i是索引的位置.使用ArrayList也很容易，因為你可以簡單的使用索引來代替創建iterator對象的操作。LinkList也會為每個插入的元素創建對象，所有你要明白它也會帶來額外的開銷。
最後，在《Practical Java》一書中Peter Haggar建議使用一個簡單的數組（Array）來代替Vector或ArrayList。尤其是對于執行效率要求高的程序更應如此。因為使用數組(Array)避免了同步、額外的方法調用和不必要的重新分配空間的操作。
