數組是 Java 語言內置的類型，除此之外， Java 有多種保存對象引用的方式。 Java 類庫提供了一套相當完整的容器類，使用這些類的方法可以保存和操縱對象。下面分別進行討論，在研究Java 容器類之前，先了解一下Java 數組的基本功能和特性。

　　1. 數組的基本特性

　　數組與其它種類的容器 (List/Set /Map) 之間的區別在于效率、確定的類型和保存基本類型數據的能力。數組是一種高效的存儲和隨機訪問對象引用序列的方式，使用數組可以快速的訪問數組中的元素。但 是當創建一個數組對象 ( 注意和對象數組的區別 ) 后，數組的大小也就固定了，當數組空間不足的時候就再創建一個新的數組，把舊的數組中所有的引用復制到新的數組中。

　　Java 中的數組和容器都需要進行邊界檢查，如果越界就會得到一個 RuntimeException 異常。這點和 C++ 中有所不同， C++ 中 vector 的操作符 [] 不會做邊界檢查，這在速度上會有一定的提高， Java 的數組和容器會因為時刻存在的邊界檢查帶來一些性能上的開銷。

　　Java 中通用的容器類不會以具體的類型來處理對象，容器中的對象都是以 Object 類型處理的，這是 Java 中所有類的基類。另外，數組可以保存基本類型，而容器不能，它只能保存任意的 Java 對象。

　　一般情況下，考慮到效率與類型檢查，應該盡可能考慮使用數組。如果要解決一般化的問題，數組可能會受到一些限制，這時可以使用 Java 提供的容器類。

　　2. 操作數組的實用功能

　　在 java .util.Arrays 類中，有許多 static 靜態方法，提供了操作數組的一些基本功能：

　　equals() 方法 ---- 用于比較兩個數組是否相等，相等的條件是兩個數組的元素個數必須相等，并且對應位置的元素也相等。

　　fill() 方法 ---- 用以某個值填充整個數組，這個方法有點笨。

　　asList() 方法 ---- 接受任意的數組為參數，將其轉變為 List 容器。

　　binarySearch() 方法 ---- 用于在已經排序的數組中查找元素，需要注意的是必須是已經排序過的數組。當 Arrays.binarySearch() 找到了查找目標時，該方法將返回一個等于或大于 0 的值，否則將返回一個負值，表示在該數組目前的排序狀態下此目標元素所應該插入的位置。負值的計算公式是 “-x-1” 。 x 指的是第一個大于查找對象的元素在數組中的位置，如果數組中所有的元素都小于要查找的對象，則 x = a.size() 。如果數組中包含重復的元素，則無法保證找到的是哪一個元素，如果需要對沒有重復元素的數組排序，可以使用 TreeSet 或者 LinkedHashSet 。另外，如果使用 Comparator 排序了某個對象數組，在使用該方法時必須提供同樣的 Comparator 類型的參數。需要注意的是，基本類型數組無法使用 Comparator 進行排序。

　　sort() 方法 ---- 對數組進行升序排序。

　　在 Java 標準類庫中，另有 static 方法 System.arraycopy() 用來復制數組，它針對所有類型做了重載。

　　3. 數組的排序

　　在 Java1.0 和 1.1 兩個版本中，類庫缺少基本的算法操作，包括排序的操作， Java2 對此進行了改善。在進行排序的操作時，需要根據對象的實際類型執行比較操作，如果為每種不同的類型各自編寫一個不同的排序方法，將會使得代碼很難被復用。 一般的程序設計目標應是“將保持不變的事物與會發改變的事物相分離”。在這里，不變的是通用的排序算法，變化的是各種對象相互比較的方式。

　　Java 有兩種方式來實現比較的功能，一種是實現 java .lang.Comparable 接口，該接口只有一個 compareTo() 方法，并以一個 Object 類為參數，如果當前對象小于參數則返回負值，如果相等返回零，如果當前對象大于參數則返回正值。另一種比較方法是采用策略 (strategy) 設計模式，將會發生變化的代碼封裝在它自己的類 ( 策略對象 ) 中，再將策略對象交給保持不變的代碼中，后者使用此策略實現它的算法。因此，可以為不同的比較方式生成不同的對象，將它們用在同樣的排序程序中。在此情況 下，通過定義一個實現了 Comparator 接口的類而創建了一個策略，這個策略類有 compare() 和 equals() 兩個方法，一般情況下實現 compare() 方法即可。

　　使用上述兩種方法即可對任意基本類型的數組進行排序，也可以對任意的對象數組進行排序。再提示一遍，基本類型數組無法使用 Comparator 進行排序。

