java集合
集合之間的關(guān)系
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap
Collection
最基本的集合接口，一個Collection代表一組Object的集合，這些Object被稱作Collection的元素。Collection是一個接口，用以提供規(guī)范定義，不能被實(shí)例化使用;不論 Collection 的實(shí)際類型如何，它都支持一個 iterator() 的方法，該方法返回一個迭代子，使用該迭代子即可逐一訪問 Collection 中每一個元素。典型的用法如下：
Iterator it = collection.iterator(); // 獲得一個迭代子
while(it.hasNext()){
Object obj = it.next(); // 得到下一個元素
}
List
List集合代表一個元素有序、可重復(fù)的集合，集合中每個元素都有其對應(yīng)的順序索引。List集合允許加入重復(fù)元素，因?yàn)樗梢酝ㄟ^索引來訪問指定位置的集合元素。List集合默認(rèn)按元素的添加順序設(shè)置元素的索引，除了具有 Collection 接口必備的 iterator() 方法外，List 還提供一個 listIterator() 方法，返回一個 ListIterator 接口。和標(biāo)準(zhǔn)的 Iterator 接口相比，ListIterator 多了一些 add() 之類的方法，允許添加、刪除、設(shè)定元素、向前或向后遍歷等功能，實(shí)現(xiàn) List 接口的常用類有 LinkedList，ArrayList，Vector 和 Stack
LinkedList
LinkedList 實(shí)現(xiàn)了 List 接口，允許 Null 元素。此外 LinkedList 提供額外的 Get、Remove、Insert 等方法在 LinkedList 的首部或尾部操作數(shù)據(jù)。這些操作使得 LinkedList 可被用作堆棧（Stack）、隊列（Queue）或雙向隊列（Deque，無同步方法，創(chuàng)建 List 時構(gòu)造一個同步的 List，方法如
List list = Collections.synchronizedList(new LinkedList(...))
ArrayList
ArrayList是基于數(shù)組實(shí)現(xiàn)的List類，它封裝了一個動態(tài)的增長的、允許再分配的Object[]數(shù)組，它允許所有元素，包括 Null。Size、IsEmpty、Get、Set 等方法的運(yùn)行時間為常數(shù)，但是 Add 方法開銷為分?jǐn)偟某?shù)，添加 N 個元素需要 O(N) 的時間，其他的方法運(yùn)行時間為線性，也是非線程同步的，另外在插入大量元素時可以調(diào)用 ensureCapacity 方法來增加 ArrayList 的容量以提高插入效率
Vector
和ArrayList基本一致，但是是線程同步，同時使用時可能會拋出ConcurrentModificationException，因此必須捕獲該異常
Stack
Stack 繼承自 Vector，實(shí)現(xiàn)了一個后進(jìn)先出的堆棧。Stack 提供 5 個額外的方法使得 Vector 得以被當(dāng)作堆棧使用。除了基本的 Push 和 Pop 方法，還有 Peek 方法得到棧頂?shù)脑?，Empty 方法測試堆棧是否為空，Search 方法檢測一個元素在堆棧中的位置。注意，Stack 剛創(chuàng)建后是空棧
Set
Set 是一種不包含重復(fù)的元素的 Collection，即任意的兩個元素 e1 和 e2 都有 e1.equals(e2)=false。Set 最多有一個 null 元素。很明顯，Set 的構(gòu)造函數(shù)有一個約束條件，傳入的 Collection 參數(shù)不能包含重復(fù)的元素。請注意，必須小心操作可變對象（Mutable Object），如果一個 Set 中的可變元素改變了自身狀態(tài)，這可能會導(dǎo)致一些問題，另外：Set判斷兩個對象相同不是使用"=="運(yùn)算符，而是根據(jù)equals方法。
HashSet
HashSet是Set接口的典型實(shí)現(xiàn)，HashSet使用HASH算法來存儲集合中的元素，因此具有良好的存取和查找性能。
當(dāng)向HashSet集合中存入一個元素時，HashSet會調(diào)用該對象的hashCode()方法來得到該對象的hashCode值，然后根據(jù)該HashCode值決定該對象在HashSet中的存儲位置。
值得注意的是，HashSet集合判斷兩個元素相等的標(biāo)準(zhǔn)是兩個對象通過equals()方法比較相等，并且兩個對象的hashCode()方法的返回值相等
LinkedHashSet
LinkedHashSet集合也是根據(jù)元素的hashCode值來決定元素的存儲位置，但和HashSet不同的是，它同時使用鏈表維護(hù)元素的次序，這樣使得元素看起來是以插入的順序保存的。
當(dāng)遍歷LinkedHashSet集合里的元素時，LinkedHashSet將會按元素的添加順序來訪問集合里的元素。
LinkedHashSet需要維護(hù)元素的插入順序，因此性能略低于HashSet的性能，但在迭代訪問Set里的全部元素時(遍歷)將有很好的性能(鏈表很適合進(jìn)行遍歷)
SortedSet
此接口主要用于排序操作，即實(shí)現(xiàn)此接口的子類都屬于排序的子類
TreeSet
TreeSet是SortedSet接口的實(shí)現(xiàn)類，TreeSet可以確保集合元素處于排序狀態(tài)
Map
Map用于保存具有"映射關(guān)系"的數(shù)據(jù)，因此Map集合里保存著兩組值，一組值用于保存Map里的key，另外一組值用于保存Map里的value。key和value都可以是任何引用類型的數(shù)據(jù)。Map的key不允許重復(fù)，即同一個Map對象的任何兩個key通過equals方法比較結(jié)果總是返回false。關(guān)于Map，我們要從代碼復(fù)用的角度去理解，java是先實(shí)現(xiàn)了Map，然后通過包裝了一個所有value都為null的Map就實(shí)現(xiàn)了Set集合，Map的這些實(shí)現(xiàn)類和子接口中key集的存儲形式和Set集合完全相同(即key不能重復(fù))，Map的這些實(shí)現(xiàn)類和子接口中value集的存儲形式和List非常類似(即value可以重復(fù)、根據(jù)索引來查找)
HashMap
和HashSet集合不能保證元素的順序一樣，HashMap也不能保證key-value對的順序。并且類似于HashSet判斷兩個key是否相等的標(biāo)準(zhǔn)也是: 兩個key通過equals()方法比較返回true;同時兩個key的hashCode值也必須相等;如果迭代操作的性能相當(dāng)重要的話，不要將 HashMap 的初始化容量設(shè)得過高，或者 Load Factor 參數(shù)設(shè)置過低。
LinkedHashMap
LinkedHashMap也使用雙向鏈表來維護(hù)key-value對的次序，該鏈表負(fù)責(zé)維護(hù)Map的迭代順序，與key-value對的插入順序一致(注意和TreeMap對所有的key-value進(jìn)行排序進(jìn)行區(qū)
Hashtable
是一個古老的Map實(shí)現(xiàn)類，線程同步，Hashtable 繼承 Map 接口，實(shí)現(xiàn)了一個基于 Key-Value 映射的哈希表。任何非空（non-null）的對象都可作為 Key 或者 Value。添加數(shù)據(jù)使用 Put(Key，Value)，取出數(shù)據(jù)使用 Get(Key)，這兩個基本操作的時間開銷為常數(shù)，Hashtable 通過 Initial Capacity 和 Load Factor 兩個參數(shù)調(diào)整性能。通常缺省的 Load Factor 0.75 較好地實(shí)現(xiàn)了時間和空間的均衡。增大 Load Factor 可以節(jié)省空間但相應(yīng)的查找時間將增大，會影響像 Get 和 Put 這樣的操作
TreeMap
TreeMap就是一個紅黑樹數(shù)據(jù)結(jié)構(gòu)，每個key-value對即作為紅黑樹的一個節(jié)點(diǎn)。TreeMap存儲key-value對(節(jié)點(diǎn))時，需要根據(jù)key對節(jié)點(diǎn)進(jìn)行排序。TreeMap可以保證所有的key-value對處于有序狀態(tài)。同樣，TreeMap也有兩種排序方式: 自然排序、定制排序
WeakHashMap
WeakHashMap與HashMap的用法基本相似。區(qū)別在于，HashMap的key保留了對實(shí)際對象的"強(qiáng)引用"，這意味著只要該HashMap對象不被銷毀，該HashMap所引用的對象就不會被垃圾回收。但WeakHashMap的key只保留了對實(shí)際對象的弱引用，這意味著如果WeakHashMap對象的key所引用的對象沒有被其他強(qiáng)引用變量所引用，則這些key所引用的對象可能被垃圾回收，當(dāng)垃圾回收了該key所對應(yīng)的實(shí)際對象之后，WeakHashMap也可能自動刪除這些key所對應(yīng)的key-value對。
實(shí)踐
ArrayList、Vector、LinkedList 均來自 AbstractList 的實(shí)現(xiàn)，而 AbstractList 直接實(shí)現(xiàn)了 List 接口，并擴(kuò)展自 AbstarctCollection。ArrayList 和 Vector 使用了數(shù)組實(shí)現(xiàn)，ArrayList 沒有對任何一個方法提供線程同步，因此不是線程安全的，Vector 中絕大部分方法都做了線程同步，是一種線程安全的實(shí)現(xiàn)。LinkedList 使用了循環(huán)雙向鏈表數(shù)據(jù)結(jié)構(gòu)，由一系列表項(xiàng)連接而成，一個表項(xiàng)總是包含 3 個部分，元素內(nèi)容、前驅(qū)表項(xiàng)和后驅(qū)表項(xiàng)。
當(dāng) ArrayList 對容量的需求超過當(dāng)前數(shù)組的大小時，需要進(jìn)行擴(kuò)容。擴(kuò)容過程中，會進(jìn)行大量的數(shù)組復(fù)制操作，而數(shù)組復(fù)制時，最終將調(diào)用 System.arraycopy() 方法。LinkedList 由于使用了鏈表的結(jié)構(gòu)，因此不需要維護(hù)容量的大小，然而每次的元素增加都需要新建一個 Entry 對象，并進(jìn)行更多的賦值操作，在頻繁的系統(tǒng)調(diào)用下，對性能會產(chǎn)生一定的影響，在不間斷地生成新的對象還是占用了一定的資源。而因?yàn)閿?shù)組的連續(xù)性，因此總是在尾端增加元素時，只有在空間不足時才產(chǎn)生數(shù)組擴(kuò)容和數(shù)組復(fù)制。
ArrayList 是基于數(shù)組實(shí)現(xiàn)的，而數(shù)組是一塊連續(xù)的內(nèi)存空間，如果在數(shù)組的任意位置插入元素，必然導(dǎo)致在該位置后的所有元素需要重新排列，因此其效率較差，盡可能將數(shù)據(jù)插入到尾部。LinkedList 不會因?yàn)椴迦霐?shù)據(jù)導(dǎo)致性能下降。
ArrayList 的每一次有效的元素刪除操作后都要進(jìn)行數(shù)組的重組，并且刪除的元素位置越靠前，數(shù)組重組時的開銷越大，要刪除的元素位置越靠后，開銷越小。LinkedList 要移除中間的數(shù)據(jù)需要便利完半個 List。
HashMap 是將 Key 做 Hash 算法，然后將 Hash 值映射到內(nèi)存地址，直接取得 Key 所對應(yīng)的數(shù)據(jù)。在 HashMap 中，底層數(shù)據(jù)結(jié)構(gòu)使用的是數(shù)組，所謂的內(nèi)存地址即數(shù)組的下標(biāo)索引。HashMap 的高性能需要保證以下幾點(diǎn)：
- Hash 算法必須是高效的；
- Hash 值到內(nèi)存地址 (數(shù)組索引) 的算法是快速的；
- 根據(jù)內(nèi)存地址 (數(shù)組索引) 可以直接取得對應(yīng)的值。
HashMap 實(shí)際上是一個鏈表的數(shù)組。前面已經(jīng)介紹過，基于 HashMap 的鏈表方式實(shí)現(xiàn)機(jī)制，只要 HashCode() 和 Hash() 方法實(shí)現(xiàn)得足夠好，能夠盡可能地減少沖突的產(chǎn)生，那么對 HashMap 的操作幾乎等價于對數(shù)組的隨機(jī)訪問操作，具有很好的性能。但是，如果 HashCode() 或者 Hash() 方法實(shí)現(xiàn)較差，在大量沖突產(chǎn)生的情況下，HashMap 事實(shí)上就退化為幾個鏈表，對 HashMap 的操作等價于遍歷鏈表，此時性能很差。
HashMap 的一個功能缺點(diǎn)是它的無序性，被存入到 HashMap 中的元素，在遍歷 HashMap 時，其輸出是無序的。如果希望元素保持輸入的順序，可以使用 LinkedHashMap 替代。
LinkedHashMap 繼承自 HashMap，具有高效性，同時在 HashMap 的基礎(chǔ)上，又在內(nèi)部增加了一個鏈表，用以存放元素的順序。
HashMap 通過 hash 算法可以最快速地進(jìn)行 Put() 和 Get() 操作。TreeMap 則提供了一種完全不同的 Map 實(shí)現(xiàn)。從功能上講，TreeMap 有著比 HashMap 更為強(qiáng)大的功能，它實(shí)現(xiàn)了 SortedMap 接口，這意味著它可以對元素進(jìn)行排序。TreeMap 的性能略微低于 HashMap。如果在開發(fā)中需要對元素進(jìn)行排序，那么使用 HashMap 便無法實(shí)現(xiàn)這種功能，使用 TreeMap 的迭代輸出將會以元素順序進(jìn)行。LinkedHashMap 是基于元素進(jìn)入集合的順序或者被訪問的先后順序排序，TreeMap 則是基于元素的固有順序 (由 Comparator 或者 Comparable 確定)。
LinkedHashMap 是根據(jù)元素增加或者訪問的先后順序進(jìn)行排序，而 TreeMap 則根據(jù)元素的 Key 進(jìn)行排序。
總結(jié)
綜合前面的介紹，我們可以知道，如果涉及到堆棧、隊列等操作，應(yīng)該考慮用 List。對于需要快速插入、刪除元素等操作，應(yīng)該使用 LinkedList。如果需要快速隨機(jī)訪問元素，應(yīng)該使用 ArrayList。如果程序在單線程環(huán)境中，或者訪問僅僅在一個線程中進(jìn)行，考慮非同步的類，其效率較高。如果多個線程可能同時操作一個類，應(yīng)該使用同步的類。要特別注意對哈希表的操作，作為 Key 的對象要正確復(fù)寫 Equals 和 HashCode 方法。盡量返回接口而非實(shí)際的類型，如返回 List 而非 ArrayList，這樣如果以后需要將 ArrayList 換成 LinkedList 時，客戶端代碼不用改變，這就是針對抽象進(jìn)行編程思想
整理自：
http://www.ibm.com/developerworks/cn/java/j-lo-set-operation/index.html
http://www.cnblogs.com/LittleHann/p/3690187.html
http://wiki.jikexueyuan.com/project/java-interview-bible/collection.html
http://www.importnew.com/13801.html
