一.基本概念

Java容器類類庫的用途是“持有對象”抄沮，并將其劃分為兩個不同的概念：

1旦装、Collection：一個獨(dú)立元素的序列奇唤，這些元素都服從一條或者多條規(guī)則。

????List必須按照插入的順序保存元素弧满，而set不能有重復(fù)的元素。Queue按照排隊(duì)規(guī)則來確定對象產(chǎn)生的順序（通常與它們被插入的順序相同）此熬。

Collection的List庭呜、Set、Queue類圖

2犀忱、Map：一組成對的“鍵值對”對象募谎，允許你使用鍵來查找值

? ??map中也不能有相同的key，但是不同的key可以對應(yīng)相同的value阴汇。

Map容器的類圖

3数冬、上面的類圖中有幾個單獨(dú)列出的接口或者類：

Comparator

比較器接口，最重要的是compare()方法搀庶，對于容器中存儲元素item的排序（包括自定義排序等）有重要作用拐纱，如果使用的是有序容器（SortedSet、SortedMap哥倔、TreeMap）秸架，則存放的元素必須是可進(jìn)行比較的，需要實(shí)現(xiàn)Comparator接口咆蒿。

RandomAccess

隨機(jī)存取接口东抹，實(shí)現(xiàn)容器的隨機(jī)存取蚂子，如ArrayList、Vector（相當(dāng)于同步的ArrayList）等府阀。

Iterator和ListIterator

Iterator接口使用了迭代器設(shè)計模式來對所有的容器進(jìn)行快速遍歷缆镣，容器本身不需要關(guān)注存儲元素item的數(shù)據(jù)類型（具體是什么類），這些確定類型和轉(zhuǎn)型的工作由iterator負(fù)責(zé)實(shí)現(xiàn)试浙。

ListIterator是List容器所獨(dú)有的迭代器董瞻，與一般的Iterator相比，ListIterator包含add()田巴、hasPrevious()钠糊、previous()、nextIndex()等方法壹哺，能夠在遍歷過程中修改集合抄伍、逆向順序遍歷、定位遍歷索引管宵；而Iterator只能遍歷不能修改截珍、只能順向順序遍歷、不能定位索引箩朴。

Iterable

Iterable是java.lang*;包中的接口岗喉，實(shí)現(xiàn)該接口的類能后實(shí)現(xiàn)“For-each loop”，不要將其與Iterator和ListIterator迭代器混淆炸庞∏玻”For-each loop“是增強(qiáng)for循環(huán)，例如對于一個ArrayList容器的循環(huán)埠居，使用增強(qiáng)for循環(huán)能夠簡化代碼查牌，提高效率。

示例代碼如下：

迭代器與增強(qiáng)for循環(huán)遍歷

4滥壕、Collection集合接口詳細(xì)介紹

Collection是最基本的集合接口纸颜，一個Collection代表一組Object，即Collection的元素（Elements）绎橘。一些Collection允許相同的元素而另一些不行胁孙。一些能排序而另一些不行。Java SDK不提供直接繼承自Collection的類金踪，Java SDK提供的類都是繼承自Collection的“子接口”如List和Set浊洞。

collection接口主要方法

一、List接口

List是有序的Collection胡岔，使用此接口能夠精確的控制每個元素插入的位置法希。用戶能夠使用索引（元素在List中的位置，類似于數(shù)組下標(biāo)）來訪問List中的元素靶瘸，這類似于Java的數(shù)組苫亦。

實(shí)現(xiàn)List接口的常用類有LinkedList毛肋，ArrayList，Vector和Stack屋剑。

1）LinkedList類

LinkedList實(shí)現(xiàn)了List接口润匙，允許null元素。此外LinkedList提供額外的get唉匾，remove孕讳，insert方法在 LinkedList的首部或尾部。這些操作使LinkedList可被用作堆棧（stack）巍膘，隊(duì)列（queue）或雙向隊(duì)列（deque）厂财。

