對(duì)象的集合
如果程序的對(duì)象數(shù)量有限，且壽命可知，那么這個(gè)程序是相當(dāng)簡(jiǎn)單的。

數(shù)組
數(shù)組與其它容器的區(qū)別體現(xiàn)在三個(gè)方面：效率，類(lèi)型識(shí)別以及可以持有primitives。數(shù)組是Java提供的，能隨機(jī)存儲(chǔ)和訪(fǎng)問(wèn)reference序列的諸多方法中的，最高效的一種。數(shù)組是一個(gè)簡(jiǎn)單的線(xiàn)性序列，所有它可以快速的訪(fǎng)問(wèn)其中的元素。但是速度是有代價(jià)的；當(dāng)你創(chuàng)建了一個(gè)數(shù)組之后，它的容量就固定了，而且在其生命周期里不能改變。也許你會(huì)提議先創(chuàng)建一個(gè)數(shù)組，等到快不夠用的時(shí)候，再創(chuàng)建一個(gè)新的，然后將舊的數(shù)組里的reference全部導(dǎo)到新的里面。其實(shí)（我們以后會(huì)講的）ArrayList就是這么做的。但是這種靈活性所帶來(lái)的開(kāi)銷(xiāo)，使得ArrayList的效率比起數(shù)組有了明顯下降。
Java對(duì)數(shù)組和容器都做邊界檢查；如果過(guò)了界，它舊會(huì)給一個(gè)RuntimeException。這種異常表明這個(gè)錯(cuò)誤是由程序員造成的，這樣你就用不著再在程序里面檢查了。
還有一些泛型容器類(lèi)包括List，Set和Map。他們處理對(duì)象的時(shí)候就好像這些對(duì)象都沒(méi)有自己的具體類(lèi)型一樣。也就是說(shuō)，容器將它所含的元素都看成是（Java中所有類(lèi)的根類(lèi)）Object的。這樣你只需要建一種容器，就能把所有類(lèi)型的對(duì)象全都放進(jìn)去。從這個(gè)角度來(lái)看，這種做法很不錯(cuò)（只是苦了 primitive。如果是常量，你還可以用Java的primitive的Wrapper類(lèi)；如果是變量，那就只能放在你自己的類(lèi)里了）。與其他泛型容器相比，這里體現(xiàn)數(shù)組的第二革優(yōu)勢(shì)：創(chuàng)建數(shù)組的時(shí)候，你也同時(shí)指明了它所持有的對(duì)象的類(lèi)型（這又引出了第三點(diǎn)－－數(shù)組可以持有primitives，而容器卻不行）。也就是說(shuō)，它會(huì)在編譯的時(shí)候作類(lèi)型檢查，從而防止你插入錯(cuò)誤類(lèi)型的對(duì)象，或者是在提取對(duì)象的時(shí)候把對(duì)象的類(lèi)型給搞錯(cuò)了。Java在編譯和運(yùn)行時(shí)都能阻止你將一個(gè)不恰當(dāng)?shù)南鹘o對(duì)象。所有這并不是說(shuō)使用容器就有什么危險(xiǎn)，只是如果編譯器能夠幫你指定，那么程序運(yùn)行會(huì)更快，最終用戶(hù)也會(huì)較少收到程序運(yùn)行異常的騷擾。
從效率和類(lèi)型檢查的角度來(lái)看，使用數(shù)組總是沒(méi)錯(cuò)的。但是，如果你在解決一個(gè)更為一般的問(wèn)題，那數(shù)組就會(huì)顯得功能太弱了點(diǎn)。

數(shù)組是第一流的對(duì)象
不管你用的是那種類(lèi)型的數(shù)組，數(shù)組的標(biāo)識(shí)符實(shí)際上都是一個(gè)“創(chuàng)建在堆（heap）里的實(shí)實(shí)在在的對(duì)象的”reference。實(shí)際上是那個(gè)對(duì)象持有其他對(duì)象的reference。你即可以用數(shù)組的初始化語(yǔ)句，隱含地創(chuàng)建這個(gè)對(duì)象，也可以用new表達(dá)式，明確地創(chuàng)建這個(gè)對(duì)象，只讀的length屬性能告訴你數(shù)組能存儲(chǔ)多少元素。它是數(shù)組對(duì)象的一部分（實(shí)際上也是你唯一能訪(fǎng)問(wèn)的屬性或方法）。‘[]’語(yǔ)法是另一條訪(fǎng)問(wèn)數(shù)組對(duì)象的途徑。
你沒(méi)法知道數(shù)組里面究竟放了多少元素，因?yàn)閘ength只是告訴你數(shù)組能放多少元素，也就是說(shuō)是數(shù)組對(duì)象的容量，而不是它真正已經(jīng)持有的元素的數(shù)量。但是，創(chuàng)建數(shù)組對(duì)象的時(shí)候，它所持有的reference都會(huì)被自動(dòng)地初始化為null，所以你可以通過(guò)檢查數(shù)組的某個(gè)“槽位”是否為null，來(lái)判斷它是否持有對(duì)象。以此類(lèi)推，primitive的數(shù)組，會(huì)自動(dòng)來(lái)數(shù)字初始化為零，字符初始化為(char)0，boolean初始化為false。

primitive容器
容器類(lèi)只能持有Object對(duì)象的reference。而數(shù)組除了能持有Objects的reference之外，還可以直接持有primitive。當(dāng)然可以使用諸如Integer，Double之類(lèi)的wrapper類(lèi)。把primitive的值放到容器中，淡這樣總有點(diǎn)怪怪的。此外， primitive數(shù)組的效率要比wrapper類(lèi)容器的高出許多。
當(dāng)然，如果你使用primitive的時(shí)候，還需要那種“能隨需要自動(dòng)擴(kuò)展的”容器類(lèi)的靈活性，那就不能用數(shù)組了。你只能用容器來(lái)存儲(chǔ)primitive的wrapper類(lèi)。

