注：以下僅個(gè)人常用集合整理香府，更多待后續(xù)學(xué)習(xí)整理

所有的集合類位于java.util包下董栽，后來為了解決并發(fā)問題，Java 5 還在Java.util.concurrent包下提供了一些線程支持的集合類企孩。

對(duì)于Set\List\Deque\Map 最常用的集合類有：
HashSet锭碳、TreeSet、ArrayList勿璃、ArrayList擒抛、ArrayDeque、LinkedList补疑、HashMap闻葵、TreeMap

一、常用集合分類

按照實(shí)現(xiàn)劃分癣丧，如圖：

image.png

按照數(shù)據(jù)結(jié)構(gòu)劃分，如圖：

image.png

下面此圖來自博友：

image.png

三 栈妆、Set不能存放重復(fù)值的原因

Set 集合訪問時(shí)胁编，是通過訪問元素本身來實(shí)現(xiàn)的厢钧。

Set本質(zhì)上與Collection沒有什么區(qū)別，主要在于Set不允許包含重復(fù)元素
（Set比較兩個(gè)對(duì)象相等是通過equals方法比較的）

四嬉橙、Set

（一）HashSet 主要特性

①不排序早直、不同步、元素可為 null
②HashSet 集合判斷添加的元素是否包含重復(fù)是通過“equals”和“hashCode” 方法返回值來判斷的市框，如果一個(gè)類只重寫了其中某一個(gè)方法霞扬，另一個(gè)方法的返回值與之不對(duì)應(yīng)，同樣也會(huì)出現(xiàn)添加了重復(fù)元素枫振。若多個(gè)元素的hashCode值相等喻圃，將會(huì)導(dǎo)致性能下降。
③采用Hash算法 決定元素的存儲(chǔ)位置粪滤，Hash算法詳見：http://www.reibang.com/p/4cb61f333b51

③結(jié)合上述特征：所以HashSet最好用于添加不可變?cè)?/p>

（二）LinkedHashSet主要特征

①它是HashSet的一個(gè)“子類”斧拍，但它是使用“鏈表”維護(hù)元素的次序，所以這個(gè)類是按照插入的順序存儲(chǔ)元素的杖小。
②需要維護(hù)元素的插入順序肆汹，因此性能略低于HashSet。

（三）TreeSet主要特征

①SortedSet的實(shí)現(xiàn)類予权，因此可以支持排序
②采用“紅黑樹”來存儲(chǔ)集合元素昂勉，支持“自然排序”和“定制排序”
③所添加的元素必須實(shí)現(xiàn)Comparable接口，因?yàn)門reeSet會(huì)調(diào)用集合元素的 o1.compareTo（Object o2）方法來判斷大猩ㄏ佟（compareTo返回0相等岗照，返回正數(shù)，o1大于o2斧账，反之小于）谴返。
④所添加元素必須是同一類型對(duì)象，否則發(fā)生ClassCastException異常咧织。
⑤當(dāng)我們重寫對(duì)應(yīng)類的equals方法時(shí)嗓袱，必須保證compareTo方法與之對(duì)應(yīng)。
⑥結(jié)合上述特征：所以TreeSet也最好用于添加不可變?cè)?/p>

（四）EnumSet

①專為枚舉類設(shè)計(jì)的集合類习绢，此類中所有元素都必須是指定枚舉類型的枚舉值
②集合元素也是有序的：以枚舉值在枚舉類中的定義順序來決定集合元素的順序渠抹。
③內(nèi)部以向量的形式存儲(chǔ)，非常緊湊闪萄、高效梧却，占用內(nèi)存小，運(yùn)行效率高败去。
④不允許添加null元素放航。

各Set實(shí)現(xiàn)類的性能分析

①HashSet的性能總是比TreeSet性能好，特別是常用的添加圆裕、查詢?cè)毓泖ⅲ驗(yàn)門reeSet需要額外的紅黑樹算法來維護(hù)集合元素的次序荆几，只有需要一個(gè)保持排序的Set時(shí)候，才使用TreeSet赊时。否則都用HashSet吨铸。
②HashSet的子類LinkedHashSet對(duì)于普通的插入、刪除操作祖秒，它比HashSet要略微慢一點(diǎn)诞吱，這是由于維護(hù)鏈表的開銷造成的，不過也因?yàn)殒湵斫叻欤闅v會(huì)更快一些房维。
③EnumSet是所有實(shí)現(xiàn)類中性能最好的，但只適用于枚舉類

