Java2的重新設計了1.0和1.1裡面那個表現差勁的容器類。新的設計更緊湊也更合理。同時它也補齊了容器類庫的功能，提供了連結串列（linked list），佇列（queue）和雙向佇列（deques，讀成“decks”）這幾種資料結構的功能。 Java2的容器類要解決“怎樣持有物件”，而它把這個問題分成兩類： 1。Collection：通常是一組有一定規律的獨立元素。List必須按照特定的順序持有這些元素，而Set則不能儲存重複的元素。（bag沒有這個限制，但是Java的容器類庫沒有實現它，因為List已經提供這種功能了） 2。Map：一組以“鍵－－值”（key-value）形式出現的pair。初看上去，它應該是一個pair的Collection，但是真這麼去做的話，它就會變得很滑稽，所以還是把這個概念獨立列出來為好。退一步說，真的要用到Map的某個自己的時候，建立一個Collection也是很方便的。 Map可以返回“鍵（key）的”Set，值的Collection，或者pair的Set。和陣列一樣，Map不需要什麼修改，就能很容易地擴充套件成多維。你只要直接把Map的值設成Map就可以了（然後它的值再是Map，依此類推）。 Java的容器類分成兩種基本型別。它們的區別就在，每個位置能放多少物件。Collection只允許每個位置上放一個物件（這個名字有點誤導，因為容器類庫也常被統稱為collections）。它包括“以一定順序持有一組物件”的List，以及“只能允許新增不重複的物件”的Set。 ArrayList是一種List，而HashSet則是一種Set。你可以用add()方法往Collection裡面加物件。 Map儲存的是“鍵（key）－－值”形式的pair，很像是一個微型資料庫。 Map又被稱為關聯性陣列（associative array）。你可以用put()方法往Map裡面加元素。它接受鍵－－值形式pair作引數。 fill()方法還為Collection和Map作了過載。輸出在預設情況下使用容器類的toString()方法。打印出來的Collection會用方括號括起來，元素與元素之間用逗號分開。Map會用花括號括起來，鍵和值之間用等號聯起來（鍵在左邊，值在右邊）。 List會老老實實地持有你所輸入的所有物件，既不做排序也不做編輯。Set則每個物件只接受一次，而且還要用它自己的規則對元素進行重新排序（一般情況下，你關心的只是Set包沒包括某個物件，而不是它到底排在哪裡－－如果是那樣，你最好還是用List）。而Map也不接收重複的pair，至於是不是重複，要由key來決定。此外，它也有它自己的內部排序規則，不會受輸入順序影響。如果插入順序是很重要的，那你就只能使用LinkedHashSet或 LinkedHashMap了。 填充容器 和Arrays一樣，Collection也有一個叫Collections的輔助類，它包含了一些靜態的實用工具方法，其中就有一個fill()。這個 fill()也只是把同一個物件的reference複製到整個容器，而且它還只能為List，不能為Set和Map工作。容器的缺點：不知道物件的型別 Java的容器有個缺點，就是往容器裡面放物件的時候，會把物件的型別資訊給弄丟了。這是因為開發容器類的程式設計師不會知道你要用它來儲存什麼型別的物件，而讓容器僅只儲存特定型別的物件又會影響它的通用性。所以容器被做成只有持有Object，也就是所有物件的根類的reference，這樣它就能持有任何型別的物件了。（當然不包括primitive，因為它們不是物件，也沒有繼承別的物件。）這是一個很了不起的方案，只是： 1，由於在將物件放入容器的時候，它的型別資訊被扔掉了，所以容器對“能往裡面加什麼型別的物件”沒有限制。比方說，即使你想讓它只持有cat，別人也能很輕易地把dog放進去。 2，由於物件的型別資訊沒了，容器只知道它持有的Object的reference，所以物件在使用之前還必須進行型別轉換。 好的一面是，Java不會讓你誤用放進容器裡的物件。假設你往cat的容器裡面扔了個dog，然後要把這個容器裡的所有物件都當cat來用，當你把dog 的reference從cat的容器裡面拉出來，並且試圖將它轉換成cat的時候，就會引發一個RuntimeException。 ArrayList的用法也是很簡單：先建立一個，用add()把物件放進去，要用的時候再給get()傳一個下標－－就跟用陣列差不多，只是不需要用方括號了。ArrayList也有一個size()方法，它會告訴你容器裡面有多少物件，這樣你就不會粗心大意地過了界然後引發異常了。 有時即使不正確它也能執行 有時，即使不把物件轉換成原先的型別，它好像也能正常工作。有一種情況比較特殊：String能從編譯器哪裡得到一些能使之平穩工作的特殊幫助。只要編譯器沒能得到它所期望的String物件，它就會呼叫toString()。這個方法油Object定義，能被任何Java類覆寫。它所返回的String 物件，會被用到任何要用它的地方。 於是只要覆寫了類的toString()方法，你就能列印物件了。 做一個型別敏感的ArrayList 引數化型別（Parameterized types）迭代器 無論是哪種容器，你都得有辦法既能放東西進去，也能拿東西出來。畢竟，容器的主要任務就是存放物件。ArrayList的add()就是用來放東西的，而 get()則是把物件拿出來的辦法。ArrayList恨靈活；你可以隨時提取任何東西，並且換一個下標，馬上就能選擇另一個元素。 “迭代器（iterator 又是一個設計模式）”是一個物件，它的任務是，能在讓“客戶程式在不知道，或者不關心他所處理的是什麼樣的底層序列結構”的情況下，就能在一個物件序列中前後移動，並選取其中的物件。此外迭代器還是一種通常所說的“輕量級”的物件，既建立代價很小的物件。 Java的Iterator就屬於有這種限制的迭代器。它做不了很多事情，除了： 1，用iterator()方法叫容器傳給你一個Iterator物件。第一次呼叫Iterator的next()方法的時候，它就會傳給你序列中的第一個元素。 2，用next()方法獲取序列中的下一個物件。 3，用hasNext()方法查詢序列中是否還有其他物件。 4，用remove()方法刪除迭代器所返回的最後一個元素。 就這麼多了。這只是迭代器的一個恨簡單的實現，不過還是很強大（對List來說，還有一個更精巧的ListIterator）。 不經意的遞迴（Unintended recursion） 由於Java的標準容器類（同其它類一樣）也是繼承Object的，因此它們也有一個toString()方法。這個方法已經被覆寫了，所以它能生成一個表示它自己以及所有它所儲存的物件的String。比如ArrayList的toString()方法就會遍歷ArrayList的每個元素，然後呼叫它們的toString()方法。假設你要列印類的地址。好像最直接的辦法就是使用this。但是會出現很多異常，解決的辦法就是去呼叫Object的 toString()方法，它就是幹這活的。所以不要用this，應該寫super.toString()。容器分類學 根據程式設計的需要，Collection和Map分別有好幾個實現。實際上只有三種容器元件－－Map，List和Set，而每種又有兩到三個實現。 與存放物件有關的介面包括Collection, List, Set和Map。在理想情況下，絕大多數程式碼應該只同這些介面打交道，只是在建立容器的時候才要精確地指明它的確切型別。 add()，就像它的名字告訴我們的，會把新的元素放進Collection。但是文件裡面特別仔細地宣告，“add()會確保容器包含指定的元素”。這句話是說給Set的，因為它只新增原先沒有的元素，對ArrayList或其他List，add()總是“把它放進去”，因為List並不關心它是不是儲存了相同的元素。 Collection都能用iterator()方法產生一個Iterator。這裡，我們用Iterator來遍歷整個Collection，然後把他們打印出來。
方法/步驟
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的基本用法事相當將但的。雖然絕大多數時候，你只是用add()加物件，用get()取物件，用iterator()獲取這個序列的Iterator，但List還有一些別的很有用的方法。 實際上有兩種List：擅長對元素進行隨機訪問的，較常用的ArrayList，和更強大的LinkedList。LinkedList不是為快速的隨機訪問而設計的，但是它卻有一組更加通用的方法。 Lisk（介面）：List的最重要的特徵就是有序；它會確保以一定的順序儲存元素。List在Collection的基礎上添加了大量方法，使之能在序列中間插入和刪除元素。（只對LinkedList推薦使用。）List可以製造ListIterator物件，你除了能用它在List的中間插入和刪除元素之外，還能用它沿兩個方法遍歷List。 ArrayList*：一個用陣列實現的List。能進行快速的隨機訪問，但是往列表中間插入和刪除元素的時候比較慢。ListIterator只能用在反向遍歷ArrayList的場合，不要用它來插入和刪除元素，因為相比LinkedList，在ArrayList裡面用ListIterator的系統開銷比較高。 LinkedList：對順序訪問進行了優化。在List中間插入和刪除元素的代價也不高。隨機訪問的速度相對較慢。（用ArrayList吧。）此外它還有addFirst()，addLast()，getFirst()，getLast()，removeFirst()和removeLast()等方法（這些方法，介面和基類均未定義），你能把它當成棧（stack），佇列（queue）或雙向佇列（deque）來用。 記住，容器只是一個儲存物件的盒子。如果這個笑盒子能幫你解決所有的問題，那你就用不著取管它事怎麼實現的（在絕大多數情況下，這是使用物件的基本概念）。如果開發環境裡面還有一些別的，會造成固定的效能開銷的因素存在，那麼ArrayList和LinkedList之間的效能差別就會變得不那麼重要了。你只需要它們中的一個，你甚至可以想象有這樣一種“完美”的抽象容器；它能根據用途，自動地切換其底層的實現。 用LinkedList做一個棧 “棧（stack）”有時也被稱為“後進先出”（LIFO）的容器。就是說，最後一個被“壓”進棧中的東西，會第一個“彈”出來。同其他Java容器一樣，壓進去和彈出來的東西都是Object，所以除非你只用Object的功能，否則就必須對彈起來的東西進行型別轉換。 LinkedList的方法能直接實現棧的功能，所以你完全可以不寫Stack而直接使用LinkedList。 如果你只想要棧的功能，那麼繼承就不太合適了，因為繼承出來的是一個擁有LinkedList的所有方法的類。 用LinkedList做一個佇列 佇列（queue）是一個“先進先出”（FIFO）容器。也就是，你把一端把東西放進去，從另一端把東西取出來。所以你放東西的順序也就是取東西的順序。 LinkedList有支援佇列的功能的方法，所以它也能被當作Queue來用。 還能很輕易地用LinkedList做一個deque（雙向佇列）。它很像佇列，只是你可以從任意一端新增和刪除元素。
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的功能 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()來比較鍵的hash map。不是為我們平常使用而設計的，是用來解決特殊問題的。 雜湊是往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）演算法，這樣還沒被訪問過的元素（同時也是要刪除的候選物件）就會出現在佇列的最前頭。這樣，為節省資源而寫一個定時清理的程式就變得很簡單了。 雜湊演算法與Hash數 一個合適的equals()必須做到一下五點： 1 反身性：對任何x, x.equals(x)必須是true的。 2 對稱性：對任何x和y，如果y.equals(x)是true的，那麼 x.equals(y)也必須是true的。 3 傳遞性：對任何x，y和z，如果x.equals(y)是true的，且 y.equals(z)也是true的，那麼x.equals(z)也必須是true的。 4 一致性：對任何x和y，如果物件裡面用來判斷相等姓的資訊沒有修 改過，那麼無論呼叫多少次x.equals(y)，它都必須一致地返回 true或false。 5 對於任何非空的x，x.equals(null)必須返回false。 預設的Object.equals()只是簡單地比較兩個物件的地址。 如果你想把子集寫的類當HashMap的鍵來用的話，你就必須把hashCode()和equals（）都給覆寫了。 理解hashCode() 如果你不覆寫鍵的hashCode()和equals()的話，雜湊資料結構（HashSet，HashMap，LinkedHashSet，或LinkedHashMap）就沒法正確地處理鍵。 雜湊的價值就在於速度：雜湊演算法能很快地找出東西。 陣列是最快的資料結構。持有reference java.lang.ref類庫裡有一套能增進垃圾回收器工作的靈活性的類。一旦碰到了“物件達到要耗光記憶體”的時候，這些類就會閒的格外有用。有三個類是繼承抽象類Reference的：SoftReference，WeakReference和PhantomReference。如果待處理的物件只能通過這些Reference進行訪問的話，那麼這些Reference物件就會向垃圾回收器提供一些不同級別的暗事。 ……
總結： 總結Java標準類庫的容器類： 1。陣列把物件和數字形式的下標聯絡起來。它持有的是型別確定的物件，這樣提取物件的時候就不用再作型別傳遞了。它可以是多維的，也可以持有primitive。但是建立之後它的容量不能改了。 2。Collection持有單個元素，而Map持有相關聯的pair。 3。和陣列一樣，List也把數字下標同對象聯絡起來，你可以把陣列和List想成有序的容器。List會隨元素的增加自動調整容量。但是List只能持有Object reference，所以不能存放primitive，而且把Object提取出來之後，還要做型別傳遞。 4。如果要做很多隨機訪問，那麼請用ArrayList，但是如果要再List的中間做很多插入和刪除的話，就應該用LinkedList了。 5。LinkedList能提供佇列，雙向佇列和棧的功能。 6。Map提供的不是物件與陣列的關聯，而是物件和物件的關聯。 HashMap看重的是訪問速度，而TreeMap各國那看重鍵的順序，因而它不如HashMap那麼快。而LinkedHashMap則保持物件插入的順序，但是也可以用LRU演算法為它重新排序。 7。Set只接受不重複的物件。HashSet提供了最快的查詢速度。而TreeSet則保持元素有序。LinkedHashSet保持元素的插入順序。 8。沒必要再在新程式碼裡使用舊類庫留下來的Vector，Hashtable和Stack了。 容器類庫是你每天都會用到的工具，它能使程式更簡介，更強大並且更搞笑。