數組與其它容器的區別體現在三個方面：效率，類型識別以及可以持有primitives.
數組是java提供的，是能隨機存儲和訪問reference序列的諸多方法中，最高效的一種。數組是線形序列，所以它可以快速訪問其中的元素，但速度是有代價的，當你創建了一個數組之后它的容量就固定了，而且在其生命周期里不能改變。也許你會提議先創建一個數組，等到快不夠用的時候，再創建一個新的，然后將舊數組里的reference 全部導到新的里面。其實ArrayList 就是這么做的。但是這種靈活性所帶來的開銷，使得ArrayList 的效率比 起數組有了明顯下降。
在我們寫程序的時候往往不知道要用多少對象，或者要用一種更復雜方式來存儲對象情況。為此，Java 提供了“容器類(container
class)”。其基本類型有List,
Set 和Map。有了這些工具，你就能解決很多問題了。它們還有一些別的特性。比方說Set
所持有的對象，個個都不同，Map則是一個“關聯性數組(associative array)”，它能在兩個對象之間建立聯系。此外，與數組不同，它們還能自動調整大小，所以你可以往里面放任意數量的對象。這樣寫程序的時候，就不用操心要開多大的空間了。
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，以此類推)。我們先來看看容器的一般特性，然后深入細節，最后再看什么會有這么多版本，以及如何進行選擇。
List 會老老實實地持有你所輸入的所有對象，既不做排序也不做編輯。Set 則每個對象只接受一次，而且還要用它自己的規則對元素進行重新排序(一般情況下，你關心的只是Set
包沒包括某個對象，而不是它到底排在哪里——如果是那樣，你最好還是用List)。而Map 也不接收重復的pair，至于是不是重復，要由key來決定。此外，它也有它自己的內部排序規則，不會受輸入順序影響。如果插入順序是很重要的，那你就只能使用LinkedHashSet 或LinkedHashMap 了。
第一眼看到這張圖的時候，你會覺得很震撼。不過你馬上就會知道，實際上只有三種容器組件——Map，List 和Set，而每種又有兩到三個實現。最常用的幾個容器已經用粗黑線框了起來。看到這里，這張圖就不再那么令人望而生畏了。
用點號框起來的是interface，用虛線框起來的是abstract 類，實線
則表示普通的(“實體concrete”)類。點線的箭頭表示類實現了這個interface(或者，abstract 類表示部分實現了這個interface)。實線
箭頭表示這個類可以制造箭頭所指的那個類的對象。比如，Collection
能制造Iterator，而List 還能制造ListIterator(也能制造Iterator，因為List 是繼承自Collection 的)。
與存放對象有關的接口包括Collection，List，Set 和Map。在理想情況下，絕大多數代碼應該只同這些接口打交道，只是在創建容器的時候才要精確地指明它的確切類型。所以你可以這樣創建一個List。
List x = new LinkedList( );
當然，你也可以選擇讓x 成為LinkedList(而不是泛型的List)，這樣x 就帶上了準確的類型信息interface 的優雅 (同時也是它的本意)就在于，你想修改具體的實現的時候，只要改一下創建的聲明就可以了，就
像這樣：
List x = new ArrayList( );
無需驚動其它代碼(用迭代器也能獲得一些這種泛型性)。這個類系里面有很多以“Abstract”開頭的類，初看起來這可能會讓人有點不明白。實際上它們只是一些部分實現某個接口的辦成品。假如你要編一個你自己的Set，不要從Set 接口開始挨個實現它的方法；相反你最好繼承AbstractSet，這樣就能把編程的工作量壓縮到最低了。但是，實際上容器類庫的功能已經夠強的了，我們要求的事情它幾乎都能做
到。所以對我們來說，你完全可以忽略以“Abstract”開頭的類。
List 的功能
正如你從ArrayList 那里所看到的，List 的基本用法是相當簡單的。雖然絕大多數時候，你只是用add( )加對象，用get( )取對象，用iterator( )獲取這個序列的Iterator，但List 還有一些別的很有用的
方法。
實際上有兩種List：擅長對元素進行隨機訪問的，較常用的ArrayList，和更強大的LinkedList。LinkedList 不是為快速的隨機訪問而設計的，但是它卻有一組更加通用的方法。
| List (接口) | 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)來用。
下面這段程序把各種操作都集中到方法里面：List 都能作的事(basicTest( ))，用Iterator 在列表中移動(iterMotion( ))，修改
列表的元素(iterManipulation( ))，查看List 的操作結果(testVisual( ))，以及LinkedList 所獨有的方法。 |
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 的時候，
它是按插入順序進行訪問的。 |
Map 的功能ArrayList 能讓你用數字在一個對象序列里面進行選擇，所以從某種意義上講，它是將數字和對象關聯起來。但是，如果你想根據其他條件在一個對象序列里面進行選擇的話，那又該怎么做呢？從概念上講，它看上去像是一個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 里存數據的常用算法。有時你會需要知道散列算法的工作
細節，所以我們會稍后再講。 |