返回一個(gè)數(shù)組
假設(shè)你寫(xiě)了一個(gè)方法，它返回的不是一個(gè)而是一組東西。那么在Java中就可以返回的“就是一個(gè)數(shù)組”。與C++不同，你永遠(yuǎn)也不必為Java的數(shù)組操心－－只要你還需要它，它就還在；一旦你用完了，垃圾回收器會(huì)幫你把它打掃干凈。

Arrays類(lèi)
java.util里面有一個(gè)Arrays類(lèi)，它包括了一組可用于數(shù)組的static方法，這些方法都是一些實(shí)用工具。其中有四個(gè)基本方法：用來(lái)比較兩個(gè)數(shù)組是否相等的equals()；用來(lái)填充的fill()；用來(lái)對(duì)數(shù)組進(jìn)行排序的sort()；以及用于在一個(gè)已排序的數(shù)組中查找元素的 binarySearch()。所有這些方法都對(duì)primitive和Object進(jìn)行了重載。此外還有一個(gè)asList()方法，它接受一個(gè)數(shù)組，然后把它轉(zhuǎn)成一個(gè)List容器。
雖然Arrays還是有用的，但它的功能并不完整。舉例來(lái)說(shuō)，如果它能讓我們不用寫(xiě)for循環(huán)就能直接打印數(shù)組，那就好了。此外，正如你所看到的fill()只能用一個(gè)值填數(shù)組。所以，如果你想把隨即生成的數(shù)字填進(jìn)數(shù)組的話(huà)，fill()是無(wú)能為力的。

復(fù)制一個(gè)數(shù)組
Java標(biāo)準(zhǔn)類(lèi)庫(kù)提供了一個(gè)System.arraycopy()的static方法。相比f(wàn)or循環(huán)，它能以更快的速度拷貝數(shù)組。System.arraycopy()對(duì)所有類(lèi)型都作了重載。
對(duì)象數(shù)組和primitive數(shù)組都能拷貝。但是如果你拷貝的是對(duì)象數(shù)組，那么你只拷貝了它們的reference－－對(duì)象本身不會(huì)被拷貝。這被成為淺拷貝（shallow copy）。

數(shù)組的比較
為了能比較數(shù)組是否完全相等，Arrays提供了經(jīng)重載的equals()方法。當(dāng)然，也是針對(duì)各種primitive以及Object的。兩個(gè)數(shù)組要想完全相等，他們必須有相同數(shù)量的元素，而且數(shù)組的每個(gè)元素必須與另一個(gè)數(shù)組的相對(duì)應(yīng)的位置上的元素相等。元素的相等姓，用equals()判斷。（對(duì)于 primitive，它會(huì)使用其wrapper類(lèi)的equals()；比如int使用Integer.equals()。）。

數(shù)組元素的比較
Java里面有兩種能讓你實(shí)現(xiàn)比較功能的方法。一是實(shí)現(xiàn)java.lang.Comparable接口，并以此實(shí)現(xiàn)類(lèi)“自有的”比較方法。這是一個(gè)很簡(jiǎn)單的接口，它只有一個(gè)方法compareTo()。這個(gè)方法能接受另一個(gè)對(duì)象作為參數(shù)，如果現(xiàn)有對(duì)象比參數(shù)小，它就會(huì)返回一個(gè)負(fù)數(shù)，如果相同則返回零，如果現(xiàn)有的對(duì)象比參數(shù)大，它就返回一個(gè)正數(shù)。
static randInt()方法會(huì)生成一個(gè)介于0到100之間的正數(shù)。
現(xiàn)在架設(shè)，有人給你一個(gè)沒(méi)有實(shí)現(xiàn)Comparable接口的類(lèi)，或者這個(gè)類(lèi)實(shí)現(xiàn)了Comparable接口，但是你發(fā)現(xiàn)它的工作方式不是你所希望的，于是要重新定義一個(gè)新的比較方法。Java沒(méi)有強(qiáng)求你一定要把比較代碼塞進(jìn)類(lèi)里，它的解決方案是使用“策略模式（strategy design pattern）”。有了策略之后，你就能把會(huì)變的代碼封裝到它自己的類(lèi)里（即所謂的策略對(duì)象strategy object）。你把策略對(duì)象交給不會(huì)變的代碼，然后用它運(yùn)用策略完成整個(gè)算法。這樣，你就可以用不同的策略對(duì)象來(lái)表示不同的比較方法，然后把它們都交給同一個(gè)排序程序了。接下來(lái)就要“通過(guò)實(shí)現(xiàn)Comparator接口”來(lái)定義策略對(duì)象了。這個(gè)接口有兩個(gè)方法compare()和equals()。但是除非是有特殊的性能要求，否則你用不著去實(shí)現(xiàn)equals()。因?yàn)橹灰穷?lèi)，它就都隱含地繼承自O(shè)bject，而Object里面已經(jīng)有了一個(gè) equals()了。所以你盡可以使用缺省的Object的equals()，這樣就已經(jīng)滿(mǎn)足接口的要求了。
Collections類(lèi)里專(zhuān)門(mén)有一個(gè)會(huì)返回與對(duì)象自有的比較法相反的Comparator的方法。它能很輕易地被用到CompType上面。
Collections.reverseOrder()返回了一個(gè)Comparator的reference。
compare()方法會(huì)根據(jù)第一個(gè)參數(shù)是小于，等于還是大于第二個(gè)參數(shù)，分別返回負(fù)整數(shù)，零或是正整數(shù)。

數(shù)組的排序
有了內(nèi)置的排序方法之后，你就能對(duì)任何數(shù)組排序了，不論是primitive的還是對(duì)象數(shù)組的，只要它實(shí)現(xiàn)了Comparable接口或有一個(gè)與之相關(guān)的Comparator對(duì)象就行了。
Java標(biāo)準(zhǔn)類(lèi)庫(kù)所用的排序算法已經(jīng)作了優(yōu)化－－對(duì)primitive，它用的是“快速排序（Quicksort）”，對(duì)對(duì)象，它用的是“穩(wěn)定合并排序（stable merge sort）”。所以除非是prolier表明排序算法是瓶頸，否則你不用為性能擔(dān)心。

