Java8程式設計思想精粹(十)-容器(上)

如果一個程式隻包含固定數量的對象且對象的生命周期都是已知的，那麼這是一個非常簡單的程式。

• 程式設計痛點

  通常程式總是根據運作時才知道某些條件,進而去建立新的對象。

  在此之前，無法知道所需對象的數量甚至确切類型。

• 解決方案

  需要在任意時刻和任意位置建立任意數量的對象。

  是以，不能再簡單地這樣依靠建立命名的引用來持有每一個對象：

MyType aReference;      

因為你不會知道實際上到底需要多少個這樣的引用。

Java有多種方式儲存對象的引用。例如數組，這種編譯器支援的類型,是儲存一組對象的最有效的方式，如果想要儲存一組基本類型資料，也推薦使用數組。

但數組具有固定容量，而在更一般情況下，寫程式時我們并不知道

将需要多少個對象

是否需要更複雜的方式來存儲對象

是以數組這一限制過于受限。

java.util 庫提供了一套相當完整的集合類（collection classes）來解決這個問題，其中基本的類型有 List 、 Set 、 Queue 和 Map。也稱作容器類（container classes）。集合提供了完善的方法來儲存對象，可以使用這些工具來解決大量的問題。

集合還有一些其它特性。例如，

Set 對于每個值都隻儲存一個對象

Map 是一個關聯數組，允許将某些對象與其他對象關聯起來

Java集合類都可動态調整容量。可将任意數量的對象放置在集合中，而不用關心集合應該多大。

盡管在 Java 中沒有直接的關鍵字支援，但集合類仍然是可以顯著增強程式設計能力的基本工具。

1 泛型和類型安全的集合

Java5 之前的集合的一個主要問題是編譯器準許SE向集合中插入不正确類型。

例如， Apple 對象的集合，使用最基本最可靠的 ArrayList ,可自動擴充自身容量的數組。

建立一個執行個體，用 add() 插入對象；get() 通路對象，此時需要使用索引，就像數組那樣，但無需方括号。size() 方法說明集合中包含了多少個元素，是以不會不小心因數組越界而引發錯誤。

如下示例, Apple 和 Orange 都被放到集合，然後取出。

正常情況下，Java編譯器會給出警告，因為這裡沒有使用泛型。使用

@SuppressWarning

注解及其參數表示隻抑制“unchecked”類型的警告.

• 運作結果

• 

• Apple 和 Orange 是截然不同的，它們除了都是 Object 外沒有任何共同點。

因為 ArrayList 儲存的是 Object ，是以不僅可以通過 ArrayList 的 add() 方法将 Apple 對象放入這個集合，而且可以放入 Orange 對象，這無論在編譯期還是運作時都不會有問題。

當使用 ArrayList 的 get() 方法來取出你認為是 Apple 的對象時，得到的其實是 Object 引用，必須轉型為 Apple。

然後将整個表達式用括号括起來，以便在調用 Apple 的 id() 方法之前，強制執行轉型。

否則，将會産生文法錯誤。

在運作時，當嘗試将 Orange 對象轉為 Apple 時，會出現輸出中顯示的錯誤。

使用 Java 泛型來建立類可能很複雜。但是，使用預先定義的泛型類卻相當簡單。例如，要定義一個用于儲存 Apple 對象的 ArrayList ，隻需要使用 ArrayList\ 來代替 ArrayList 。

尖括号括起來的是類型參數（可能會有多個），指定了這個集合執行個體可以儲存的類型。

通過使用泛型，就可以在編譯期防止将錯誤類型的對象放置到集合中。

泛型版本示例

new ArrayList<>()

,“菱形文法”（diamond syntax）。在 Java7 之前，必須要在兩端都進行類型聲明，如下：

ArrayList<Apple> apples = new ArrayList<Apple>();      

随着類型變得越來越複雜，這種重複産生的代碼非常混亂且難以閱讀。程式員發現所有類型資訊都可以從左側獲得，是以，編譯器沒有理由強迫右側再重複這些。

雖然類型推斷（type inference）隻是個很小的請求，Java 語言團隊仍然欣然接受并進行了改進。