最后最重要的是Set的HashSet歌馍、TreeSet和EnumSet都是線程不安全的握巢，通常可以通過Collections工具類（只是java.util包下的一個(gè)工具類）的synchronizedSortedSet方法來包裝Set集合松却，在創(chuàng)建的時(shí)候執(zhí)行：

SortedSet  s  =  Collections.synchronizedSortedSet( new  TreeSet( ....) );

五暴浦、List

List集合代表一個(gè)有序、可重復(fù)的集合晓锻，默認(rèn)按照添加順序設(shè)置元素的索引歌焦。

（一）List接口和ListIterator接口

①List是Collection的子接口
②與Set集合相比，List增加了根據(jù)索引來插入砚哆、替換和刪除集合元素的方法独撇。
③List集合判斷兩個(gè)對(duì)象相等只要通過equals方法比較返回true即可。
④與Set集合遍歷方法Iterator不同的是：List集合額外提供了一個(gè)listIterator方法躁锁，繼承自Iterator接口纷铣，提供專門操作List接口的方法，這個(gè)方法增加了向前迭代的功能：hasPrevious和previous战转，還可以add元素搜立，Iterator只能remove刪除元素。

（二）ArrayList和Vector實(shí)現(xiàn)類

①兩者都是List的典型實(shí)現(xiàn)
②基于數(shù)組槐秧，所以內(nèi)部封裝了一個(gè)動(dòng)態(tài)的啄踊、允許再分配的Object[]數(shù)組，使用initialCapacity參數(shù)來設(shè)置數(shù)組的長(zhǎng)度刁标，當(dāng)元素超過數(shù)組長(zhǎng)度時(shí)候颠通，就會(huì)自動(dòng)增加initialCapacity。
下面兩種情況可提前指定initialCapacity提高性能：
第一添加大量元素時(shí)膀懈，第二知道元素個(gè)數(shù)的時(shí)候顿锰。
③trimToSize方法用來減少集合對(duì)象占用的多于空間，調(diào)整數(shù)組長(zhǎng)度為當(dāng)前元素個(gè)數(shù)。
④ArrayList與Vector最顯著的區(qū)別在于前者是線程不安全的撵儿，但是Collections提供的一個(gè)方法能結(jié)解決這個(gè)問題乘客，所以就性能上講，淘汰Vector是必然的淀歇。

固定長(zhǎng)度的List（Arrays數(shù)組工具類）

  提供asList(Object......a)方法把一個(gè)數(shù)組或指定個(gè)數(shù)的對(duì)象轉(zhuǎn)換成一個(gè)List對(duì)象，這個(gè)對(duì)象只是Arrays的內(nèi)部類ArrayList的實(shí)例匈织。它是一個(gè)固定長(zhǎng)度的List集合浪默，程序只能遍歷訪問該集合里面的元素，不可以增加缀匕、刪除纳决，否則應(yīng)發(fā)UnsupportedOperationException異常。

*：LinkedList也是List集合的實(shí)現(xiàn)類乡小，在后面Queue集合中簡(jiǎn)述阔加。

六、Queue

Queue用于模擬隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)

（一）PriorityQueue

①一個(gè)標(biāo)準(zhǔn)的隊(duì)列實(shí)現(xiàn)類
②之所以稱之為標(biāo)準(zhǔn)：是因?yàn)樗４骊?duì)列元素的順序并不是以加入隊(duì)列的元素的順序满钟，而是按隊(duì)列元素的“大小”進(jìn)行重新排序胜榔，因襲調(diào)用peek或者poll方法取出隊(duì)列中的元素時(shí)，是取出隊(duì)列中最小的元素湃番。
③不允許插入Null值
④有兩種排序方式夭织，與TreeSet有異曲同工的特點(diǎn)。

（二）Deque接口與ArrayDeque實(shí)現(xiàn)類

