前言

Java中集合大家族的成員實(shí)在是太豐富了暇藏，有常用的ArrayList蜜笤、HashMap、HashSet盐碱，也有不常用的Stack把兔、Queue沪伙，有線程安全的Vector、HashTable县好，也有線程不安全的LinkedList围橡、TreeMap等等。

java集合類

一缕贡、Collection接口

Collection接口是最基本的集合接口某饰，它不提供直接的實(shí)現(xiàn)，Java SDK提供的類都是繼承自Collection的“子接口”如List和Set善绎。Collection所代表的是一種規(guī)則黔漂，它所包含的元素都必須遵循一條或者多條規(guī)則。如有些允許重復(fù)而有些則不能重復(fù)禀酱、有些必須要按照順序插入而有些則是散列炬守，有些支持排序但是有些則不支持。
????在Java中所有實(shí)現(xiàn)了Collection接口的類都必須提供兩套標(biāo)準(zhǔn)的構(gòu)造函數(shù)剂跟，一個是無參减途，用于創(chuàng)建一個空的Collection，一個是帶有Collection參數(shù)的有參構(gòu)造函數(shù)曹洽，用于創(chuàng)建一個新的Collection鳍置，這個新的Collection與傳入進(jìn)來的Collection具備相同的元素。

二、List接口

List接口為Collection直接接口。List所代表的是有序的Collection片习，即它用某種特定的插入順序來維護(hù)元素順序万皿。用戶可以對列表中每個元素的插入位置進(jìn)行精確地控制，同時可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素，并搜索列表中的元素。實(shí)現(xiàn)List接口的集合主要有：ArrayList、LinkedList衫冻、Vector、Stack谒出。
2.1隅俘、ArrayList
????ArrayList是一個動態(tài)數(shù)組，也是我們最常用的集合笤喳。它允許任何符合規(guī)則的元素插入甚至包括null为居。每一個ArrayList都有一個初始容量（10），該容量代表了數(shù)組的大小莉测。隨著容器中的元素不斷增加颜骤，容器的大小也會隨著增加。在每次向容器中增加元素的同時都會進(jìn)行容量檢查捣卤，當(dāng)快溢出時忍抽，就會進(jìn)行擴(kuò)容操作八孝。所以如果我們明確所插入元素的多少，最好指定一個初始容量值鸠项，避免過多的進(jìn)行擴(kuò)容操作而浪費(fèi)時間干跛、效率。
????size祟绊、isEmpty楼入、get、set牧抽、iterator 和 listIterator 操作都以固定時間運(yùn)行嘉熊。add 操作以分?jǐn)偟墓潭〞r間運(yùn)行，也就是說扬舒，添加 n 個元素需要 O(n) 時間（由于要考慮到擴(kuò)容阐肤，所以這不只是添加元素會帶來分?jǐn)偣潭〞r間開銷那樣簡單）。
????ArrayList擅長于隨機(jī)訪問讲坎。同時ArrayList是非同步的孕惜。
2.2、LinkedList
????同樣實(shí)現(xiàn)List接口的LinkedList與ArrayList不同晨炕，ArrayList是一個動態(tài)數(shù)組衫画，而LinkedList是一個雙向鏈表。所以它除了有ArrayList的基本操作方法外還額外提供了get瓮栗，remove削罩，insert方法在LinkedList的首部或尾部。
????由于實(shí)現(xiàn)的方式不同遵馆，LinkedList不能隨機(jī)訪問鲸郊，它所有的操作都是要按照雙重鏈表的需要執(zhí)行丰榴。在列表中索引的操作將從開頭或結(jié)尾遍歷列表（從靠近指定索引的一端）货邓。這樣做的好處就是可以通過較低的代價在List中進(jìn)行插入和刪除操作。
????與ArrayList一樣四濒，LinkedList也是非同步的换况。如果多個線程同時訪問一個List，則必須自己實(shí)現(xiàn)訪問同步盗蟆。一種解決方法是在創(chuàng)建List時構(gòu)造一個同步的List： List list = Collections.synchronizedList(new LinkedList(...));
2.3戈二、Vector
????與ArrayList相似，但是Vector是同步的喳资。所以說Vector是線程安全的動態(tài)數(shù)組觉吭。它的操作與ArrayList幾乎一樣。
2.4仆邓、Stack
????Stack繼承自Vector鲜滩，實(shí)現(xiàn)一個后進(jìn)先出的堆棧伴鳖。Stack提供5個額外的方法使得Vector得以被當(dāng)作堆棧使用♂愎瑁基本的push和pop 方法榜聂，還有peek方法得到棧頂?shù)脑兀琫mpty方法測試堆棧是否為空嗓蘑，search方法檢測一個元素在堆棧中的位置须肆。Stack剛創(chuàng)建后是空棧。

三桩皿、Set接口