有了 ArrayList 聲明中的類型指定，編譯器會阻止将 Orange 放入 apples ，是以，這會成為一個編譯期錯誤而不是運作時錯誤。

好處

使用泛型，從 List 中擷取元素無需強制類型轉換。

因為 List 知道自己持有的啥類型，是以當調用 get() 時，它會替你執行轉型。

是以，使用泛型，你不僅知道編譯器将檢查放入集合的對象類型，而且在使用集合中的對象時也可以獲得更清晰的文法。

泛型下的向上轉型

當指定了某個類型為泛型參數時，并不僅限于隻能将确切類型的對象放入集合中。

向上轉型也可以像作用于其他類型一樣作用于泛型：

是以，可以将 Apple 的子類型添加到被指定為儲存 Apple 對象的集合中。

2 基本概念

Java集合類庫采用“持有對象”（holding objects）的思想，并将其分為兩個不同的概念，表示為類庫的基本接口：

集合（Collection） ：

一個獨立元素的序列，這些元素都服從一條或多條規則。

List 必須以插入的順序儲存元素

Set 不能包含重複元素

Queue 按照排隊規則來确定對象産生的順序（通常與它們被插入的順序相同）。

   2. 映射（Map） ：

一組成對的“鍵值對”對象，允許使用鍵來查找值。

ArrayList 使用數字來查找對象，是以在某種意義上講，它是将數字和對象關聯在一起。

map 允許我們使用一個對象來查找另一個對象，它也被稱作關聯數組（associative array），因為它将對象和其它對象關聯在一起；

或者稱作字典（dictionary），因為可以使用一個鍵對象來查找值對象，就像在字典中使用單詞查找定義一樣。

在理想情況下，大部分代碼都在與這些接口打交道，并且唯一需要指定所使用的精确類型的地方就是在建立的時候。

是以，可以像下面這樣建立一個 List ：

List<Apple> apples = new ArrayList<>();      

ArrayList 已經被向上轉型為了 List ，這與之前示例中的處理方式正好相反。

使用接口的目的是，如果想要改變具體實作，隻需在建立時修改它即可:

List<Apple> apples = new LinkedList<>();      

是以，應該建立一個具體類的對象，将其向上轉型為對應的接口，然後在其餘代碼中都是用這個接口。

這種方式并非總是有效的，因為某些具體類有額外的功能。

例如， LinkedList 具有 List 接口中未包含的額外方法，而 TreeMap 也具有在 Map 接口中未包含的方法。

如果需要使用這些方法，就不能将它們向上轉型為更通用的接口。

3  添加元素組

在 java.util 包中的 Arrays 和 Collections 類中都有很多實用的方法，可以在一個 Collection 中添加一組元素。

• Arrays.asList() 方法接受一個數組或是逗号分隔的元素清單（使用可變參數），并将其轉換為 List 對象。

Collections.addAll() 方法接受一個 Collection 對象，以及一個數組或是一個逗号分隔的清單，将其中元素添加到 Collection 中

Collection 的構造器可以接受另一個 Collection，用它來将自身初始化。是以，可以使用 Arrays.asList() 來為這個構造器産生輸入。但是， Collections.addAll() 運作得更快，而且很容易建構一個不包含元素的 Collection ，然後調用 Collections.addAll() ，是以這是首選方式。

Collection.addAll() 方法隻能接受另一個 Collection 作為參數，沒有 Arrays.asList() 或 Collections.addAll() 靈活。這兩個方法都使用可變參數清單。

也可以直接使用 Arrays.asList() 的輸出作為一個 List ，但是這裡的底層實作是數組，沒法調整大小。

4 列印集合

必須使用

Arrays.toString()

來生成數組的可列印形式。但列印集合無需任何幫助。

Java集合庫中的兩個主要類型。它們的差別在于集合中的每個“槽”（slot）儲存的元素個數。

Collection 類型在每個槽中隻能儲存一個元素。

Map 在每個槽中存放了兩個元素，即鍵和與之關聯的值。

預設的列印

使用集合提供的

toString()

方法即可生成可讀性很好的結果。

Collection 列印出的内容用方括号包覆，每個元素由逗号分隔。