　　Java 標準類庫中的排序算法針對排序的類型進行了優化——針對基本類型設計了“快速排序”，針對對象設計的“穩定歸并排序”。一般不用擔心其性能。

　　Java 容器分析--List和Set

　　容器類可以大大提高編程效率和編程能力，在Java2 中，所有的容器都由 SUN 公司的 Joshua Bloch 進行了重新設計，豐富了容器類庫的功能。

　　Java2 容器類類庫的用途是“保存對象”，它分為兩類：

　　Collection ---- 一組獨立的元素，通常這些元素都服從某種規則。 List 必須保持元素特定的順序，而 Set 不能有重復元素。

　　Map ---- 一組成對的“鍵值對”對象，即其元素是成對的對象，最典型的應用就是數據字典，并且還有其它廣泛的應用。另外， Map 可以返回其所有鍵組成的 Set 和其所有值組成的 Collection ，或其鍵值對組成的 Set ，并且還可以像數組一樣擴展多維 Map ，只要讓 Map 中鍵值對的每個“值”是一個 Map 即可。

　　1. 迭代器

　　迭代器是一種設計模式，它是一個對象，它可以遍歷并選擇序列中的對象，而開發人員不需要了解該序列的底層結構。迭代器通常被稱為“輕量級”對象， 因為創建它的代價小。

　　Java 中的 Iterator 功能比較簡單，并且只能單向移動：

　　(1) 使用方法 iterator() 要求容器返回一個 Iterator 。第一次調用 Iterator 的 next() 方法時，它返回序列的第一個元素。

　　(2) 使用 next() 獲得序列中的下一個元素。

　　(3) 使用 hasNext() 檢查序列中是否還有元素。

　　(4) 使用 remove() 將迭代器新返回的元素刪除。

　　Iterator 是 Java 迭代器最簡單的實現，為 List 設計的 ListIterator 具有更多的功能，它可以從兩個方向遍歷 List ，也可以從 List 中插入和刪除元素。

　　2.List 的功能方法

　　List(interface): 次序是 List 最重要的特點；它確保維護元素特定的順序。 List 為 Collection 添加了許多方法，使得能夠向 List 中間插入與移除元素 ( 只推薦 LinkedList 使用 ) 。一個 List 可以生成 ListIterator ，使用它可以從兩個方向遍歷 List ，也可以從 List 中間插入和刪除元素。

　　ArrayList: 由數組實現的 List 。它允許對元素進行快速隨機訪問，但是向 List 中間插入與移除元素的速度很慢。 ListIterator 只應該用來由后向前遍歷 ArrayList ，而不是用來插入和刪除元素，因為這比 LinkedList 開銷要大很多。

　　LinkedList: 對順序訪問進行了優化，向 List 中間插入與刪除得開銷不大，隨機訪問則相對較慢 ( 可用 ArrayList 代替 ) 。它具有方法 addFirst() 、 addLast() 、 getFirst() 、 getLast() 、 removeFirst() 、 removeLast() ，這些方法 ( 沒有在任何接口或基類中定義過 ) 使得 LinkedList 可以當作堆棧、隊列和雙向隊列使用。

　　3.Set 的功能方法

　　Set (interface): 存入 Set 的每個元素必須是唯一的，因為 Set 不保存重復元素。加入 Set 的 Object 必須定義 equals() 方法以確保對象的唯一性。 Set 與 Collection 有完全一樣的接口。 Set 接口不保證維護元素的次序。

　　HashSet: 為快速查找而設計的 Set 。存入 HashSet 的對象必須定義 hashCode() 。

　　TreeSet: 保持次序的 Set ，底層為樹結構。使用它可以從 Set 中提取有序的序列。

　　LinkedHashSet: 具有 HashSet 的查詢速度，且內部使用鏈表維護元素的順序 ( 插入的次序 ) 。于是在使用迭代器遍歷 Set 時，結果會按元素插入的次序顯示。

　　HashSet 采用散列函數對元素進行排序，這是專門為快速查詢而設計的； TreeSet 采用紅黑樹的數據結構進行排序元素； LinkedHashSet 內部使用散列以加快查詢速度，同時使用鏈表維護元素的次序，使得看起來元素是以插入的順序保存的。需要注意的是，生成自己的類時， Set 需要維護元素的存儲順序，因此要實現 Comparable 接口并定義 compareTo() 方法。

　　Java 容器分析--Map