Set是一種不包括重復(fù)元素的Collection豌汇。它維持它自己的內(nèi)部排序，所以隨機(jī)訪問沒有任何意義泄隔。與List一樣瘤礁，它同樣運(yùn)行null的存在但是僅有一個。由于Set接口的特殊性梅尤，所有傳入Set集合中的元素都必須不同柜思，同時要注意任何可變對象，如果在對集合中元素進(jìn)行操作時巷燥，導(dǎo)致e1.equals(e2)==true赡盘，則必定會產(chǎn)生某些問題。實(shí)現(xiàn)了Set接口的集合有：EnumSet缰揪、HashSet陨享、TreeSet。
3.1钝腺、EnumSet
????是枚舉的專用Set抛姑。所有的元素都是枚舉類型。
3.2艳狐、HashSet
????HashSet堪稱查詢速度最快的集合定硝，因?yàn)槠鋬?nèi)部是以HashCode來實(shí)現(xiàn)的。它內(nèi)部元素的順序是由哈希碼來決定的毫目，所以它不保證set 的迭代順序蔬啡；特別是它不保證該順序恒久不變。
3.3镀虐、TreeSet
????基于TreeMap箱蟆，生成一個總是處于排序狀態(tài)的set，內(nèi)部以TreeMap來實(shí)現(xiàn)刮便。它是使用元素的自然順序?qū)υ剡M(jìn)行排序空猜，或者根據(jù)創(chuàng)建Set 時提供的 Comparator 進(jìn)行排序，具體取決于使用的構(gòu)造方法。

四辈毯、Map接口

Map與List久信、Set接口不同，它是由一系列鍵值對組成的集合漓摩，提供了key到Value的映射裙士。同時它也沒有繼承Collection。在Map中它保證了key與value之間的一一對應(yīng)關(guān)系管毙。也就是說一個key對應(yīng)一個value腿椎，所以它不能存在相同的key值，當(dāng)然value值可以相同夭咬。實(shí)現(xiàn)map的有：HashMap啃炸、TreeMap、HashTable卓舵、Properties南用、EnumMap。
4.1掏湾、HashMap
????以哈希表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)裹虫，查找對象時通過哈希函數(shù)計(jì)算其位置，它是為快速查詢而設(shè)計(jì)的融击，其內(nèi)部定義了一個hash表數(shù)組（Entry[] table）筑公，元素會通過哈希轉(zhuǎn)換函數(shù)將元素的哈希地址轉(zhuǎn)換成數(shù)組中存放的索引，如果有沖突尊浪，則使用散列鏈表的形式將所有相同哈希地址的元素串起來匣屡，可能通過查看HashMap.Entry的源碼它是一個單鏈表結(jié)構(gòu)。
4.2拇涤、TreeMap
????鍵以某種排序規(guī)則排序捣作，內(nèi)部以red-black（紅-黑）樹數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，實(shí)現(xiàn)了SortedMap接口
4.3鹅士、HashTable
????也是以哈希表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的券躁，解決沖突時與HashMap也一樣也是采用了散列鏈表的形式，不過性能比HashMap要低

五如绸、Queue

主要分為兩大類嘱朽，
????一類是阻塞式隊(duì)列，隊(duì)列滿了以后再插入元素則會拋出異常怔接，主要包括ArrayBlockQueue、PriorityBlockingQueue稀轨、LinkedBlockingQueue扼脐。
????另一種隊(duì)列則是雙端隊(duì)列，支持在頭、尾兩端插入和移除元素瓦侮，主要包括：ArrayDeque艰赞、LinkedBlockingDeque、LinkedList肚吏。

六方妖、異同點(diǎn)

6.1、Vector和ArrayList

1. vector是線程同步的罚攀，所以它也是線程安全的党觅，而arraylist是線程異步的，是不安全的斋泄。如果不考慮到線程的安全因素杯瞻，一般用arraylist效率比較高。
2. 如果集合中的元素的數(shù)目大于目前集合數(shù)組的長度時炫掐，vector增長率為目前數(shù)組長度的100%,而arraylist增長率為目前數(shù)組長度的50%.如過在集合中使用數(shù)據(jù)量比較大的數(shù)據(jù)魁莉，用vector有一定的優(yōu)勢。
3. 如果查找一個指定位置的數(shù)據(jù)募胃，vector和arraylist使用的時間是相同的旗唁，都是0(1),這個時候使用vector和arraylist都可以。而如果移動一個指定位置的數(shù)據(jù)花費(fèi)的時間為0(n-i)n為總長度痹束，這個時候就應(yīng)該考慮到使用linklist,因?yàn)樗苿右粋€指定位置的數(shù)據(jù)所花費(fèi)的時間為0(1),而查詢一個指定位置的數(shù)據(jù)時花費(fèi)的時間為0(i)逆皮。