Map 則由大括号包覆，每個鍵和值用等号連接配接（鍵在左側，值在右側）。

ArrayList 和 LinkedList 都是 List 的類型，從輸出中可以看出，它們都按插入順序儲存元素。兩者之間的差別不僅在于執行某些類型的操作時的性能，而且 LinkedList 包含的操作多于 ArrayList 。

HashSet ， TreeSet 和 LinkedHashSet 是 Set 的類型。Set 僅儲存每個相同項中的一個，并且不同的 Set 實作存儲元素的方式也不同。HashSet 使用相當複雜的方法存儲元素。現在隻需要知道，這種技術是檢索元素的最快方法，是以，存儲順序看上去沒有什麼意義（通常隻關心某事物是否是 Set 的成員，而存儲順序并不重要）。如果存儲順序很重要，則可以使用 TreeSet ，它将按比較結果的升序儲存對象）或 LinkedHashSet ，它按照被添加的先後順序儲存對象。

Map （也稱為關聯數組）使用鍵來查找對象，就像一個簡單的資料庫。所關聯的對象稱為值。假設有一個 Map 将美國州名與它們的首府聯系在一起，如果想要俄亥俄州（Ohio）的首府，可以用“Ohio”作為鍵來查找，幾乎就像使用數組下标一樣。正是由于這種行為，對于每個鍵， Map 隻存儲一次。

Map.put(key, value) 添加一個所想要添加的值并将它與一個鍵（用來查找值）相關聯。Map.get(key) 生成與該鍵相關聯的值。上面的示例僅添加鍵值對，并沒有執行查找。這将在稍後展示。

Map 的三種基本風格：HashMap ， TreeMap 和 LinkedHashMap 。

HashMap 中的順序不是插入順序，其使用了非常快速的查找算法

TreeMap 通過比較結果的升序來儲存鍵，

LinkedHashMap 在保持 HashMap 查找速度的同時按鍵的插入順序儲存鍵。

5 List

将元素儲存在特定的序列中。在 Collection 的基礎上添加了許多方法，允許在 List 的中間插入和删除元素。

有兩種類型 List ：

基本的 ArrayList ，擅長随機通路元素，但在 List 中間插入和删除元素時速度較慢。

LinkedList ，它通過代價較低的在 List 中間進行的插入和删除操作，提供了優化的順序通路。

LinkedList 對于随機通路來說相對較慢，但它具有比 ArrayList 更大的特征集。

常用方法

可以使用 contains() 方法确定對象是否在清單中

如果要删除一個對象，可以将該對象的引用傳遞給 remove() 方法

如果有一個對象的引用，可以使用 indexOf() 在 List 中找到該對象所在位置的下标号

當确定元素是否是屬于某個 List ，尋找某個元素的索引，以及通過引用從 List 中删除元素時，都會用到 equals() 方法。

是否永遠不應該在 ArrayList 的中間插入元素，并最好轉換為 LinkedList ？

不，它隻是意味着你應該意識到這個問題，如果你開始在某個 ArrayList 中間執行很多插入操作，并且程式開始變慢，那麼你應該看看你的 List 實作有可能就是罪魁禍首。

優化是一個很棘手的問題，最好的政策就是置之不顧，直到發現必須要去擔心它了（盡管去了解這些問題總是一個很好的主意并且國内面試必備）。

subList() 方法可以輕松地從更大的清單中建立切片，當将切片結果傳遞給原來這個較大的清單的 containsAll() 方法時，很自然地會得到 true。

retainAll() 方法實際上是一個“集合交集”操作，請再次注意，所産生的結果行為依賴于 equals() 方法。

使用索引号來删除元素與通過對象引用來删除元素相比，顯得更加直覺，因為在使用索引時，不必擔心 equals() 的行為。

removeAll() 方法也是基于 equals() 方法運作的。顧名思義，它會從 List 中删除在參數 List 中的所有元素。

set() 方法的命名顯得很不合時宜，因為它與 Set 類存在潛在的沖突。使用“replace”可能更适合，因為它的功能是用第二個參數替換索引處的元素（第一個參數）。