查詢(xún)有序數(shù)組
一旦數(shù)組排完序，你就能用Arrays.binarySearch()進(jìn)行快速查詢(xún)了。但是切忌對(duì)一個(gè)尚未排序的數(shù)組使用binarySearch()；因?yàn)檫@么做的結(jié)果是沒(méi)意義的。
如果Arrays.binarySearch()找到了，它就返回一個(gè)大于或等于0的值。否則它就返回一個(gè)負(fù)值，而這個(gè)負(fù)值要表達(dá)的意思是，如果你手動(dòng)維護(hù)這個(gè)數(shù)組的話(huà)，這個(gè)值應(yīng)該插在哪個(gè)為止。這個(gè)值就是：
-(插入點(diǎn))-1
“插入點(diǎn)”就是，在所有“比要找的那個(gè)值”更大值中，最小的那個(gè)值的下標(biāo)，或者，如果數(shù)組中所有的值都比要找的值小，它就是a.size()。
如果數(shù)組里面有重復(fù)元素，那它不能保證會(huì)返回哪一個(gè)。這個(gè)算法不支持重復(fù)元素，不過(guò)它也不報(bào)錯(cuò)。所以，如果你需要的是一個(gè)無(wú)重復(fù)元素的有序序列的話(huà)，那么可以考慮使用本章后面所介紹的TreeSet（支持【排序順序“sorted order”】）和LinkedHashSet（支持【插入順序“sorted order”】）。這兩個(gè)類(lèi)會(huì)幫你照看所有細(xì)節(jié)。只有在遇到性能瓶頸的時(shí)候，你才應(yīng)該用手動(dòng)維護(hù)的數(shù)組來(lái)代替這兩個(gè)類(lèi)。
如果排序的時(shí)候用到了Comparator（針對(duì)對(duì)象數(shù)組，primitive數(shù)組不允許使用Comparator），那么binarySearch()的時(shí)候，也必須使用同一個(gè)Comparator（用這個(gè)方法的重載版）。

數(shù)組部分的總結(jié)
總而言之，如果你要持有一組對(duì)象，首選，同時(shí)也是效率最高的選擇，應(yīng)該是數(shù)組。而且，如果這是一組primitive的話(huà)，你也只能用數(shù)組。還有一些更為一般的情況，也就是寫(xiě)程序的時(shí)候還不知道要用多少對(duì)象，或者要用一種更復(fù)雜方式來(lái)存儲(chǔ)對(duì)象情況。為此，Java提供了“容器類(lèi)（container class）”。其基本類(lèi)型有List，Set和Map。
它們還有一些別的特性。比方說(shuō)Set所持有的對(duì)象，個(gè)個(gè)都不同，Map則是一個(gè)“關(guān)聯(lián)性數(shù)組（associative array）”，它能在兩個(gè)對(duì)象之間建立聯(lián)系。此外，與數(shù)組不同，它們還能自動(dòng)調(diào)整大小，所以你可以往里面放任意數(shù)量的對(duì)象。

容器簡(jiǎn)介
Java2的重新設(shè)計(jì)了1.0和1.1里面那個(gè)表現(xiàn)差勁的容器類(lèi)。新的設(shè)計(jì)更緊湊也更合理。同時(shí)它也補(bǔ)齊了容器類(lèi)庫(kù)的功能，提供了鏈表（linked list），隊(duì)列（queue）和雙向隊(duì)列（deques，讀成“decks”）這幾種數(shù)據(jù)結(jié)構(gòu)的功能。
Java2的容器類(lèi)要解決“怎樣持有對(duì)象”，而它把這個(gè)問(wèn)題分成兩類(lèi)：
1。Collection：通常是一組有一定規(guī)律的獨(dú)立元素。List必須按照特定的順序持有這些元素，而Set則不能保存重復(fù)的元素。（bag沒(méi)有這個(gè)限制，但是Java的容器類(lèi)庫(kù)沒(méi)有實(shí)現(xiàn)它，因?yàn)長(zhǎng)ist已經(jīng)提供這種功能了）
2。Map：一組以“鍵－－值”（key-value）形式出現(xiàn)的pair。初看上去，它應(yīng)該是一個(gè)pair的Collection，但是真這么去做的話(huà)，它就會(huì)變得很滑稽，所以還是把這個(gè)概念獨(dú)立列出來(lái)為好。退一步說(shuō)，真的要用到Map的某個(gè)自己的時(shí)候，創(chuàng)建一個(gè)Collection也是很方便的。 Map可以返回“鍵（key）的”Set，值的Collection，或者pair的Set。和數(shù)組一樣，Map不需要什么修改，就能很容易地?cái)U(kuò)展成多維。你只要直接把Map的值設(shè)成Map就可以了（然后它的值再是Map，依此類(lèi)推）。
Java的容器類(lèi)分成兩種基本類(lèi)型。它們的區(qū)別就在，每個(gè)位置能放多少對(duì)象。Collection只允許每個(gè)位置上放一個(gè)對(duì)象（這個(gè)名字有點(diǎn)誤導(dǎo)，因?yàn)槿萜黝?lèi)庫(kù)也常被統(tǒng)稱(chēng)為collections）。它包括“以一定順序持有一組對(duì)象”的List，以及“只能允許添加不重復(fù)的對(duì)象”的Set。 ArrayList是一種List，而HashSet則是一種Set。你可以用add()方法往Collection里面加對(duì)象。
Map保存的是“鍵（key）－－值”形式的pair，很像是一個(gè)微型數(shù)據(jù)庫(kù)。
Map又被稱(chēng)為關(guān)聯(lián)性數(shù)組（associative array）。你可以用put()方法往Map里面加元素。它接受鍵－－值形式pair作參數(shù)。
fill()方法還為Collection和Map作了重載。輸出在默認(rèn)情況下使用容器類(lèi)的toString()方法。打印出來(lái)的Collection會(huì)用方括號(hào)括起來(lái)，元素與元素之間用逗號(hào)分開(kāi)。Map會(huì)用花括號(hào)括起來(lái)，鍵和值之間用等號(hào)聯(lián)起來(lái)（鍵在左邊，值在右邊）。
List會(huì)老老實(shí)實(shí)地持有你所輸入的所有對(duì)象，既不做排序也不做編輯。Set則每個(gè)對(duì)象只接受一次，而且還要用它自己的規(guī)則對(duì)元素進(jìn)行重新排序（一般情況下，你關(guān)心的只是Set包沒(méi)包括某個(gè)對(duì)象，而不是它到底排在哪里－－如果是那樣，你最好還是用List）。而Map也不接收重復(fù)的pair，至于是不是重復(fù)，要由key來(lái)決定。此外，它也有它自己的內(nèi)部排序規(guī)則，不會(huì)受輸入順序影響。如果插入順序是很重要的，那你就只能使用LinkedHashSet或 LinkedHashMap了。