①Deque是Queue接口的子接口吠撮，代表雙端隊(duì)列
②Deque不僅可以當(dāng)成雙端隊(duì)列使用尊惰，而且可以被當(dāng)成棧來使用，因?yàn)樵擃惏鰲op泥兰、push 出棧入棧兩個(gè)方法弄屡。
③Deque接口提供了一個(gè)典型的實(shí)現(xiàn)類：ArrayDeque：基于數(shù)組實(shí)現(xiàn)的雙端隊(duì)列，創(chuàng)建Deque的同時(shí)同樣可以指定一個(gè)numElements參數(shù)指定內(nèi)部數(shù)組的長(zhǎng)度鞋诗。
④ArrayList和ArrayDeque兩個(gè)集合類的實(shí)現(xiàn)機(jī)制基本 相似膀捷，它們的底層都采用一個(gè)動(dòng)態(tài)、可重新分配的Object[]數(shù)組來存儲(chǔ)集合元素师脂。
⑤程序中需要使用“椀？祝”這種數(shù)據(jù)結(jié)構(gòu)時(shí)，推薦使用ArrayDeque或者LinkedList吃警。

（三）LinkedList

①List接口糕篇、Deque接口的實(shí)現(xiàn)類，所以可根據(jù)索引訪問元素酌心，也可被當(dāng)做雙端隊(duì)列來使用拌消，自然也可以被當(dāng)做“棧”來使用。
②此類與ArrayDeque墩崩、ArrayList實(shí)現(xiàn)機(jī)制完全不同氓英，前者是以鏈表的形式保存元素，后者是數(shù)組鹦筹，所以此類隨機(jī)訪問性能較差铝阐，但插入刪除和迭代的性能非常好，原因就在于數(shù)組和鏈表這兩種數(shù)據(jù)結(jié)構(gòu)的不同铐拐。

*：對(duì)于所有基于數(shù)組實(shí)現(xiàn)的集合：使用隨機(jī)訪問的性能比使用Iterator迭代訪問的性能要好徘键。

七、Map

如果把Map的key放在一起遍蟋，就組成了一個(gè)Set集合（所有的key沒有順序吹害，不重復(fù)），keySet方法返回所有key值組成的Set對(duì)象虚青。Set和Map關(guān)系密切它呀。當(dāng)然values方法返回所有value組成的Collection集合。

事實(shí)上棒厘，Map提供了一個(gè)Entry內(nèi)部類來封裝key-value對(duì)纵穿，而計(jì)算Entry存儲(chǔ)時(shí)則只考慮Entry封裝的key，從Java源碼來看绊谭，Java是先實(shí)現(xiàn)了Map 政恍，然后通過包裝一個(gè)所有value都為null的Map就實(shí)現(xiàn)了Set集合。

如果把Map 里所有value放在一起看又類似于一個(gè)List达传，元素與元素之間可以重復(fù)篙耗，每個(gè)元素可以根據(jù)索引查找，只是Map中的索引不再使用整數(shù)值宪赶，而是以另一個(gè)對(duì)象作為索引宗弯，Map有時(shí)也被稱為字典，或關(guān)聯(lián)數(shù)組搂妻。

（一）HashMap 和Hashtable 實(shí)現(xiàn)類

①M(fèi)ap的典型實(shí)現(xiàn)類蒙保，所以大部分特性為Map特性，Hashtable從Java 1.0就開始了欲主，目前很少使用

HashMap與Hashtable的區(qū)別邓厕？
1、Hashtable是線程安全的扁瓢，所以HashMap的性能高一點(diǎn)
Hashtable底層是利用鎖住整個(gè)操作來實(shí)現(xiàn)線程安全详恼，所以在多線程情況下是串行的，這就導(dǎo)致了運(yùn)行效率非常低引几。
2昧互、Hashtable不允許使用Null值作為key，HashMap可以。

盡量少用Hashtable,即使要線程安全敞掘，也可以使用前面提到的Collections工具類的方法把HashMap變成線程安全的叽掘。

②所有的Map實(shí)現(xiàn)類都重寫了toString 方法，調(diào)用Map對(duì)象的toString方法總是返回一個(gè)類似于json字符串的數(shù)據(jù)玖雁。
③用作key的對(duì)象必須實(shí)現(xiàn)hashCode方法和equals方法更扁。