　　標準的Java 類庫中包含了幾種類型的 Map ，它們都擁有同樣的基本接口 Map ，但是行為特性各不相同，主要表現在效率、鍵值對的保存、元素呈現次序、對象的保存周期和判定鍵是否等價的策略等方面。

　　1.Map 的功能方法

　　Map(interface): 維護 label 和 value 的關聯性，使得可以通過 label 查找 value 。

　　HashMap: Map 基于散列表的實現，取代了 Hashtable 。插入和查詢 label/value 的開銷是固定的，并且可以通過構造器設置容量和負載因子，以調整容器的性能。

　　LinkedHashMap: 在 HashMap 的基礎上做了一些改進，在迭代遍歷它時，取得 label/value 的順序是其插入的次序，或者是最近最少使用 (LRU) 的次序，速度上比 HashMap 要慢一點，但在迭代訪問時速度會更快，主要原因是它使用了鏈表維護內部次序。

　　TreeMap: 查看 label 或 label/value 時，元素會被排序，其次序由 Comparable 或 Comparator 決定，因此查詢所得到的結果是經過排序的。另外，它是唯一帶有 subMap() 方法的 Map 具體類，即返回一個子樹。它也是 SortedMap 接口的唯一實現， subMap() 方法也是從該接口繼承的。

　　WeakHashMap: Weak Key 映射，允許釋放映射所指向的對象。當映射之外沒有引用指向某個 label 時，此 label 可以被垃圾收集器回收。

　　IdentityHashMap: 使用 == 代替 equals() 對 label 進行比較的散列映射。

　　2.hashCode()

　　當使用標準庫中的類 Integer 作為 HashMap 的 label 時，程序能夠正常運行，但是使用自己創建的類作為 HashMap 的 label 時，通常犯一個錯誤。

　　在 HashMap 中通過 label 查找 value 時，實際上是計算 label 對象地址的散列碼來確定 value 的。一般情況下，我們是使用基類 Object 的方法 hashCode() 來生成散列碼，它默認是使用對象的地址來計算的，因此由第一個對象 new Apple(5) 和第二個對象 new Apple(5) 生成的散列碼是不同的，不能完成正確的查找。通常，我們可以編寫自己的 hashCode() 方法來覆蓋基類的原始方法，但與此同時，我們必須同時實現 equals() 方法來判斷當前的 label 是否與表中存在的 label 相同。正確的 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) 對任何不是 null 的 x ， x.equals(null) 一定返回 false 。

equals() 比較的是對象的地址，如果要使用自己的類作為 HashMap 的 label ，必須同時重載 hashCode() 和 equals() 方法。

　　使用散列的目的：想要使用一個對象來查找另一個對象。使用 TreeSet 或 TreeMap 也能實現此目的。另外，還可以自己實現一個 Map ，此時，必須提供 Map.entrySet() 方法來生成 Map.Entry 對象的 Set 。

　　使用散列的價值：速度，散列使得查詢可以快速進行。散列將 label 保存載數組中方便快速查詢，因為存儲一組元素最快的數據結構是數組，用它來表示 label 的信息 ( 后面有信息的描述 ) ，而不是 label 本身。通過 label 對象計算得到一個數字，作為數組的下標，這個數字就是散列碼 ( 即前面所述的信息 ) 。該散列碼具體是通過定義在基類 Object 中，可能由程序員自定義的類覆蓋的 hashCode() 方法，即散列函數生成。為了解決數組容量帶來的限制，可以使不同的 label 生成相同的下標，保存在一個鏈表 list 中，每一個鏈表就是數組的一個元素。查詢 label 時就可以通過對 list 中的信息進行查找，當散列函數比較好，數組的每個位置中的 list 長度較短，則可以快速查找到數組元素 list 中的某個位置，提高了整體速度。

　　散列表中的 slot 通常稱為 bucket ，為了使散列分步均勻， bucket 的值一般取質數。但事實證明，質數實際上并不是散列 bucket 的理想容量，近來 Java 散列實現都使用 2 的冪，具體如何驗證以后再續。

　　3.HashMap 的性能因子

　　容量 (capacity): 散列表中 bucket 的數量。

　　初始化容量 (initial capacity): 創建散列表時 bucket 的數量。可以在構造方法中指定 HashMap 和 HashSet 的初始化容量。

　　尺寸 (size): 散列表中記錄的數量。 ( 數組的元素個數，非 list 中元素總和 )