填充容器
和Arrays一樣，Collection也有一個(gè)叫Collections的輔助類(lèi)，它包含了一些靜態(tài)的實(shí)用工具方法，其中就有一個(gè)fill()。這個(gè) fill()也只是把同一個(gè)對(duì)象的reference復(fù)制到整個(gè)容器，而且它還只能為L(zhǎng)ist，不能為Set和Map工作。

容器的缺點(diǎn)：不知道對(duì)象的類(lèi)型
Java的容器有個(gè)缺點(diǎn)，就是往容器里面放對(duì)象的時(shí)候，會(huì)把對(duì)象的類(lèi)型信息給弄丟了。這是因?yàn)殚_(kāi)發(fā)容器類(lèi)的程序員不會(huì)知道你要用它來(lái)保存什么類(lèi)型的對(duì)象，而讓容器僅只保存特定類(lèi)型的對(duì)象又會(huì)影響它的通用性。所以容器被做成只有持有Object，也就是所有對(duì)象的根類(lèi)的reference，這樣它就能持有任何類(lèi)型的對(duì)象了。（當(dāng)然不包括primitive，因?yàn)樗鼈儾皇菍?duì)象，也沒(méi)有繼承別的對(duì)象。）這是一個(gè)很了不起的方案，只是：
1，由于在將對(duì)象放入容器的時(shí)候，它的類(lèi)型信息被扔掉了，所以容器對(duì)“能往里面加什么類(lèi)型的對(duì)象”沒(méi)有限制。比方說(shuō)，即使你想讓它只持有cat，別人也能很輕易地把dog放進(jìn)去。
2，由于對(duì)象的類(lèi)型信息沒(méi)了，容器只知道它持有的Object的reference，所以對(duì)象在使用之前還必須進(jìn)行類(lèi)型轉(zhuǎn)換。
好的一面是，Java不會(huì)讓你誤用放進(jìn)容器里的對(duì)象。假設(shè)你往cat的容器里面扔了個(gè)dog，然后要把這個(gè)容器里的所有對(duì)象都當(dāng)cat來(lái)用，當(dāng)你把dog 的reference從cat的容器里面拉出來(lái)，并且試圖將它轉(zhuǎn)換成cat的時(shí)候，就會(huì)引發(fā)一個(gè)RuntimeException。
ArrayList的用法也是很簡(jiǎn)單：先創(chuàng)建一個(gè)，用add()把對(duì)象放進(jìn)去，要用的時(shí)候再給get()傳一個(gè)下標(biāo)－－就跟用數(shù)組差不多，只是不需要用方括號(hào)了。ArrayList也有一個(gè)size()方法，它會(huì)告訴你容器里面有多少對(duì)象，這樣你就不會(huì)粗心大意地過(guò)了界然后引發(fā)異常了。

有時(shí)即使不正確它也能運(yùn)行
有時(shí)，即使不把對(duì)象轉(zhuǎn)換成原先的類(lèi)型，它好像也能正常工作。有一種情況比較特殊：String能從編譯器哪里得到一些能使之平穩(wěn)工作的特殊幫助。只要編譯器沒(méi)能得到它所期望的String對(duì)象，它就會(huì)調(diào)用toString()。這個(gè)方法油Object定義，能被任何Java類(lèi)覆寫(xiě)。它所返回的String 對(duì)象，會(huì)被用到任何要用它的地方。
于是只要覆寫(xiě)了類(lèi)的toString()方法，你就能打印對(duì)象了。

做一個(gè)類(lèi)型敏感的ArrayList

參數(shù)化類(lèi)型（Parameterized types）

迭代器
無(wú)論是哪種容器，你都得有辦法既能放東西進(jìn)去，也能拿東西出來(lái)。畢竟，容器的主要任務(wù)就是存放對(duì)象。ArrayList的add()就是用來(lái)放東西的，而 get()則是把對(duì)象拿出來(lái)的辦法。ArrayList恨靈活；你可以隨時(shí)提取任何東西，并且換一個(gè)下標(biāo)，馬上就能選擇另一個(gè)元素。
“迭代器（iterator 又是一個(gè)設(shè)計(jì)模式）”是一個(gè)對(duì)象，它的任務(wù)是，能在讓“客戶(hù)程序在不知道，或者不關(guān)心他所處理的是什么樣的底層序列結(jié)構(gòu)”的情況下，就能在一個(gè)對(duì)象序列中前后移動(dòng)，并選取其中的對(duì)象。此外迭代器還是一種通常所說(shuō)的“輕量級(jí)”的對(duì)象，既創(chuàng)建代價(jià)很小的對(duì)象。
Java的Iterator就屬于有這種限制的迭代器。它做不了很多事情，除了：
1，用iterator()方法叫容器傳給你一個(gè)Iterator對(duì)象。第一次調(diào)用Iterator的next()方法的時(shí)候，它就會(huì)傳給你序列中的第一個(gè)元素。
2，用next()方法獲取序列中的下一個(gè)對(duì)象。
3，用hasNext()方法查詢(xún)序列中是否還有其他對(duì)象。
4，用remove()方法刪除迭代器所返回的最后一個(gè)元素。
就這么多了。這只是迭代器的一個(gè)恨簡(jiǎn)單的實(shí)現(xiàn)，不過(guò)還是很強(qiáng)大（對(duì)List來(lái)說(shuō)，還有一個(gè)更精巧的ListIterator）。