與HashSet類似的是：
④這兩個(gè)都不能保證其中key-value對(duì)的順序。
⑤判斷兩個(gè)key相等的標(biāo)準(zhǔn)也是：兩個(gè)key通過equals方法比較返回true茄菊，兩個(gè)key的hashCode返回值也相等疯潭。
⑥盡量使用不可變對(duì)象作為存儲(chǔ)元素，若要存可變?cè)孛嬷常脖仨毐ＷC元素不要被更改，否則可能引發(fā)不必要的錯(cuò)誤哭廉。

⑥判斷兩個(gè)value相等的標(biāo)準(zhǔn)更簡(jiǎn)單：只要兩個(gè)對(duì)象通過equals方法比較返回true即可脊僚。

（二）LinkedHashMap

①使用雙向鏈表來維護(hù)key-value對(duì)的次序（其實(shí)只需要考慮key的次序），該鏈表負(fù)責(zé)維護(hù)Map的迭代順序遵绰，迭代順序與key-value的插入順序保持一致辽幌，且性能較好。
②可以避免對(duì)HashMap椿访、Hashtable里的key-value對(duì)進(jìn)行排序乌企，同時(shí)又可以避免使用TreeMap所增加的成本。
③需要維護(hù)元素的插入順序成玫，因此性能略低于HashMap的性能加酵。

（三）Properties

Properties作為Hashtable類的子類，在處理屬性文件時(shí)特別方便（windows 操作平臺(tái)上的ini文件就是一種屬性文件哭当，Java中的xml文件）猪腕，此類可以把Map對(duì)象和屬性文件關(guān)聯(lián)起來，從而可以把Map對(duì)象中的key-value對(duì)寫入屬性文件中钦勘，也可以把屬性文件中的“屬性名=屬性值”加載到Map對(duì)象中陋葡。

（四）SortedMap接口和TreeMap實(shí)現(xiàn)類

正如Set接口派生出SortedSet子接口，SortedSet接口有一個(gè)TreeSet實(shí)現(xiàn)類一樣彻采，Map接口也派生出SortedMap腐缤，也有一個(gè)TreeMap實(shí)現(xiàn)類。

①TreeMap就是一個(gè)紅黑樹結(jié)構(gòu)肛响，每個(gè)key-value對(duì)即為紅黑樹的一個(gè)節(jié)點(diǎn)岭粤，在存儲(chǔ)節(jié)點(diǎn)時(shí)，需要根據(jù)key對(duì)節(jié)點(diǎn)進(jìn)行排序终惑，TreeMap是有序的绍在。
同TreeSet類似，也有兩個(gè)排序方式：
1、自然排序：所有key必須實(shí)現(xiàn)Compatable接口偿渡，而且所有key必須是同一個(gè)對(duì)象臼寄，否則會(huì)拋出ClassCastException異常。
2溜宽、定制排序：創(chuàng)建TreeMap時(shí)吉拳，傳入一個(gè)Comparator對(duì)象，該對(duì)象負(fù)責(zé)對(duì)TreeMap中所有key進(jìn)行排序适揉，采用定制排序時(shí)不要求Map的key實(shí)現(xiàn)Comparable接口留攒。

②判斷兩個(gè)key相等的標(biāo)準(zhǔn)是：兩個(gè)key通過compareTo方法返回0，和equals方法返回值為true嫉嘀，TreeMap就認(rèn)為這兩個(gè)key是相等的炼邀。
③TreeMap是有序的：所以訪問前一個(gè)、后一個(gè)剪侮、第一個(gè)拭宁、最后一個(gè)都有相應(yīng)的API。

（五）WeakHashMap實(shí)現(xiàn)類與HashMap的區(qū)別

此類的key只保留了對(duì)實(shí)際對(duì)象（字符串是強(qiáng)引用）的弱引用瓣俯，意味著當(dāng)此類對(duì)象的key所引用的對(duì)象沒有被其他強(qiáng)引用變量所引用杰标，則這些key將可能被垃圾回收，WeakHashMap也可能自動(dòng)刪除這些key所對(duì)應(yīng)的key-value對(duì)彩匕。

而HashMap的key保留了對(duì)實(shí)際對(duì)象的強(qiáng)引用腔剂，意味著只要該HashMap對(duì)象不被銷毀，該HashMap的所有key所引用的對(duì)象就不會(huì)被垃圾回收驼仪，HashMap也不會(huì)自動(dòng)刪除這些key所對(duì)應(yīng)的key-value對(duì)掸犬。