注意:LinkedList沒有同步方法。如果多個線程同時訪問一個List峡懈，則必須自己實(shí)現(xiàn)訪問同步璃饱。一種解決方法是在創(chuàng)建List時構(gòu)造一個同步的List：List list = Collections.synchronizedList(new LinkedList(…));

2) ArrayList類

ArrayList實(shí)現(xiàn)了可變大小的數(shù)組。它允許所有元素肪康，包括null荚恶。ArrayList沒有同步。size磷支，isEmpty谒撼，get，set方法運(yùn)行時間為常數(shù)齐唆。但是add方法開銷為分?jǐn)偟某?shù)嗤栓，添加n個元素需要O(n)的時間冻河。其他的方法運(yùn)行時間為線性箍邮。每個ArrayList實(shí)例都有一個容量（Capacity），即用于存儲元素的數(shù)組的大小叨叙。這個容量可隨著不斷添加新元素而自動增加锭弊，但是增長算法并 沒有定義。當(dāng)需要插入大量元素時擂错，在插入前可以調(diào)用ensureCapacity方法來增加ArrayList的容量以提高插入效率味滞。

和LinkedList一樣，ArrayList也是非同步的（unsynchronized）钮呀。一般情況下使用這兩個就可以了剑鞍，因?yàn)榉峭剑孕时容^高爽醋。

如果涉及到堆棧蚁署，隊(duì)列等操作，應(yīng)該考慮用List蚂四，對于需要快速插入光戈，刪除元素哪痰，應(yīng)該使用LinkedList，如果需要快速隨機(jī)訪問元素久妆，應(yīng)該使用ArrayList晌杰。

3）Vector類

Vector非常類似ArrayList，但是Vector是同步的筷弦。由Vector創(chuàng)建的Iterator肋演，雖然和ArrayList創(chuàng)建的 Iterator是同一接口，但是烂琴，因?yàn)閂ector是同步的惋啃，當(dāng)一個 Iterator被創(chuàng)建而且正在被使用，另一個線程改變了Vector的狀態(tài)（例 如监右，添加或刪除了一些元素）边灭，這時調(diào)用Iterator的方法時將拋出 ConcurrentModificationException，因此必須捕獲該 異常健盒。

4）Stack 類

Stack繼承自Vector绒瘦，實(shí)現(xiàn)一個后進(jìn)先出的堆棧。Stack提供5個額外的方法使得Vector得以被當(dāng)作堆棧使用扣癣《杳保基本的push和pop方 法，還有 peek方法得到棧頂?shù)脑馗嘎牵琫mpty方法測試堆棧是否為空该酗，search方法檢測一個元素在堆棧中的位置。Stack剛創(chuàng)建后是空棧士嚎。

2呜魄、Set接口

Set是一種不包含重復(fù)的元素的Collection，即任意的兩個元素e1和e2都有e1.equals(e2)=false莱衩，Set最多有一個null元素爵嗅。 Set的構(gòu)造函數(shù)有一個約束條件，傳入的Collection參數(shù)不能包含重復(fù)的元素笨蚁。

Set容器類主要有HashSet和TreeSet等睹晒。

1）HashSet類

Java.util.HashSet類實(shí)現(xiàn)了Java.util.Set接口。

它不允許出現(xiàn)重復(fù)元素括细；

?不保證和政集合中元素的順序

允許包含值為null的元素伪很，但最多只能有一個null元素

向set中添加元素

結(jié)果：

集合中元素打印結(jié)果

2）TreeSet?

　　TreeSet描述的是Set的一種變體——可以實(shí)現(xiàn)排序等功能的集合，它在講對象元素添加到集合中時會自動按照某種比較規(guī)則將其插入到有序的對象序列中奋单，并保證該集合元素組成的對象序列時刻按照“升序”排列锉试。

treeset添加元素

按照String的字典序排列：

運(yùn)行結(jié)果

二、Map集合接口