不經(jīng)意的遞歸（Unintended recursion）
由于Java的標(biāo)準(zhǔn)容器類(lèi)（同其它類(lèi)一樣）也是繼承Object的，因此它們也有一個(gè)toString()方法。這個(gè)方法已經(jīng)被覆寫(xiě)了，所以它能生成一個(gè)表示它自己以及所有它所保存的對(duì)象的String。比如ArrayList的toString()方法就會(huì)遍歷ArrayList的每個(gè)元素，然后調(diào)用它們的toString()方法。假設(shè)你要打印類(lèi)的地址。好像最直接的辦法就是使用this。但是會(huì)出現(xiàn)很多異常，解決的辦法就是去調(diào)用Object的 toString()方法，它就是干這活的。所以不要用this，應(yīng)該寫(xiě)super.toString()。

容器分類(lèi)學(xué)
根據(jù)編程的需要，Collection和Map分別有好幾個(gè)實(shí)現(xiàn)。實(shí)際上只有三種容器組件－－Map，List和Set，而每種又有兩到三個(gè)實(shí)現(xiàn)。
與存放對(duì)象有關(guān)的接口包括Collection, List, Set和Map。在理想情況下，絕大多數(shù)代碼應(yīng)該只同這些接口打交道，只是在創(chuàng)建容器的時(shí)候才要精確地指明它的確切類(lèi)型。
add()，就像它的名字告訴我們的，會(huì)把新的元素放進(jìn)Collection。但是文檔里面特別仔細(xì)地聲明，“add()會(huì)確保容器包含指定的元素”。這句話(huà)是說(shuō)給Set的，因?yàn)樗惶砑釉葲](méi)有的元素，對(duì)ArrayList或其他List，add()總是“把它放進(jìn)去”，因?yàn)長(zhǎng)ist并不關(guān)心它是不是保存了相同的元素。
Collection都能用iterator()方法產(chǎn)生一個(gè)Iterator。這里，我們用Iterator來(lái)遍歷整個(gè)Collection，然后把他們打印出來(lái)。

Collection的功能
下面這張表給出了Collection的所有功能，也就是你能用Set和List做什么事（不包括從Object自動(dòng)繼承過(guò)來(lái)的方法）。（List還有一些額外的功能。）Map不是繼承Collection的，所以我們會(huì)區(qū)別對(duì)待。

boolean add(Object)：確保容器能持有你傳給它的那個(gè)參數(shù)。如果沒(méi)有把它加進(jìn)去，就返回false。（這是個(gè)“可選”的方法，本章稍后會(huì)再作解釋。）
boolean addAll(Collection)：加入?yún)?shù)Collection所含的所有元素。只要加了元素，就返回true。
void clear()：清除容器所保存的所有元素。（“可選”）
boolean contains(Object)：如果容器持有參數(shù)Object，就返回true。
boolean containsAll(Collection)：如果容器持有參數(shù)Collection所含的全部元素，就返回true。
boolean isEmpty()：如果容器里面沒(méi)有保存任何元素，就返回true。
Iterator iterator()：返回一個(gè)可以在容器的各元素之間移動(dòng)的Iterator。
boolean removeAll(Collection)：刪除容器里面所有參數(shù)Collection所包含的元素。只要?jiǎng)h過(guò)東西，就返回true。（“可選”）
boolean retainAll(Collection)：只保存參數(shù)Collection所包括的元素（集合論中“交集”的概念）。如果發(fā)生過(guò)變化，則返回true。（“可選”）
int size()：返回容器所含元素的數(shù)量。
Object[] toArray()：返回一個(gè)包含容器中所有元素的數(shù)組。
Object[] toArray(Object[] a)：返回一個(gè)包含容器中所有元素的數(shù)組，且這個(gè)數(shù)組不是普通的Object數(shù)組，它的類(lèi)型應(yīng)該同參數(shù)數(shù)組a的類(lèi)型相同（要做類(lèi)型轉(zhuǎn)換）。
注意，這里沒(méi)有能進(jìn)行隨機(jī)訪(fǎng)問(wèn)的get()方法。這是因?yàn)镃ollection還包括Set。而Set有它自己的內(nèi)部順序（因此隨即訪(fǎng)問(wèn)事毫無(wú)意義的）。所以如果你要檢查Collection的元素，你就必須使用迭代器。
接下來(lái)講List, Set和Map的各種實(shí)現(xiàn)了，每講一種容器，我都會(huì)（用星號(hào)）告訴你默認(rèn)情況下應(yīng)該選用哪種實(shí)現(xiàn)。

