Java，是由Sun公司於1995年推出的程式語言。用Java實現的HotJava瀏覽器（支持Java applet）顯示了Java的魅力：跨平台、動態的Web、Internet計算。從此，Java被廣泛接受並推動了Web的迅速發展，常用的瀏覽器現在均支持Java applet。集合框架是為表示和操作集合而規定的一種統一的標準的體系結構。任何集合框架都包含三大塊內容：對外的接口、接口的實現和對集合運算的算法。
基本介紹
集合論引,集合,集合框架,數組與容器,返回數組,相關類,複製數組,數組比較,數組元素,數組排序,有序數組,數組部分,框架益處,減少設計辛勞,提高速度質量,API缺點,集合框架復用,基礎版本,簡介,Vector,Stack,Hashtable,後續版本,Collection,List,Set,Map,未來容器,總結,
集合論引
集合論是現代數學中重要的基礎理論。它的概念和方法已經滲透到代數、拓撲和分析等許多數學分支以及物理學和質點力學等一些自然科學部門，為這些學科提供了奠基的方法，改變了這些學科的面貌。計算機科學作為一門現代科學因其與數學的緣源，自然其中的許多概念也來自數學，集合是其中之一。如果說集合論的產生給數學注入了新的生機與活力，那么計算機科學中的集合概念給程式設計師的生活也注入了新的生機與活力。
集合
很難給集合下一個精確的定義，通常情況下，把具有相同性質的一類東西，匯聚成一個整體，就可以稱為集合。比如，用Java編程的所有程式設計師，全體中國人等。通常集合有兩種表示法，一種是列舉法，比如集合A={1,2,3,4}，另一種是性質描述法，比如集合B={X|0<X<100且X屬於整數}。集合論的奠基人康托爾在創建集合理論給出了許多公理和性質，這都成為後來集合在其它領域套用的基礎，本文並不是講述集合論的，所以如果你對集合論感興趣，可以參考相關書籍。
集合框架
那么有了集合的概念，什麼是集合框架呢？集合框架是為表示和操作集合而規定的一種統一的標準的體系結構。任何集合框架都包含三大塊內容：對外的接口、接口的實現和對集合運算的算法。
接口：即表示集合的抽象數據類型。接口提供了讓我們對集合中所表示的內容進行單獨操作的可能。
實現：也就是集合框架中接口的具體實現。實際它們就是那些可復用的數據結構。
算法：在一個實現了某個集合框架中的接口的對象身上完成某種有用的計算的方法，例如查找、排序等。這些算法通常是多態的，因為相同的方法可以在同一個接口被多個類實現時有不同的表現。事實上，算法是可復用的函式。如果你學過C++，那C++中的標準模版庫（STL）你應該不陌生，它是眾所周知的集合框架的絕好例子。
數組與容器
數組與其它容器的區別體現在三個方面：效率，類型識別以及可以持有primitives。數組是Java提供的，能隨機存儲和訪問reference序列的諸多方法中的，最高效的一種。數組是一個簡單的線性序列，所以它可以快速的訪問其中的元素。但是速度是有代價的；當你創建了一個數組之後，它的容量就固定了，而且在其生命周期里不能改變。也許你會提議先創建一個數組，等到快不夠用的時候，再創建一個新的，然後將舊的數組裡的reference全部導到新的裡面。其實（我們以後會講的）ArrayList就是這么做的。但是這種靈活性所帶來的開銷，使得ArrayList的效率比起數組有了明顯下降。
Java對數組和容器都做邊界檢查；如果過了界，它就會給一個RuntimeException。這種異常表明這個錯誤是由程式設計師造成的，這樣你就用不著再在程式裡面檢查了。
還有一些泛型容器類包括List，Set和Map。他們處理對象的時候就好像這些對象都沒有自己的具體類型一樣。也就是說，容器將它所含的元素都看成是（Java中所有類的根類）Object的。這樣你只需要建一種容器，就能把所有類型的對象全都放進去。從這個角度來看，這種作法很不錯（只是苦了primitive。如果是常量，你還可以用Java的primitive的Wrapper類；如果是變數，那就只能放在你自己的類里了）。與其他泛型容器相比，這裡體現數組的第二個優勢：創建數組的時候，你也同時指明了它所持有的對象的類型（這又引出了第三點－－數組可以持有primitives，而容器卻不行）。也就是說，它會在編譯的時候作類型檢查，從而防止你插入錯誤類型的對象，或者是在提取對象的時候把對象的類型給搞錯了。Java在編譯和運行時都能阻止你將一個不恰當的訊息傳給對象。所有這並不是說使用容器就有什麼危險，只是如果編譯器能夠幫你指定，那么程式運行會更快，最終用戶也會較少收到程式運行異常的騷擾。
從效率和類型檢查的角度來看，使用數組總是沒錯的。但是，如果你在解決一個更為一般的問題，那數組就會顯得功能太弱了點。
不管你用的是哪種類型的數組，數組的標識符實際上都是一個“創建在堆（heap）里的實實在在的對象的”reference。實際上是那個對象持有其他對象的reference。你即可以用數組的初始化語句，隱含地創建這個對象，也可以用new表達式，明確地創建這個對象，唯讀的length屬性能告訴你數組能存儲多少元素。它是數組對象的一部分（實際上也是你唯一能訪問的屬性或方法）。‘[]’語法是另一條訪問數組對象的途徑。
你沒法知道數組裡面究竟放了多少元素，因為length只是告訴你數組能放多少元素，也就是說是數組對象的容量，而不是它真正已經持有的元素的數量。但是，創建數組對象的時候，它所持有的reference都會被自動地初始化為null，所以你可以通過檢查數組的某個“槽位”是否為null，來判斷它是否持有對象。以此類推，primitive的數組，會自動來數字初始化為零，字元初始化為(char)0，boolean初始化為false。
容器類只能持有Object對象的reference。而數組除了能持有Objects的reference之外，還可以直接持有primitive。當然可以使用諸如Integer，Double之類的wrapper類。把primitive的值放到容器中，但這樣總有點怪怪的。此外，primitive數組的效率要比wrapper類容器的高出許多。
當然，如果你使用primitive的時候，還需要那種“能隨需要自動擴展的”容器類的靈活性，那就不能用數組了。你只能用容器來存儲primitive的wrapper類。
返回數組
假設你寫了一個方法，它返回的不是一個而是一組東西。那么在Java中就可以返回的“就是一個數組”。與C++不同，你永遠也不必為Java的數組操心－－只要你還需要它，它就還在；一旦你用完了，垃圾回收器會幫你把它打掃乾淨。
相關類
雖然Arrays還是有用的，但它的功能並不完整。舉例來說，如果它能讓我們不用寫for循環就能直接列印數組，那就好了。此外，正如你所看到的fill()只能用一個值填數組。所以，如果你想把隨機生成的數字填進數組的話，fill()是無能為力的。
複製數組
數組比較
為了能比較數組是否完全相等，Arrays提供了經重載的equals()方法。當然，也是針對各種primitive以及Object的。兩個數組要想完全相等，他們必須有相同數量的元素，而且數組的每個元素必須與另一個數組的相對應的位置上的元素相等。元素的相等性，用equals()判斷。（對於primitive，它會使用其wrapper類的equals()；比如int使用Integer.equals()。）。
數組元素
Java裡面有兩種能讓你實現比較功能的方法。一是實現java.lang.Comparable接口，並以此實現類“自有的”比較方法。這?這個方法能接受另一個對象作為參數，如果現有對象比參數小，它就會返回一個負數，如果相同則返回零，如果現有的對象比參數大，它就返回一個正數。
static randInt()方法會生成一個介於0到100之間的正數。
假設，有人給你一個沒有實現Comparable接口的類，或者這個類實現了Comparable接口，但是你發現它的工作方式不是你所希望的，於是要重新定義一個新的比較方法。Java沒有強求你一定要把比較代碼塞進類里，它的解決方案是使用“策略模式（strategy design pattern）”。有了策略之後，你就能把會變的代碼封裝到它自己的類里（即所謂的策略對象strategy object）。你把策略對象交給不會變的代碼，然後用它運用策略完成整個算法。這樣，你就可以用不同的策略對象來表示不同的比較方法，然後把它們都交給同一個排序程式了。接下來就要“通過實現Comparator接口”來定義策略對象了。這個接口有兩個方法compare()和equals()。但是除非是有特殊的性能要求，否則你用不著去實現equals()。因為只要是類，它就都隱含地繼承自Object，而Object裡面已經有了一個equals()了。所以你盡可以使用預設的Object的equals()，這樣就已經滿足接口的要求了。
Collections類里專門有一個會返回與對象自有的比較法相反的Comparator的方法。它能很輕易地被用到CompType上面。
Collections.reverseOrder()返回了一個Comparator的reference。
compare()方法會根據第一個參數是小於，等於還是大於第二個參數，分別返回負整數，零或是正整數。
數組排序
Java標準類庫所用的排序算法已經作了最佳化－－對primitive，它用的是“快速排序（Quicksort）”，對對象，它用的是“穩定合併排序（stable merge sort）”。所以除非是prolier表明排序算法是瓶頸，否則你不用為性能擔心。
有序數組
一旦數組排完序，你就能用Arrays.binarySearch()進行快速查詢了。但是切忌對一個尚未排序的數組使用binarySearch()；因為這么做的結果是沒意義的。
如果Arrays.binarySearch()找到了，它就返回一個大於或等於0的值。否則它就返回一個負值，而這個負值要表達的意思是，如果你手動維護這個數組的話，這個值應該插在哪個為止。這個值就是：
-(插入點)-1
“插入點”就是，在所有“比要找的那個值”更大值中，最小的那個值的下標，或者，如果數組中所有的值都比要找的值小，它就是a.size()。
如果數組裡面有重複元素，那它不能保證會返回哪一個。這個算法不支持重複元素，不過它也不報錯。所以，如果你需要的是一個無重複元素的有序序列的話，那么可以考慮使用本章後面所介紹的TreeSet（支持【排序順序“sorted order”】）和LinkedHashSet（支持【插入順序“sorted order”】）。這兩個類會幫你照看所有細節。只有在遇到性能瓶頸的時候，你才應該用手動維護的數組來代替這兩個類。
如果排序的時候用到了Comparator（針對對象數組，primitive數組不允許使用Comparator），那么binarySearch()的時候，也必須使用同一個Comparator（用這個方法的重載版）。
數組部分
總而言之，如果你要持有一組對象，首選，同時也是效率最高的選擇，應該是數組。而且，如果這是一組primitive的話，你也只能用數組。還有一些更為一般的情況，也就是寫程式的時候還不知道要用多少對象，或者要用一種更複雜方式來存儲對象情況。為此，Java提供了“容器類（container class）”。其基本類型有List，Set和Map。
它們還有一些別的特性。比方說Set所持有的對象，個個都不同，Map則是一個“關聯性數組（associative array）”，它能在兩個對象之間建立聯繫。此外，與數組不同，它們還能自動調整大小，所以你可以往裡面放任意數量的對象。
框架益處
減少設計辛勞
集合框架通過提供有用的數據結構和算法使你能集中注意力於你的程式的重要部分上，而不是為了讓程式能正常運轉而將注意力於低層設計上。通過這些在無關API之間的簡易的互用性，使你免除了為改編對象或轉換代碼以便聯合這些API而去寫大量的代碼。
提高速度質量
集合框架通過提供對有用的數據結構和算法的高性能和高質量的實現使你的程式速度和質量得到提高。因為每個接口的實現是可互換的，所以你的程式可以很容易的通過改變一個實現而進行調整。另外，你將可以從寫你自己的數據結構的苦差事中解脫出來，從而有更多時間關注於程式其它部分的質量和性能。
API缺點
許多API天生的有對集合的存儲和獲取。在過去，這樣的API都有一些子API幫助操縱它的集合內容，因此在那些特殊的子API之間就會缺乏一致性，你也不得不從零開始學習，並且在使用時也很容易犯錯。而標準集合框架接口的出現使這個問題迎刃而解。
集合框架復用
對於遵照標準集合框架接口的新的數據結構天生即是可復用的。同樣對於操作一個實現了這些接口的對象的算法也是如此。
有了這些優點，並通過合理的使用，它就會成為程式設計師的一種強大的工具。不過，從歷史上來看，集合大多其結構相當複雜，也就給它們一個造成極不合理的學習曲線的壞名聲。但是，希望Java2的集合框架能縮短你的學習曲線，從而快速掌握它。
在許多高級語言中的數組其實也是集合的一種簡單實現，比如C,C++,Pascal和Java。數組保存著相同類型的多個值，它的長度在數組被創建時就固定下來，建立之後就無法改變。如果你需要一種大小能動態改變的存儲結構，數組就不適合了，這時集合框架就有了用武之地了。
基礎版本
簡介
其實在Java2之前，Java是沒有完整的集合框架的。它只有一些簡單的可以自擴展的容器類，比如Vector，Stack，Hashtable等。Vector中包含的元素可以通過一個整型的索引值取得，它的大小可以在添加或移除元素時自動增加或縮小。然而，Vector的設計卻存在極多缺陷（下面會說到）。Stack是一種後進先出（LIFO）的堆疊序列，學過數據結構的都會知道，它的重要特點是先放入的東西最後才能被取出。Hashtable與Java2中的Map類似，可以看成一種關聯或映射數組，可以將兩個或多個毫無關係的對象相關聯，與數組不同的是它的大小可以動態變化。
Vector
Vector的操作很簡單，通過addElement()加入一個對象，用elementAt()取出它，還可以查詢當前所保存的對象的個數size();另外還有一個Enumeration類提供了連續操作Vector中元素的方法，這可以通過Vector中的elements()方法來獲取一個Enumeration類的對象，可以用一個While循環來遍歷其中的元素。用hasMoreElements()檢查其中是否還有更多的元素。用nextElement()獲得下一個元素。Enumeration的用意在於使你能完全不用理會你要遍歷的容器的基礎結構，只關注你的遍歷方法，這也就使得遍歷方法的重用成為可能。由於這種思想的強大功能，所以在Java2中被保留下來，不過具體實現，方法名和內部算法都改變了，這就是Java2中的Iterator以及ListIterator類。然而Enumeration的功能卻十分有限，比如只能朝一個方向進行，只能讀取而不能更改等。
Stack
單元素容器Stack，它最常用的操作便是壓入和彈出，最後壓入的元素最先被彈出。你可以想像一個只上面開口的書箱，最後放進去的書一定是最先被拿到，而最先放進去的只有在全部書拿出後才能取出，這種特性被稱為後進先出（LIFO）。在Java中Stack的的用法也很簡單，有push()壓入一個元素，用pop()彈出一個元素。然而它的設計卻無法讓人理解，Stack繼承了Vector而不用Vector作為其中一個元素類型來實現其功能，這樣造成的結果是Stack也擁有Vector的行為，也就是說你可以把Stack當作一個Vector來用，而這與Stack的用意毫無關係。這應該算為Java1（1.0/1.1)中容器類庫設計者的一大失誤吧，還好，這些在Java2中都有了相當大的改變觀。
Hashtable
Hashtable也是Java1中一個有用的容器類庫。它的基本目標是實現兩個或多個對象之間進行關聯。舉一個現實生活中的例子，比如我們說美國白宮時，指的就是在美國華盛頓的總統辦公大樓，為什麼一說到美國白宮，指的就是總統辦公大樓呢？這是我們人為的對“美國白宮”和總統辦公大樓進行了關聯，本來“美國白宮”就是四個普通的文字，卻有了不同的含義。在Java中我們就可以用String定義一個內容為“美國白宮”的對象變數，在定義一個總統大樓的對象變數，把它們進行關聯，這就是Hashtable的用意。通過使用pub(Object key,Object value)方法把兩個對象進行關聯，需要時用get(Object key)取得與key關聯的值對象。還可以查詢某個對象的索引值等等。值得說明的這裡的get方法查找一個對象時與Vector中的get方法在內部實現時有很大不同，在一個Hashtable中查找一個鍵對象要比在一個Vector中快的多。這是因為Hashtable使用了一種哈希表的技術（在數據結構中有詳細講解），在Java每個對象預設都有一個通過Object的hashCode()方法獲得的哈希碼，Hashtable就是利用這個哈希實現快速查找鍵對象的。
Java1容器類庫設計的另一個重大失誤是竟然沒有對容器進行排序的工具。比如你想讓Vector容器中的對象按字典順序進行排序，你就要自己實現。
雖然Java1中的容器類庫如此簡陋，卻也使Java程式設計師在當時編程時省力不少，那些容器類也被大量用到，正所謂無可奈何，沒得選擇。可能是Java在其成長過程一直被美麗的光環籠照著，所以它的缺點也被人們忽略了，幸好，在Java2中容器類庫設計者對以前的拙劣設計進行了大刀闊斧的整改，從而使Java變得更加完美。
後續版本
自Java1.2之後Java版本統稱為Java2，Java2中的容器類庫才可以說是一種真正意義上的集合框架的實現。基本完全重新設計，但是又對Java1中的一些容器類庫在新的設計上進行了保留，這主要是為了向下兼容的目的，當用Java2開發程式時，應儘量避免使用它們，Java2的集合框架已經完全可以滿足你的需求。有一點需要提醒的是，在Java1中容器類庫是同步化的，而Java2中的容器類庫都是非同步化，這可能是對執行效率進行考慮的結果。
Java2中的集合框架提供了一套設計優良的接口和類，使程式設計師操作成批的數據或對象元素極為方便。這些接口和類有很多對抽象數據類型操作的API，而這是我們常用的且在數據結構中熟知的。例如Maps，Sets，Lists，Arrays等。並且Java用面向對象的設計對這些數據結構和算法進行了封裝，這就極大的減化了程式設計師編程時的負擔。程式設計師也可以以這個集合框架為基礎，定義更高級別的數據抽象，比如棧、佇列和執行緒安全的集合等，從而滿足自己的需要。
Java2的集合框架，抽其核心，主要有三類：List、Set和Map。List和Set繼承了Collection，而Map則獨成一體。初看上去可能會對Map獨成一體感到不解，它為什麼不也繼承Collection呢？但是仔細想想，這種設計是合理的。一個Map提供了通過Key對Map中存儲的Value進行訪問，也就是說它操作的都是成對的對象元素，比如put()和get()方法，而這是一個Set或List所不就具備的。當然在需要時，你可以由keySet()方法或values()方法從一個Map中得到鍵的Set集或值的Collection集。
Collection
Collection接口提供了一組操作成批對象的方法
它提供了基本操作如添加、刪除。它也支持查詢操作如是否為空isEmpty()方法等。為了支持對Collection進行獨立操作，Java的集合框架給出了一個Iterator，它使得你可以泛型操作一個Collection，而不需知道這個Collection的具體實現類型是什麼。它的功能與Java1中的Enumeration類似，只是更易掌握和使用，功能也更強大。在建立集合框架時，Sun的開發團隊考慮到需要提供一些靈活的接口，用來操作成批的元素，又為了設計的簡便，就把那些對集合進行可選操作的方法與基本方法放到了一起。因為一個接口的實現者必須提供對接口中定義的所有方法的實現，這就需要一種途徑讓調用者知道它正在調用的可選方法當前不支持。最後開發團隊選擇使用一種信號，也即拋出一種不支持操作例外(UnsupportedOperationException)，如果你在使用一個Collection中遇到一個上述的例外，那就意味著你的操作失敗，比如你對一個唯讀Collection添加一個元素時，你就會得到一個不支持操作例外。在你實現一個集合接口時，你可以很容易的在你不想讓用戶使用的方法中拋出UnsupportOperationException來告訴使用者這個方法當前沒有實現，UnsupportOperationException是RuntimeException的一個擴展。
另外Java2的容器類庫還有一種Fail fast的機制。比如你正在用一個Iterator遍歷一個容器中的對象，這時另外一個執行緒或進程對那個容器進行了修改，那么再用next()方法時可能會有災難性的後果，而這是你不願看到的，這時就會引發一個ConcurrentModificationException例外。這就是fail－fast。Collection的功能
下面這張表給出了Collection的所有功能，也就是你能用Set和List做什麼事（不包括從Object自動繼承過來的方法）。（List還有一些額外的功能。）Map不是繼承Collection的，所以我們會區別對待。
boolean add(Object)：確保容器能持有你傳給它的那個參數。如果沒有把它加進去，就返回false。（這是個“可選”的方法，本章稍後會再作解釋。）
boolean addAll(Collection)：加入參數Collection所含的所有元素。只要加了元素，就返回true。
void clear()：清除容器所保存的所有元素。（“可選”）
boolean contains(Object)：如果容器持有參數Object，就返回true。
boolean containsAll(Collection)：如果容器持有參數Collection所含的全部元素，就返回true。 boolean isEmpty()：如果容器裡面沒有保存任何元素，就返回true。
Iterator iterator()：返回一個可以在容器的各元素之間移動的Iterator。
boolean removeAll(Collection)：刪除容器裡面所有參數Collection所包含的元素。只要刪過東西，就返回true。（“可選”）
boolean retainAll(Collection)：只保存參數Collection所包括的元素（集合論中“交集”的概念）。如果發生過變化，則返回true。（“可選”）
int size()：返回容器所含元素的數量。
Object[] toArray()：返回一個包含容器中所有元素的數組。
Object[] toArray(Object[] a)：返回一個包含容器中所有元素的數組，且這個數組不是普通的Object數組，它的類型應該同參數數組a的類型相同（要做類型轉換）。
注意，這裡沒有能進行隨機訪問的get()方法。這是因為Collection還包括Set。而Set有它自己的內部順序（因此隨機訪問是毫無意義的）。所以如果你要檢查Collection的元素，你就必須使用疊代器。
接下來講List, Set和Map的各種實現了，每講一種容器，我都會（用星號）告訴你默認情況下應該選用哪種實現。
List
List接口對Collection進行了簡單的擴充
它的具體實現類常用的有ArrayList和LinkedList。你可以將任何東西放到一個List容器中，並在需要時從中取出。ArrayList從其命名中可以看出它是一種類似數組的形式進行存儲，因此它的隨機訪問速度極快，而LinkedList的內部實現是鍊表，它適合於在鍊表中間需要頻繁進行插入和刪除操作。在具體套用時可以根據需要自由選擇。前面說的Iterator只能對容器進行向前遍歷，而ListIterator則繼承了Iterator的思想，並提供了對List進行雙向遍歷的方法。List的功能
List的基本用法是相當簡單的。雖然絕大多數時候，你只是用add()加對象，用get()取對象，用iterator()獲取這個序列的Iterator，但List還有一些別的很有用的方法。
實際上有兩種List：擅長對元素進行隨機訪問的，較常用的ArrayList，和更強大的LinkedList。LinkedList不是為快速的隨機訪問而設計的，但是它卻有一組更加通用的方法。
List（接口）：List的最重要的特徵就是有序；它會確保以一定的順序保存元素。List在Collection的基礎上添加了大量方法，使之能在序列中間插入和刪除元素。（只對LinkedList推薦使用。）List可以製造ListIterator對象，你除了能用它在List的中間插入和刪除元素之外，還能用它沿兩個方向遍歷List。
記住，容器只是一個存儲對象的盒子。如果這個小盒子能幫你解決所有的問題，那你就用不著去管它是怎么實現的（在絕大多數情況下，這是使用對象的基本概念）。如果開發環境裡面還有一些別的，會造成固定的性能開銷的因素存在，那么ArrayList和LinkedList之間的性能差別就會變得不那么重要了。你只需要它們中的一個，你甚至可以想像有這樣一種“完美”的抽象容器；它能根據用途，自動地切換其底層的實現。
LinkedList的用途
用LinkedList做一個棧
“棧（stack）”有時也被稱為“後進先出”（LIFO）的容器。就是說，最後一個被“壓”進棧中的東西，會第一個“彈”出來。同其他Java容器一樣，壓進去和彈出來的東西都是Object，所以除非你只用Object的功能，否則就必須對彈起來的東西進行類型轉換。
LinkedList的方法能直接實現棧的功能，所以你完全可以不寫Stack而直接使用LinkedList。
如果你只想要棧的功能，那么繼承就不太合適了，因為繼承出來的是一個擁有LinkedList的所有方法的類。
用LinkedList做一個佇列
佇列（queue）是一個“先進先出”（FIFO）容器。也就是，你把一端把東西放進去，從另一端把東西取出來。所以你放東西的順序也就是取東西的順序。LinkedList有支持佇列的功能的方法，所以它也能被當作Queue來用。
還能很輕易地用LinkedList做一個deque（雙向佇列）。它很像佇列，只是你可以從任意一端添加和刪除元素。
Set
Set接口也是Collection的一種擴展
與List不同的是，在Set中的對象元素不能重複，也就是說你不能把同樣的東西兩次放入同一個Set容器中。它的常用具體實現有HashSet和TreeSet類。HashSet能快速定位一個元素，但是你放到HashSet中的對象需要實現hashCode()方法，它使用了前面說過的哈希碼的算法。而TreeSet則將放入其中的元素按序存放，這就要求你放入其中的對象是可排序的，這就用到了集合框架提供的另外兩個實用類Comparable和Comparator。一個類是可排序的，它就應該實現Comparable接口。有時多個類具有相同的排序算法，那就不需要在每分別重複定義相同的排序算法，只要實現Comparator接口即可。集合框架中還有兩個很實用的公用類：Collections和Arrays。Collections提供了對一個Collection容器進行諸如排序、複製、查找和填充等一些非常有用的方法，Arrays則是對一個數組進行類似的操作。Set的功能
Set的接口就是Collection的，所以不像那兩個List，它沒有額外的功能。實際上Set確確實實就是一個Collection－－只不過行為方式不同罷了。（這是繼承和多態性的完美運用：表達不同地行為。）Set會拒絕持有多個具有相同值的對象的實例（對象的“值”又是由什麼決定的呢？這個問題比較複雜，我們以後會講）。
Set（接口）：加入Set的每個元素必須是唯一的；否則，Set是不會把它加進去的。要想加進Set，Object必須定義equals()，這樣才能標明對象的唯一性。Set的接口和Collection的一摸一樣。Set的接口不保證它會用哪種順序來存儲元素。
HashSet*：為最佳化查詢速度而設計的Set。要放進HashSet裡面的Object還得定義hashCode()。
TreeSet：是一個有序的Set，其底層是一顆樹。這樣你就能從Set裡面提取一個有序序列了。
LinkedHashSet(JDK 1.4)：一個在內部使用鍊表的Set，既有HashSet的查詢速度，又能保存元素被加進去的順序（插入順序）。用Iterator遍歷Set的時候，它是按插入順序進行訪問的。
HashSet保存對象的順序是和TreeSet和LinkedHashSet不一樣的。這是因為它們是用不同的方法來存儲和查找元素的。（TreeSet用了一種叫紅黑樹的數據結構【red-black tree data structure】來為元素排序，而HashSet則用了“專為快速查找而設計”的散列函式。LinkedHashSet在內部用散列來提高查詢速度，但是它看上去像是用鍊表來保存元素的插入順序的。）你寫自己的類的時候，一定要記住，Set要有一個判斷以什麼順序來存儲元素的標準，也就是說你必須實現Comparable接口，並且定義compareTo()方法。
SortedSet
SortedSet（只有TreeSet這一個實現可用）中的元素一定是有序的。這使得SortedSet接口多了一些方法：
Comparator comparator()：返回Set所使用的Comparator對象，或者用null表示它使用Object自有的排序方法。
Object first()：返回最小的元素。
Object last()：返回最大的元素。
SortedSet subSet(fromElement, toElement)：返回Set的子集，其中的元素從fromElement開始到toElement為止（包括fromElement，不包括toElement）。
SortedSet headSet(toElement)：返回Set的子集，其中的元素都應小於toElement。
SortedSet headSet(toElement)：返回Set的子集，其中的元素都應大於fromElement。
注意，SortedSet意思是“根據對象的比較順序”，而不是“插入順序”進行排序.
Map
Map是一種把鍵對象和值對象進行關聯的容器
一個值對象又可以是一個Map，依次類推，這樣就可形成一個多級映射。對於鍵對象來說，像Set一樣，一個Map容器中的鍵對象不允許重複，這是為了保持查找結果的一致性;如果有兩個鍵對象一樣，那你想得到那個鍵對象所對應的值對象時就有問題了，可能你得到的並不是你想的那個值對象，結果會造成混亂，所以鍵的唯一性很重要，也是符合集合的性質的。當然在使用過程中，某個鍵所對應的值對象可能會發生變化，這時會按照最後一次修改的值對象與鍵對應。對於值對象則沒有唯一性的要求。你可以將任意多個鍵都映射到一個值對象上，這不會發生任何問題（不過對你的使用卻可能會造成不便，你不知道你得到的到底是那一個鍵所對應的值對象）。Map有兩種比較常用的實現：HashMap和TreeMap。HashMap也用到了哈希碼的算法，以便快速查找一個鍵，TreeMap則是對鍵按序存放，因此它便有一些擴展的方法，比如firstKey(),lastKey()等，你還可以從TreeMap中指定一個範圍以取得其子Map。鍵和值的關聯很簡單，用put(Object key,Object value)方法即可將一個鍵與一個值對象相關聯。用get(Object key)可得到與此key對象所對應的值對象。
Map的功能
ArrayList能讓你用數字在一個對象序列裡面進行選擇，所以從某種意義上講，它是將數字和對象關聯起來。但是，如果你想根據其他條件在一個對象序列裡面進行選擇的話，那又該怎么做呢？棧就是一個例子。它的標準是“選取最後一個被壓入棧的對象”。我們常用的術語map，dictionary，或associative array就是一種非常強大的，能在序列裡面進行挑選的工具。從概念上講，它看上去像是一個ArrayList，但它不用數字，而是用另一個對象來查找對象！這是一種至關重要的編程技巧。
這一概念在Java中表現為Map。put(Object key, Object value)方法會往Map裡面加一個值，並且把這個值同鍵（你查找時所用的對象）聯繫起來。給出鍵之後，get(Object key)就會返回與之相關的值。你也可以用containsKey()和containsValue()測試Map是否包含有某個鍵或值。
Java標準類庫里有好幾種Map：HashMap，TreeMap，LinkedHashMap，WeakHashMap，以及IdentityHashMap。它們都實現了Map的基本接口，但是在行為方式方面有著明顯的詫異。這些差異體現在，效率，持有和表示對象pair的順序，持有對象的時間長短，以及如何決定鍵的相等性。
性能是Map所要面對的一個大問題。如果你知道get()時怎么工作的，你就會發覺（比方說）在ArrayList裡面找對象會是相當慢的。而這正是HashMap的強項。它不是慢慢地一個個地找這個鍵，而是用了一種被稱為hash code的特殊值來進行查找的。散列（hash）時一種算法，它會從目標對象當中提取一些信息，然後生成一個表示這個對象的“相對獨特”的int。hashCode()是Object根類的方法，因此所有Java對象都能生成hash code。HashMap則利用對象的hashCode()來進行快速的查找。這樣性能就有了急劇的提高。
Map（接口）：維持鍵－－值的關係（既pairs），這樣就能用鍵來找值了。
HashMap*：基於hash表的實現。（用它來代替Hashtable。）提供時間恆定的插入與查詢。在構造函式種可以設定hash表的capacity和load factor。可以通過構造函式來調節其性能。
LinkedHashMap(JDK 1.4)：很像HashMap，但是用Iterator進行遍歷的時候，它會按插入順序或最先使用的順序（least-recently-used(LRU)order）進行訪問。除了用Iterator外，其他情況下，只是比HashMap稍慢一點。用Iterator的情況下，由於是使用鍊表來保存內部順序，因此速度會更快。
TreeMap：基於紅黑樹數據結構的實現。當你查看鍵或pair時，會發現它們時按順序（根據Comparable或Comparator，我們過一會講）排列的。TreeMap的特點時，你所得到的是一個有序的Map。TreeMap是Map中唯一有subMap()方法的實現。這個方法能讓你獲取這個樹中的一部分。
WeakHashMap：一個weak key的Map，是為某些特殊問題而設計的。它能讓Map釋放其所持有的對象。如果某個對象除了在Map當中充當鍵之外，在其他地方都沒有其reference的話，那它將被當作垃圾回收。
IdentityHashMap(JDK 1.4)：一個用==，而不是equals()來比較鍵的hashmap。不是為我們平常使用而設計的，是用來解決特殊問題的。
散列是往Map里存數據的常用算法。
SortedMap
SortedMap（只有TreeMap這一個實現）的鍵肯定是有序的，因此這個接口裡面就有一些附加功能的方法了。
Comparator comparator()：返回Map所使用的comparator，如果是用Object內置的方法的話，則返回null。
Object firstKey()：返回第一個鍵。
Object lastKey()：返回最後一個鍵。
SortedMap subMap(fromKey, toKey)：返回這個Map的一個子集，其鍵從fromKey開始到toKey為止，包括前者，不包括後者。
SortedMap headMap(toKey)：返回這個Map的一個子集，其鍵均小於toKey。
SortedMap tailMap(fromKey)：返回這個Map的一個子集，其鍵均大於等於fromKey。
pair是按key的順序存儲的，由於TreeMap有順序的概念，因此“位置”是有意義的，所以你可以去獲取它的第一個和最後一個元素，以及它的子集。
LinkedHashMap
為了提高速度，LinkedHashMap對所有東西都做了hash，而且遍歷的時候（println()會遍歷整個Map，所以你能看到這個過程）還會按插入順序返回pair。此外，你還可以在LinkedHashMap的構造函式裡面進行配置，讓它使用基於訪問的LRU（least-recently-used）算法，這樣還沒被訪問過的元素（同時也是要刪除的候選對象）就會出現在佇列的最前頭。這樣，為節省資源而寫一個定時清理的程式就變得很簡單了。
未來容器
前面幾部分對Java中容器類庫的狀況進行了討論，然而就在寫下此文時，Sun已經開始通過某種途徑分發J2SE1.5的Alpha測試版了。在JavaOne大會上，諸多大師描繪了Java的美好未來與在下一個版本中即將加入的一些新特性，其中為容器類庫加入的一個重要特性就是泛型。
1. importjava.util.*;
2. public class Generics{
3. /**
4. * 輸出一個String類型的列表，假設所給參數list中所有元素都為String。
5. */
6. public static void printList(Listlist){
7. for(int i=0;i<list.size();i++){
8. System.out.println(((String)list.get(i)).toString());
9. }
10. }
11. public static void main(String[] args){
12. Listlist=new ArrayList();
13. for(int i=0;i<9;i++){
14.list.add("Number:"+Integer.toString(i));
15. }
16. //list.add(new Generics()); //(1)
17. printList(list);
18. }
19. }
上面的代碼很簡單，定義了一個靜態方法來列印一個元素為String類型的List，然而正如你看到的一樣，如果你試著將(1)行中前面的注釋去掉，你就會得到一個ClassCastException例外，因為printList會將list中的每個元素都轉型為String，而在遇到最後一個元素時發現它是一個Generics類型從而無法完成轉型，例外就被拋出。這種情況在Java編程中很容易出現，原因是Java的容器類庫通常保存的是Object類型，而這是所有類的直接或間接超類，這就允許你將任何類型的元素添加到一個List中而不會給你任何提示，有經驗的程式設計師可能會自己編寫一個容器類來限制添加到其中的元素，這是一個編程技巧。但是我們就再也不用那樣做了，泛型機制會為我們做好這件事。那就看一下用泛型機制對上面代碼進行的改進：
1. importjava.util.*;
2. public class Generics{
3. /**
4. * 輸出一個String類型的列表，限制了所給參數list中所有元素都為String
5. */
6. public static void printList(ArrayList<String> list){
7. for(int i=0;i<list.size();i++){
8. System.out.println(list.get(i).toString());
9. //get()返回的不再是Object類型，而是String類型
10. }
11. }
12. public static void main(String[] args){
13. ArrayListlist=new ArrayList<String>(); //注意此行中聲明語法的變化
14. for(int i=0;i<9;i++){
15.list.add("Number:"+Integer.toString(i)); //只能向其中添加String類型
16. }
17.list.add(new Generics()); //無法通過，編譯時錯誤
18. printList(list);
19. }
20. }
正如在代碼中所看到的，容器的聲明有了變化，即在一個容器類後面用<>來說明你想要放入這個容器中的元素類型，那么接下來你只能向這個容器加那種類型，否則編譯就無法通過。在printList中也省去了轉型的麻煩。當然有了泛型，並不是說以前的聲明方法不能用了，你完全可以還用以前的方法，這沒有任何問題。其實根據JSR中對for語句功能的增強，遍歷一個容器也會更加簡單。
當然泛型的使用方法不只如此，這裡並沒有對它進行完整描述，只想告訴你，泛型確實為我們編程提供了便利，但是仍然需要用心去學習和掌握。
總結
1.數組把對象和數字形式的下標聯繫起來。它持有的是類型確定的對象，這樣提取對象的時候就不用再作類型傳遞了。它可以是多維的，也可以持有primitive。但是創建之後它的容量不能改了。
2.Collection持有單個元素，而Map持有相關聯的pair。
3.和數組一樣，List也把數字下標同對象聯繫起來，你可以把數組和List想成有序的容器。List會隨元素的增加自動調整容量。但是List只能持有Objectreference，所以不能存放primitive，而且把Object提取出來之後，還要做類型傳遞。
4.如果要做很多隨機訪問，那么請用ArrayList，但是如果要再List的中間做很多插入和刪除的話，就應該用LinkedList了。
5.LinkedList能提供佇列，雙向佇列和棧的功能。
6.Map提供的不是對象與數組的關聯，而是對象和對象的關聯。
HashMap看重的是訪問速度，而TreeMap看重鍵的順序，因而它不如HashMap那么快。而LinkedHashMap則保持對象插入的順序，但是也可以用LRU算法為它重新排序。
7.Set只接受不重複的對象。HashSet提供了最快的查詢速度。而TreeSet則保持元素有序。LinkedHashSet保持元素的插入順序。
8.沒必要再在新代碼里使用舊類庫留下來的Vector，Hashtable和Stack了。
容器類庫是你每天都會用到的工具，它能使程式更簡潔，更強大並且更高效。
隨著Java的進一步完善，它的功能和易用性也得到提高，我有理由相信Java在計算機語言中所占的位置也會更加牢固，讓喜愛Java的人更加喜愛它。祝願Java一路順風！