對于 List ，有一個重載的 addAll() 方法可以将新清單插入到原始清單的中間位置，而不是僅能用 Collection 的 addAll() 方法将其追加到清單的末尾。

toArray() 方法将任意的 Collection 轉換為數組。這是一個重載方法，其無參版本傳回一個 Object 數組，但是如果将目标類型的數組傳遞給這個重載版本，那麼它會生成一個指定類型的數組（假設它通過了類型檢查）。如果參數數組太小而無法容納 List 中的所有元素（就像本例一樣），則 toArray() 會建立一個具有合适尺寸的新數組。

6 疊代器Iterators

在任何集合中，都必須有某種方式可以插入元素并再次擷取它們。畢竟，儲存事物是集合最基本的工作。

對于 List ， add() 是插入元素的一種方式， get() 是擷取元素的一種方式。

如果從更高層次的角度考慮，會發現這裡有個缺點：要使用集合，必須對集合的确切類型程式設計。

如果原本是 List 編碼，後來發現 Set 更友善

或者假設一開始就想編寫一段通用代碼，不關心正在使用什麼類型集合，可以用于不同類型集合

即,如何才能不重寫代碼就可以應用于不同類型的集合？

疊代器（也是一種設計模式）的概念實作了這種抽象。

疊代器是一個對象，它在一個序列中移動并選擇該序列中的每個對象，而用戶端程式員不知道或不關心該序列的底層結構。

疊代器通常被稱為輕量級對象：建立它的代價小。Java 的 Iterator 隻能單向移動。這個 Iterator 隻能用來：

iterator()

要求集合傳回一個 Iterator。

Iterator 将準備好傳回序列中的第一個元素。

next()

獲得序列中的下一個元素。

hasNext()

檢查序列中是否還有元素。

remove()

将疊代器最近傳回的那個元素删除。

有了 Iterator ，就不必再為集合中元素的數量操心了。這是 hasNext() 和 next() 關心的。

如果隻向前周遊 List ，并不打算修改 List 對象本身，那麼使用 for-in 更簡潔。

Iterator 還可删除由 next() 生成的最後一個元素，這意味着在調用 remove() 之前必須先調用 next() 。

在集合中的每個對象上執行操作，這種思想十分強大

Iterator 的真正威力：将周遊序列的操作與該序列的底層結構分離。

基于此，我們說：疊代器統一了對集合的通路方式。

ListIterator

更強大的 Iterator 子類型，隻能由各種 List 類生成。

Iterator 隻能向前移動，而 ListIterator 可以雙向移動。還可以生成相對于疊代器在清單中指向的目前位置的後一個和前一個元素的索引，并且可以使用 set() 方法替換它通路過的最近一個元素。

可通過調用 listIterator() 方法來生成指向 List 開頭的 ListIterator ，還可以通過調用 listIterator(n) 建立一個一開始就指向清單索引号為 n 的元素處的 ListIterator 。

連結清單LinkedList

LinkedList 像 ArrayList 一樣實作了基本的 List 接口，但它在 List 中間執行插入和删除操作時比 ArrayList 更高效。然而,它在随機通路操作效率方面卻要遜色一些。

LinkedList 還添加了一些方法，使其可以被用作棧、隊列或雙端隊列（deque） 。這些方法有些可能隻是名稱差異，以使得這些名字在特定用法的上下文環境中更加适用（特别是在 Queue 中）。例如：

getFirst() 和 element() ，傳回清單的頭部而并不删除它，如果 List 為空，則抛出NoSuchElementException 。

peek() 方法與這兩個方法隻是稍有差異，它在清單為空時傳回 null 。

removeFirst() 和 remove() ，删除并傳回清單的頭部元素，并在清單為空時抛出 NoSuchElementException 異常。

poll() 稍有差異，它在清單為空時傳回 null 。

addFirst() 在清單的開頭插入一個元素。

offer() 與 add() 和 addLast() 。

在清單的尾部（末尾）添加一個元素。

removeLast() 删除并傳回清單的最後一個元素。

檢視 Queue 接口就會發現，它在 LinkedList 的基礎上添加了 element() ， offer() ， peek() ， poll() 和 remove() 方法，以使其可以成為一個 Queue 的實作。