List的功能
List的基本用法事相當(dāng)將但的。雖然絕大多數(shù)時(shí)候，你只是用add()加對(duì)象，用get()取對(duì)象，用iterator()獲取這個(gè)序列的Iterator，但List還有一些別的很有用的方法。
實(shí)際上有兩種List：擅長(zhǎng)對(duì)元素進(jìn)行隨機(jī)訪(fǎng)問(wèn)的，較常用的ArrayList，和更強(qiáng)大的LinkedList。LinkedList不是為快速的隨機(jī)訪(fǎng)問(wèn)而設(shè)計(jì)的，但是它卻有一組更加通用的方法。
Lisk（接口）：List的最重要的特征就是有序；它會(huì)確保以一定的順序保存元素。List在Collection的基礎(chǔ)上添加了大量方法，使之能在序列中間插入和刪除元素。（只對(duì)LinkedList推薦使用。）List可以制造ListIterator對(duì)象，你除了能用它在List的中間插入和刪除元素之外，還能用它沿兩個(gè)方法遍歷List。
ArrayList*：一個(gè)用數(shù)組實(shí)現(xiàn)的List。能進(jìn)行快速的隨機(jī)訪(fǎng)問(wèn)，但是往列表中間插入和刪除元素的時(shí)候比較慢。ListIterator只能用在反向遍歷ArrayList的場(chǎng)合，不要用它來(lái)插入和刪除元素，因?yàn)橄啾萀inkedList，在ArrayList里面用ListIterator的系統(tǒng)開(kāi)銷(xiāo)比較高。
LinkedList：對(duì)順序訪(fǎng)問(wèn)進(jìn)行了優(yōu)化。在List中間插入和刪除元素的代價(jià)也不高。隨機(jī)訪(fǎng)問(wèn)的速度相對(duì)較慢。（用ArrayList吧。）此外它還有addFirst()，addLast()，getFirst()，getLast()，removeFirst()和removeLast()等方法（這些方法，接口和基類(lèi)均未定義），你能把它當(dāng)成棧（stack），隊(duì)列（queue）或雙向隊(duì)列（deque）來(lái)用。
記住，容器只是一個(gè)存儲(chǔ)對(duì)象的盒子。如果這個(gè)笑盒子能幫你解決所有的問(wèn)題，那你就用不著取管它事怎么實(shí)現(xiàn)的（在絕大多數(shù)情況下，這是使用對(duì)象的基本概念）。如果開(kāi)發(fā)環(huán)境里面還有一些別的，會(huì)造成固定的性能開(kāi)銷(xiāo)的因素存在，那么ArrayList和LinkedList之間的性能差別就會(huì)變得不那么重要了。你只需要它們中的一個(gè)，你甚至可以想象有這樣一種“完美”的抽象容器；它能根據(jù)用途，自動(dòng)地切換其底層的實(shí)現(xiàn)。

用LinkedList做一個(gè)棧
“棧（stack）”有時(shí)也被稱(chēng)為“后進(jìn)先出”（LIFO）的容器。就是說(shuō)，最后一個(gè)被“壓”進(jìn)棧中的東西，會(huì)第一個(gè)“彈”出來(lái)。同其他Java容器一樣，壓進(jìn)去和彈出來(lái)的東西都是Object，所以除非你只用Object的功能，否則就必須對(duì)彈起來(lái)的東西進(jìn)行類(lèi)型轉(zhuǎn)換。
LinkedList的方法能直接實(shí)現(xiàn)棧的功能，所以你完全可以不寫(xiě)Stack而直接使用LinkedList。
如果你只想要棧的功能，那么繼承就不太合適了，因?yàn)槔^承出來(lái)的是一個(gè)擁有LinkedList的所有方法的類(lèi)。

用LinkedList做一個(gè)隊(duì)列
隊(duì)列（queue）是一個(gè)“先進(jìn)先出”（FIFO）容器。也就是，你把一端把東西放進(jìn)去，從另一端把東西取出來(lái)。所以你放東西的順序也就是取東西的順序。LinkedList有支持隊(duì)列的功能的方法，所以它也能被當(dāng)作Queue來(lái)用。
還能很輕易地用LinkedList做一個(gè)deque（雙向隊(duì)列）。它很像隊(duì)列，只是你可以從任意一端添加和刪除元素。

Set的功能
Set的接口就是Collection的，所以不像那兩個(gè)List，它沒(méi)有額外的功能。實(shí)際上Set確確實(shí)實(shí)就是一個(gè)Collection－－只不過(guò)行為方式不同罷了。（這是繼承和多態(tài)性的完美運(yùn)用：表達(dá)不同地行為。）Set會(huì)拒絕持有多個(gè)具有相同值的對(duì)象的實(shí)例（對(duì)象的“值”又是由什么決定的呢？這個(gè)問(wèn)題比較復(fù)雜，我們以后會(huì)講）。
Set（接口）：加入Set的每個(gè)元素必須是唯一的；否則，Set是不會(huì)把它加進(jìn)去的。要想加進(jìn)Set，Object必須定義equals()，這樣才能標(biāo)明對(duì)象的唯一性。Set的接口和Collection的一摸一樣。Set的接口不保證它會(huì)用哪種順序來(lái)存儲(chǔ)元素。
HashSet*：為優(yōu)化查詢(xún)速度而設(shè)計(jì)的Set。要放進(jìn)HashSet里面的Object還得定義hashCode()。
TreeSet：是一個(gè)有序的Set，其底層是一顆樹(shù)。這樣你就能從Set里面提取一個(gè)有序序列了。
LinkedHashSet(JDK 1.4)：一個(gè)在內(nèi)部使用鏈表的Set，既有HashSet的查詢(xún)速度，又能保存元素被加進(jìn)去的順序（插入順序）。用Iterator遍歷Set的時(shí)候，它是按插入順序進(jìn)行訪(fǎng)問(wèn)的。
HashSet保存對(duì)象的順序是和TreeSet和LinkedHashSet不一樣的。這是因?yàn)樗鼈兪怯貌煌姆椒▉?lái)存儲(chǔ)和查找元素的。（TreeSet用了一種叫紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)【red-black tree data structure】來(lái)為元素排序，而HashSet則用了“專(zhuān)為快速查找而設(shè)計(jì)”的散列函數(shù)。LinkedHashSet在內(nèi)部用散列來(lái)提高查詢(xún)速度，但是它看上去像是用鏈表來(lái)保存元素的插入順序的。）你寫(xiě)自己的類(lèi)的時(shí)候，一定要記住，Set要有一個(gè)判斷以什么順序來(lái)存儲(chǔ)元素的標(biāo)準(zhǔn)，也就是說(shuō)你必須實(shí)現(xiàn) Comparable接口，并且定義compareTo()方法。