ArrayList 和Vector是采用數(shù)組方式存儲數(shù)據(jù)，此數(shù)組元素?cái)?shù)大于實(shí)際存儲的數(shù)據(jù)以便增加和插入元素参袱，都允許直接序號索引元素电谣，但是插入數(shù)據(jù)要設(shè)計(jì)到數(shù)組元素移動等內(nèi)存操作，所以索引數(shù)據(jù)快插入數(shù)據(jù)慢抹蚀，Vector由于使用了synchronized方法（線程安全）所以性能上比ArrayList要差剿牺，LinkedList使用雙向鏈表實(shí)現(xiàn)存儲，按序號索引數(shù)據(jù)需要進(jìn)行向前或向后遍歷环壤，但是插入數(shù)據(jù)時只需要記錄本項(xiàng)的前后項(xiàng)即可晒来，所以插入數(shù)度較快！

6.2郑现、Aarraylist和Linkedlist

1. ArrayList是實(shí)現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)湃崩，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)。
2. 對于隨機(jī)訪問get和set接箫，ArrayList覺得優(yōu)于LinkedList攒读，因?yàn)長inkedList要移動指針。
3. 對于新增和刪除操作add和remove辛友，LinedList比較占優(yōu)勢薄扁，因?yàn)锳rrayList要移動數(shù)據(jù)剪返。

這一點(diǎn)要看實(shí)際情況的。若只對單條數(shù)據(jù)插入或刪除邓梅，ArrayList的速度反而優(yōu)于LinkedList脱盲。但若是批量隨機(jī)的插入刪除數(shù)據(jù)，LinkedList的速度大大優(yōu)于ArrayList. 因?yàn)锳rrayList每插入一條數(shù)據(jù)日缨，要移動插入點(diǎn)及之后的所有數(shù)據(jù)钱反。

6.3、HashMap與TreeMap

1. HashMap通過hashcode對其內(nèi)容進(jìn)行快速查找匣距，而TreeMap中所有的元素都保持著某種固定的順序面哥，如果你需要得到一個有序的結(jié)果你就應(yīng)該使用TreeMap（HashMap中元素的排列順序是不固定的）。HashMap中元素的排列順序是不固定的）墨礁。
2. HashMap通過hashcode對其內(nèi)容進(jìn)行快速查找幢竹，而TreeMap中所有的元素都保持著某種固定的順序，如果你需要得到一個有序的結(jié)果你就應(yīng)該使用TreeMap（HashMap中元素的排列順序是不固定的）恩静。集合框架”提供兩種常規(guī)的Map實(shí)現(xiàn)：HashMap和TreeMap (TreeMap實(shí)現(xiàn)SortedMap接口)焕毫。
3. 在Map 中插入、刪除和定位元素驶乾，HashMap 是最好的選擇邑飒。但如果您要按自然順序或自定義順序遍歷鍵，那么TreeMap會更好级乐。使用HashMap要求添加的鍵類明確定義了hashCode()和 equals()的實(shí)現(xiàn)疙咸。 這個TreeMap沒有調(diào)優(yōu)選項(xiàng)，因?yàn)樵摌淇偺幱谄胶鉅顟B(tài)风科。

6.4撒轮、HashTable與HashMap

1. 歷史原因:Hashtable是基于陳舊的Dictionary類的，HashMap是Java 1.2引進(jìn)的Map接口的一個實(shí)現(xiàn) 贼穆。
2. 同步性:Hashtable是線程安全的题山，也就是說是同步的，而HashMap是線程序不安全的故痊，不是同步的 顶瞳。
3. 值：只有HashMap可以讓你將空值作為一個表的條目的key或value 。

七愕秫、對集合的選擇

7.1慨菱、對List的選擇

1. 對于隨機(jī)查詢與迭代遍歷操作，數(shù)組比所有的容器都要快戴甩。所以在隨機(jī)訪問中一般使用ArrayList
2. LinkedList使用雙向鏈表對元素的增加和刪除提供了非常好的支持符喝，而ArrayList執(zhí)行增加和刪除元素需要進(jìn)行元素位移。
3. 對于Vector而已等恐，我們一般都是避免使用洲劣。
4. 將ArrayList當(dāng)做首選备蚓，畢竟對于集合元素而已我們都是進(jìn)行遍歷课蔬，只有當(dāng)程序的性能因?yàn)長ist的頻繁插入和刪除而降低時囱稽，再考慮LinkedList。

7.2二跋、對Set的選擇

1. HashSet由于使用HashCode實(shí)現(xiàn)战惊，所以在某種程度上來說它的性能永遠(yuǎn)比TreeSet要好，尤其是進(jìn)行增加和查找操作扎即。
2. 雖然TreeSet沒有HashSet性能好吞获，但是由于它可以維持元素的排序，所以它還是存在用武之地的谚鄙。

7.3各拷、對Map的選擇

1. HashMap與HashSet同樣，支持快速查詢闷营。雖然HashTable速度的速度也不慢烤黍，但是在HashMap面前還是稍微慢了些，所以HashMap在查詢方面可以取代HashTable傻盟。
2. 由于TreeMap需要維持內(nèi)部元素的順序速蕊，所以它通常要比HashMap和HashTable慢。