　　Map沒有繼承Collection接口辱匿，Map提供key到value的映射键痛。一個Map中不能包含相同的key炫彩，每個key只能映射一個 value。Map接口提供3種集合的視圖絮短，Map的內(nèi)容可以被當(dāng)作一組key集合江兢，一組value集合，或者一組key-value映射丁频。

Map集合接口方法

1杉允、Hashtable類

????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這樣的操作。

????由于作為key的對象將通過計算其散列函數(shù)來確定與之對應(yīng)的value的位置躁染，因此任何作為key的對象都必須實(shí)現(xiàn)hashCode和equals方法鸣哀。hashCode和equals方法繼承自根類Object，如果你用自定義的類當(dāng)作key的話吞彤，要相當(dāng)小心我衬，按照散列函數(shù)的定義，如果兩個對象相同饰恕，即obj1.equals(obj2)=true挠羔，則它們的hashCode必須相同，但如果兩個對象不同懂盐，則它們的hashCode不一定不同褥赊，如果兩個不同對象的hashCode相同糕档，這種現(xiàn)象稱為沖突莉恼，沖突會導(dǎo)致操作哈希表的時間開銷增大，所以盡量定義好的hashCode()方法速那，能加快哈希表的操作俐银。

　　如果相同的對象有不同的hashCode，對哈希表的操作會出現(xiàn)意想不到的結(jié)果（期待的get方法返回null）端仰，要避免這種問題捶惜，只需要牢記一條：要同時復(fù)寫equals方法和hashCode方法，而不要只寫其中一個荔烧。

２吱七、HashMap類

HashMap和Hashtable類似汽久，不同之處在于HashMap是非同步的，并且允許null踊餐，即null value和null key景醇，但是將HashMap視為Collection時（values()方法可返回Collection），其迭代子操作時間開銷和HashMap的容量成比例吝岭。因此三痰，如果迭代操作的性能相當(dāng)重要的話，不要將HashMap的初始化容量設(shè)得過高窜管，或者load factor過低散劫。

HashTable和HashMap區(qū)別

第一、繼承不同幕帆。

public classHashtable extendsDictionary implements Mappublic

class HashMap extends AbstractMap implements Map

第二获搏、Hashtable 中的方法是同步的，而HashMap中的方法在缺省情況下是非同步的失乾。

????在多線程并發(fā)的環(huán)境下颜凯，可以直接使用Hashtable，但是要使用HashMap的話就要自己增加同步處理了仗扬。

第三症概、Hashtable中，key和value都不允許出現(xiàn)null值早芭。

????在HashMap中彼城，null可以作為鍵，這樣的鍵只有一個退个；可以有一個或多個鍵所對應(yīng)的值為null募壕。當(dāng)get()方法返回null值時，即可以表示HashMap中沒有該鍵语盈，也可以表示該鍵所對應(yīng)的值為null舱馅。因此，在HashMap中不能由get()方法來判斷HashMap中是否存在某個鍵刀荒， 而應(yīng)該用containsKey()方法來判斷代嗤。

第四、兩個遍歷方式的內(nèi)部實(shí)現(xiàn)上不同缠借。

Hashtable干毅、HashMap都使用了Iterator。而由于歷史原因泼返，Hashtable還使用了Enumeration的方式 硝逢。

第五、哈希值的使用不同，HashTable直接使用對象的hashCode渠鸽。

而HashMap重新計算hash值叫乌。

第六、Hashtable和HashMap它們兩個內(nèi)部實(shí)現(xiàn)方式的數(shù)組的初始大小和擴(kuò)容的方式徽缚。

HashTable中hash數(shù)組默認(rèn)大小是11综芥，增加的方式是old*2+1。HashMap中hash數(shù)組的默認(rèn)大小是16猎拨，而且一定是2的指數(shù)膀藐。

3、WeakHashMap類?

　　WeakHashMap是一種改進(jìn)的HashMap红省，它對key實(shí)行“弱引用”额各，如果一個key不再被外部所引用，那么該key可以被GC回收吧恃。