SortedSet
SortedSet（只有TreeSet這一個(gè)實(shí)現(xiàn)可用）中的元素一定是有序的。這使得SortedSet接口多了一些方法：
Comparator comparator()：返回Set鎖使用的Comparator對(duì)象，或者用null表示它使用Object自有的排序方法。
Object first()：返回最小的元素。
Object last()：返回最大的元素。
SortedSet subSet(fromElement, toElement)：返回Set的子集，其中的元素從fromElement開(kāi)始到toElement為止（包括fromElement，不包括toElement）。
SortedSet headSet(toElement)：返回Set的子集，其中的元素都應(yīng)小于toElement。
SortedSet headSet(toElement)：返回Set的子集，其中的元素都應(yīng)大于fromElement。
注意，SortedSet意思是“根據(jù)對(duì)象的比較順序”，而不是“插入順序”進(jìn)行排序。

Map的功能
ArrayList能讓你用數(shù)字在一愕嘎對(duì)象序列里面進(jìn)行選擇，所以從某種意義上講，它是將數(shù)字和對(duì)象關(guān)聯(lián)起來(lái)。但是，如果你想根據(jù)其他條件在一個(gè)對(duì)象序列里面進(jìn)行選擇的話(huà)，那又該怎么做呢？棧就是一個(gè)例子。它的標(biāo)準(zhǔn)是“選取最后一個(gè)被壓入棧的對(duì)象”。我們常用的術(shù)語(yǔ)map，dictionary，或 associative array就是一種非常強(qiáng)大的，能在序列里面進(jìn)行挑選的工具。從概念上講，它看上去像是一個(gè)ArrayList，但它不用數(shù)字，而是用另一個(gè)對(duì)象來(lái)查找對(duì)象！這是一種至關(guān)重要的編程技巧。
這一概念在Java中表現(xiàn)為Map。put(Object key, Object value)方法會(huì)往Map里面加一個(gè)值，并且把這個(gè)值同鍵（你查找時(shí)所用的對(duì)象）聯(lián)系起來(lái)。給出鍵之后，get(Object key)就會(huì)返回與之相關(guān)的值。你也可以用containsKey()和containsValue()測(cè)試Map是否包含有某個(gè)鍵或值。
Java標(biāo)準(zhǔn)類(lèi)庫(kù)里有好幾種Map：HashMap，TreeMap，LinkedHashMap，WeakHashMap，以及 IdentityHashMap。它們都實(shí)現(xiàn)了Map的基本接口，但是在行為方式方面有著明顯的詫異。這些差異體現(xiàn)在，效率，持有和表示對(duì)象pair的順序，持有對(duì)象的時(shí)間長(zhǎng)短，以及如何決定鍵的相等性。
性能時(shí)Map所要面對(duì)的一個(gè)大問(wèn)題。如果你知道get()時(shí)怎么工作的，你就會(huì)發(fā)覺(jué)（比方說(shuō)）在ArrayList里面找對(duì)象會(huì)是相當(dāng)慢的。而這正是 HashMap的強(qiáng)項(xiàng)。它不是慢慢地一個(gè)個(gè)地找這個(gè)鍵，而是用了一種被稱(chēng)為hash code的特殊值來(lái)進(jìn)行查找的。散列（hash）時(shí)一種算法，它會(huì)從目標(biāo)對(duì)象當(dāng)中提取一些信息，然后生成一個(gè)表示這個(gè)對(duì)象的“相對(duì)獨(dú)特”的int。 hashCode()是Object根類(lèi)的方法，因此所有Java對(duì)象都能生成hash code。HashMap則利用對(duì)象的hashCode()來(lái)進(jìn)行快速的查找。這樣性能就有了急劇的提高。
Map（接口）：維持鍵－－值的關(guān)系（既pairs），這樣就能用鍵來(lái)找值了。
HashMap*：基于hash表的實(shí)現(xiàn)。（用它來(lái)代替Hashtable。）提供時(shí)間恒定的插入與查詢(xún)。在構(gòu)造函數(shù)種可以設(shè)置hash表的capacity和load factor。可以通過(guò)構(gòu)造函數(shù)來(lái)調(diào)節(jié)其性能。
LinkedHashMap(JDK 1.4)：很像HashMap，但是用Iterator進(jìn)行遍歷的時(shí)候，它會(huì)按插入順序或最先使用的順序（least-recently-used (LRU)order）進(jìn)行訪(fǎng)問(wèn)。除了用Iterator外，其他情況下，只是比HashMap稍慢一點(diǎn)。用Iterator的情況下，由于是使用鏈表來(lái)保存內(nèi)部順序，因此速度會(huì)更快。
TreeMap：基于紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。當(dāng)你查看鍵或pair時(shí)，會(huì)發(fā)現(xiàn)它們時(shí)按順序（根據(jù)Comparable或Comparator，我們過(guò)一會(huì)講）排列的。TreeMap的特點(diǎn)時(shí)，你鎖得到的時(shí)一個(gè)有序的Map。TreeMap是Map中唯一有subMap()方法的實(shí)現(xiàn)。這個(gè)方法能讓你獲取這個(gè)樹(shù)中的一部分。
WeakHashMap：一個(gè)weak key的Map，是為某些特殊問(wèn)題而設(shè)計(jì)的。它能讓Map釋放其所持有的對(duì)象。如果某個(gè)對(duì)象除了在Map當(dāng)中充當(dāng)鍵之外，在其他地方都沒(méi)有其reference的話(huà)，那它將被當(dāng)作垃圾回收。
IdentityHashMap(JDK 1.4)：一個(gè)用＝＝，而不是equals()來(lái)比較鍵的hash map。不是為我們平常使用而設(shè)計(jì)的，是用來(lái)解決特殊問(wèn)題的。
散列是往Map里存數(shù)據(jù)的常用算法。