　　負載因子 (load factor): 尺寸 / 容量。負載因子為 0 ，表示空的散列表， 0.5 表示半滿的散列表。輕負載的散列表具有沖突少，適宜插入與查詢的特點，但是使用迭代器遍歷會比較慢。較高的負載會減少所需空間大小。當負載達到指定值時， 容器會自動成倍地增加容量，并將原有的對象重新分配，存入新的 bucket 中，這個過程稱為“重散列”。

　　4. 重寫 hashCode() 的關鍵

　　(1) 對同一個對象調用 hashCode() 都應該生成同樣的值。

　　(2) hashCode() 方法不要依賴于對象中易變的數據，當數據發生變化時， hashCode() 就會生成一個不同的散列碼，即產生了一個不同的 label 。

　　(3) hashCode() 不應依賴于具有唯一性的對象信息，例如對象地址。

　　(4) 散列碼應該更關心速度，而不是唯一性，因為散列碼不必是唯一的。

　　(5) 好的 hashCode() 應該產生分步均勻的散列碼。在 Effective Java (Addison-Wesley 2001) 中， Joshua Bloch 給 hashCode() 給出了設計指導，可以參考。

　　編寫正確高效的 hashCode() 和 equals() 可以參考 Apache 的 Jakarta Commons 項目中的工具。

　　java 集合類總結

　　對象的集合

　　如果程序的對象數量有限，且壽命可知，那么這個程序是相當簡單的。

　　數組

　　數組與其它容器的區別體現在三個方面：效率，類型識別以及可以持有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。

　　primitive容器

　　容器類只能持有Object對象的reference。而數組除了能持有Objects的reference之外，還可以直接持有 primitive。當然可以使用諸如Integer，Double之類的wrapper類。把primitive的值放到容器中，淡這樣總有點怪怪的。 此外， primitive數組的效率要比wrapper類容器的高出許多。

　　當然，如果你使用primitive的時候，還需要那種“能隨需要自動擴展的”容器類的靈活性，那就不能用數組了。你只能用容器來存儲 primitive的wrapper類。

　　返回一個數組

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

　　Arrays類

　　java .util 里面有一個Arrays類，它包括了一組可用于數組的static方法，這些方法都是一些實用工具。其中有四個基本方法：用來比較兩個數組是否相等的 equals()；用來填充的fill()；用來對數組進行排序的sort()；以及用于在一個已排序的數組中查找元素的 binarySearch()。所有這些方法都對primitive和Object進行了重載。此外還有一個asList()方法，它接受一個數組，然后 把它轉成一個List容器。

　　雖然Arrays還是有用的，但它的功能并不完整。舉例來說，如果它能讓我們不用寫for循環就能直接打印數組，那就好了。此外，正如你所看到的 fill()只能用一個值填數組。所以，如果你想把隨即生成的數字填進數組的話，fill()是無能為力的。

　　復制一個數組

　　Java 標準類庫提供了一個System.arraycopy()的static方法。相比for循環，它能以更快的速度拷貝數組。 System.arraycopy()對所有類型都作了重載。

　　對象數組和primitive數組都能拷貝。但是如果你拷貝的是對象數組，那么你只拷貝了它們的reference－－對象本身不會被拷貝。這被 成為淺拷貝（shallow copy）。

　　數組的比較

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

　　數組元素的比較

　　Java 里面有兩種能讓你實現比較功能的方法。一是實現java .lang.Comparable 接口，并以此實現類“自有的”比較方法。這是一個很簡單的接口，它只有一個方法compareTo()。這個方法能接受另一個對象作為參數，如果現有對象 比參數小，它就會返回一個負數，如果相同則返回零，如果現有的對象比參數大，它就返回一個正數。

　　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()方法會根據第一個參數是小于，等于還是大于第二個參數，分別返回負整數，零或是正整數。

　　數組的排序

　　有了內置的排序方法之后，你就能對任何數組排序了，不論是primitive的還是對象數組的，只要它實現了Comparable接口或有一個與 之相關的Comparator對象就行了。

　　Java 標準類庫所用的排序算法已經作了優化－－對primitive，它用的是“快速排序（Quicksort）”，對對象，它用的是“穩定合并排序 （stable merge sort）”。所以除非是prolier表明排序算法是瓶頸，否則你不用為性能擔心。

　　查詢有序數組

　　一旦數組排完序，你就能用Arrays.binarySearch()進行快速查詢了。但是切忌對一個尚未排序的數組使用 binarySearch()；因為這么做的結果是沒意義的。

　　如果Arrays.binarySearch()找到了，它就返回一個大于或等于0的值。否則它就返回一個負值，而這個負值要表達的意思是，如果 你手動維護這個數組的話，這個值應該插在哪個位置。