那么什么是強(qiáng)引用？什么是弱引用谅畅？詳情見：http://www.reibang.com/p/14a778168840

（六）EnumMap實(shí)現(xiàn)類

①此類中的所有key都必須是單個(gè)枚舉類的枚舉值登渣，創(chuàng)建此類時(shí)必須顯示或者隱式的指定它對(duì)應(yīng)的枚舉類。
②在內(nèi)部是以數(shù)組形式保存的毡泻，所以這種形式非常緊湊高效胜茧。
③根據(jù)key的自然順序來維護(hù)key-value對(duì)的順序
④不允許使用null值作為key，但允許使用null作為value仇味。

（七）各Map實(shí)現(xiàn)類的性能分析

①HashMap通常比Hashtable要快呻顽，因?yàn)镠ashtable需要額外的線程同步控制。
②TreeMap通常比HashMap丹墨、Hashtable要慢（尤其是插入廊遍、刪除），因?yàn)門reeMap采用紅黑樹來管理key-value鍵值對(duì)贩挣。但使用TreeMap的好處在于：TreeMap中的key-value對(duì)總是有序狀態(tài)喉前，無須專門進(jìn)行排序操作没酣，可以調(diào)用keySet()，取得key組成的Set卵迂，然后使用toArray()方法生成key的數(shù)組裕便，接下來使用Arrays的binarySearch(）方法在已 排序的數(shù)組中快速地查詢對(duì)象。
③LinkedHashMap比HashMap要慢见咒，沒什么特別出色之處
④EnumMap性能最好偿衰，但是它只能使用同一個(gè)枚舉類的枚舉值作為key。

（八）HashSet和HashMap的性能選項(xiàng)

①HashSet和HashMap都是使用hash算法來決定集合中元素的存儲(chǔ)位置（HashMap是key）改览，來控制元素的大邢卖帷（HashMap是key）
②hash表里可以存儲(chǔ)元素的位置叫作“桶”，在通常情況下宝当，單個(gè)“桶”中存儲(chǔ)一個(gè)元素视事，此時(shí)有最好的性能。
③hash算法可以根據(jù)hashCode值計(jì)算出“桶”的存儲(chǔ)位置庆揩，接著就可以從桶中取出元素郑口。
④但hash表中的狀態(tài)我open：在發(fā)生hash沖突的時(shí)候，單個(gè)桶會(huì)存儲(chǔ)多個(gè)元素盾鳞，這些元素就會(huì)以鏈表的形式存儲(chǔ)，必須按照順序搜索瞻离。
⑤hash表包含如下屬性：
1腾仅、容量(capacity)：hash表中桶的數(shù)量
2、初始化容量（initial capacity）:創(chuàng)建hash表時(shí)桶的數(shù)量套利，HashMap和HashSet都允許在構(gòu)造器中指定初始化容量推励。
3、尺寸（size）：當(dāng)前hash表中記錄的數(shù)量肉迫。
4验辞、負(fù)載因子（load factory）：負(fù)載因子 = size/capacity，輕負(fù)載的hash表具有沖突少喊衫、適宜查詢與插入的特點(diǎn)（但是Iterator遍歷較慢）
⑥負(fù)載極限：范圍0~1跌造，決定了hash表的最大填滿程度，hash表會(huì)自動(dòng)成倍的增加桶的數(shù)量族购，稱為“rehashing”壳贪，默認(rèn)為0.75，也就是當(dāng)該hash表的3/4被填滿的時(shí)候寝杖，就會(huì)發(fā)生“rehashing”

為什么是0.75违施？

較高會(huì)降低hash表占用的內(nèi)存空間，但會(huì)增加查詢數(shù)據(jù)的時(shí)間開銷瑟幕，當(dāng)然對(duì)于時(shí)間效率和占用內(nèi)存可以根據(jù)實(shí)際情況進(jìn)行調(diào)整磕蒲。

最后提及一個(gè)操作集合的工具類：Collections

該工具類提供了大量的方法對(duì)集合元素進(jìn)行排序留潦、查詢和修改等操作，還提供將集合設(shè)置為不可變辣往、對(duì)集合實(shí)現(xiàn)同步控制等方法兔院。具體見API文檔。