SortedMap
SortedMap（只有TreeMap這一個(gè)實(shí)現(xiàn)）的鍵肯定是有序的，因此這個(gè)接口里面就有一些附加功能的方法了。
Comparator comparator()：返回Map所使用的comparator，如果是用Object內(nèi)置的方法的話(huà)，則返回null。
Object firstKey()：返回第一個(gè)鍵。
Object lastKey()：返回最后一個(gè)鍵。
SortedMap subMap(fromKey, toKey)：返回這個(gè)Map的一個(gè)子集，其鍵從fromKey開(kāi)始到toKey為止，包括前者，不包括后者。
SortedMap headMap(toKey)：返回這個(gè)Map的一愕嘎子集，其鍵均小于toKey。
SortedMap tailMap(fromKey)：返回這個(gè)Map的一個(gè)子集，其鍵均大于等于fromKey。
pair是按key的順序存儲(chǔ)的，由于TreeMap有順序的概念，因此“位置”是有意義的，所以你可以去獲取它的第一個(gè)和最后一個(gè)元素，以及它的子集。

LinkedHashMap
為了提高速度，LinkedHashMap對(duì)所有東西都做了hash，而且遍歷的時(shí)候（println()會(huì)遍歷整個(gè)Map，所以你能看到這個(gè)過(guò)程）還會(huì)按插入順序返回pair。此外，你還可以在LinkedHashMap的構(gòu)造函數(shù)里面進(jìn)行配置，讓它使用基于訪(fǎng)問(wèn)的LRU（least-recently -used）算法，這樣還沒(méi)被訪(fǎng)問(wèn)過(guò)的元素（同時(shí)也是要?jiǎng)h除的候選對(duì)象）就會(huì)出現(xiàn)在隊(duì)列的最前頭。這樣，為節(jié)省資源而寫(xiě)一個(gè)定時(shí)清理的程序就變得很簡(jiǎn)單了。

散列算法與Hash數(shù)
一個(gè)合適的equals()必須做到一下五點(diǎn)：
1 反身性：對(duì)任何x, x.equals(x)必須是true的。
2 對(duì)稱(chēng)性：對(duì)任何x和y，如果y.equals(x)是true的，那么
x.equals(y)也必須是true的。
3 傳遞性：對(duì)任何x，y和z，如果x.equals(y)是true的，且
y.equals(z)也是true的，那么x.equals(z)也必須是true的。
4 一致性：對(duì)任何x和y，如果對(duì)象里面用來(lái)判斷相等姓的信息沒(méi)有修
改過(guò)，那么無(wú)論調(diào)用多少次x.equals(y)，它都必須一致地返回
true或false。
5 對(duì)于任何非空的x，x.equals(null)必須返回false。
默認(rèn)的Object.equals()只是簡(jiǎn)單地比較兩個(gè)對(duì)象的地址。
如果你想把子集寫(xiě)的類(lèi)當(dāng)HashMap的鍵來(lái)用的話(huà)，你就必須把hashCode()和equals（）都給覆寫(xiě)了。

理解hashCode()
如果你不覆寫(xiě)鍵的hashCode()和equals()的話(huà)，散列數(shù)據(jù)結(jié)構(gòu)（HashSet，HashMap，LinkedHashSet，或LinkedHashMap）就沒(méi)法正確地處理鍵。
散列的價(jià)值就在于速度：散列算法能很快地找出東西。
數(shù)組是最快的數(shù)據(jù)結(jié)構(gòu)。

持有reference
java.lang.ref類(lèi)庫(kù)里有一套能增進(jìn)垃圾回收器工作的靈活性的類(lèi)。一旦碰到了“對(duì)象達(dá)到要耗光內(nèi)存”的時(shí)候，這些類(lèi)就會(huì)閑的格外有用。有三個(gè)類(lèi)是繼承抽象類(lèi)Reference的：SoftReference，WeakReference和PhantomReference。如果待處理的對(duì)象只能通過(guò)這些Reference進(jìn)行訪(fǎng)問(wèn)的話(huà)，那么這些Reference對(duì)象就會(huì)向垃圾回收器提供一些不同級(jí)別的暗事。

……

總結(jié)Java標(biāo)準(zhǔn)類(lèi)庫(kù)的容器類(lèi)：
1。數(shù)組把對(duì)象和數(shù)字形式的下標(biāo)聯(lián)系起來(lái)。它持有的是類(lèi)型確定的對(duì)象，這樣提取對(duì)象的時(shí)候就不用再作類(lèi)型傳遞了。它可以是多維的，也可以持有primitive。但是創(chuàng)建之后它的容量不能改了。
2。Collection持有單個(gè)元素，而Map持有相關(guān)聯(lián)的pair。
3。和數(shù)組一樣，List也把數(shù)字下標(biāo)同對(duì)象聯(lián)系起來(lái)，你可以把數(shù)組和List想成有序的容器。List會(huì)隨元素的增加自動(dòng)調(diào)整容量。但是List只能持有Object reference，所以不能存放primitive，而且把Object提取出來(lái)之后，還要做類(lèi)型傳遞。
4。如果要做很多隨機(jī)訪(fǎng)問(wèn)，那么請(qǐng)用ArrayList，但是如果要再List的中間做很多插入和刪除的話(huà)，就應(yīng)該用LinkedList了。
5。LinkedList能提供隊(duì)列，雙向隊(duì)列和棧的功能。
6。Map提供的不是對(duì)象與數(shù)組的關(guān)聯(lián)，而是對(duì)象和對(duì)象的關(guān)聯(lián)。
HashMap看重的是訪(fǎng)問(wèn)速度，而TreeMap各國(guó)那看重鍵的順序，因而它不如HashMap那么快。而LinkedHashMap則保持對(duì)象插入的順序，但是也可以用LRU算法為它重新排序。
7。Set只接受不重復(fù)的對(duì)象。HashSet提供了最快的查詢(xún)速度。而TreeSet則保持元素有序。LinkedHashSet保持元素的插入順序。
8。沒(méi)必要再在新代碼里使用舊類(lèi)庫(kù)留下來(lái)的Vector，Hashtable和Stack了。
容器類(lèi)庫(kù)是你每天都會(huì)用到的工具，它能使程序更簡(jiǎn)介，更強(qiáng)大并且更搞笑。