電腦程式的思維邏輯 (55) - 容器類總結

本節從三個角度簡要總結之前介紹的各種容器類：用法和特點，數據結構和演算法，設計思維和模式。 ...

從38節到54節，我們介紹了多種容器類，本節進行簡要總結，我們主要從三個角度進行總結：

用法和特點
數據結構和演算法
設計思維和模式

用法和特點

我們在52節展示過一張圖，其中包含了容器類主要的介面和類，我們還是用這個圖總結一下：

容器類有兩個根介面，分別是Collection和Map，Collection表示單個元素的集合，Map表示鍵值對的集合。

Collection表示的數據集合有基本的增、刪、查、遍歷等方法，但沒有定義元素間的順序或位置，也沒有規定是否有重覆元素。

List是Collection的子介面，表示有順序或位置的數據集合，增加了根據索引位置進行操作的方法。它有兩個主要的實現類，ArrayList和LinkedList，ArrayList基於數組實現，LinkedList基於鏈表實現，ArrayList的隨機訪問效率很高，但從中間插入和刪除元素需要移動元素，效率比較低，LinkedList則正好相反，隨機訪問效率比較低，但增刪元素只需要調整鄰近節點的鏈接。

Set也是Collection的子介面，它沒有增加新的方法，但保證不含重覆元素。它有兩個主要的實現類，HashSet和TreeSet，HashSet基於哈希表實現，要求鍵重寫hashCode方法，效率更高，但元素間沒有順序，TreeSet基於排序二叉樹實現，元素按比較有序，元素需要實現Comparable介面，或者創建TreeSet時提供一個Comparator對象。HashSet還有一個子類LinkedHashSet可以按插入有序。還有一個針對枚舉類型的實現類EnumSet，它基於位向量實現，效率很高。

Queue是Collection的子介面，表示先進先出的隊列，在尾部添加，從頭部查看或刪除。Deque是Queue的子介面，表示更為通用的雙端隊列，有明確的在頭或尾進行查看、添加和刪除的方法。普通隊列有兩個主要的實現類，LinkedList和ArrayDeque，LinkedList基於鏈表實現，ArrayDeque基於迴圈數組實現，一般而言，如果只需要Deque介面，ArrayDeque的效率更高一些。

Deque還有一個特殊的實現類PriorityQueue，它表示優先順序隊列，內部是用堆實現的，堆除了用於實現優先順序隊列，還可以高效方便的解決很多其他問題，比如求前K個最大的元素、求中值等。

Map介面表示鍵值對集合，經常根據鍵進行操作，它有兩個主要的實現類，HashMap和TreeMap。HashMap基於哈希表實現，要求鍵重寫hashCode方法，操作效率很高，但元素沒有順序。TreeMap基於排序二叉樹實現，要求鍵實現Comparable介面，或提供一個Comparator對象，操作效率稍低，但可以按鍵有序。

HashMap還有一個子類LinkedHashMap，它可以按插入或訪問有序。之所以能有序，是因為每個元素還加入到了一個雙向鏈表中。如果鍵本來就是有序的，使用LinkedHashMap而非TreeMap可以提高效率。按訪問有序的特點可以方便的用於實現LRU緩存。

如果鍵為枚舉類型，可以使用專門的實現類EnumMap，它使用效率更高的數組實現。

需要說明的是，我們介紹的各種容器類都不是線程安全的，也就是說，如果多個線程同時讀寫同一個容器對象，是不安全的。如果需要線程安全，可以使用Collections提供的synchronizedXXX方法對容器對象進行同步，或者使用線程安全的專門容器類。

此外，容器類提供的迭代器都有一個特點，都會在迭代中間進行結構性變化檢測，如果容器發生了結構性變化，就會拋出ConcurrentModificationException，所以不能在迭代中間直接調用容器類提供的add/remove方法，如需添加和刪除，應調用迭代器的相關方法。

在解決一個特定問題時，經常需要綜合使用多種容器類。比如要統計一本書中出現次數最多的前10個單詞，可以先使用HashMap統計每個單詞出現的次數，再使用47節介紹的TopK類用PriorityQueue求前十個10單詞，或者使用Collections提供的sort方法。

在之前各節介紹的例子中，為簡單起見，容器中的元素類型往往是簡單的，但需要說明的是，它們也可以是複雜的自定義類型，也可以是容器類型。比如在一個新聞應用中，表示當天的前十大新聞可以用一個List表示，形如List<News>，而為了表示每個分類的前十大新聞，可以用一個Map表示，鍵為分類Category，值為List<News>，形如Map<Category, List<News>>，而表示每天的每個分類的前十大新聞，可以在Map中使用Map，鍵為日期，值也是一個Map，形如Map<Date, Map<Category, List<News>>。

數據結構和演算法

在容器類中，我們看到瞭如下數據結構的應用：

動態數組：ArrayList內部就是動態數組，HashMap內部的鏈表數組也是動態擴展的，ArrayDeque和PriorityQueue內部也都是動態擴展的數組。
鏈表：LinkedList是用雙向鏈表實現的，HashMap中映射到同一個鏈表數組的鍵值對是通過單向鏈錶鏈接起來的，LinkedHashMap中每個元素還加入到了一個雙向鏈表中以維護插入或訪問順序。
哈希表：HashMap是用哈希表實現的，HashSet, LinkedHashSet和LinkedHashMap基於HashMap，內部當然也是哈希表。
排序二叉樹：TreeMap是用紅黑樹(基於排序二叉樹)實現的，TreeSet內部使用TreeMap，當然也是紅黑樹，紅黑樹能保持元素的順序且綜合性能很高。
堆：PriorityQueue是用堆實現的，堆邏輯上是樹，物理上是動態數組，堆可以高效地解決一些其他數據結構難以解決的問題。
迴圈數組：ArrayDeque是用迴圈數組實現的，通過對頭尾變數的維護，實現了高效的隊列操作。
位向量：EnumSet是用位向量實現的，對於只有兩種狀態，且需要進行集合運算的數據，使用位向量進行表示、位運算進行處理，精簡且高效。

每種數據結構中往往包含一定的演算法策略，這種策略往往是一種折中，比如：

動態擴展演算法：動態數組的擴展策略，一般是指數級擴展的，是在兩方面進行平衡，一方面是希望減少記憶體消耗，另一方面希望減少記憶體分配、移動和拷貝的開銷。
哈希演算法：哈希表中鍵映射到鏈表數組索引的演算法，演算法要快，同時要儘量隨機和均勻。
排序二叉樹的平衡演算法：排序二叉樹的平衡非常重要，紅黑樹是一種平衡演算法，AVL樹是另一種，平衡演算法一方面要保證儘量平衡，另一方面要儘量減少綜合開銷。

Collections實現了一些通用演算法，比如二分查找、排序、翻轉列表順序、隨機化重排、迴圈移位等，在實現大部分演算法時，Collections也都根據容器大小和是否實現了RandomAccess介面採用了不同的實現方式。

設計思維和模式

在容器類中，我們也看到了Java的多種語言機制和設計思維的運用：

封裝：封裝就是提供簡單介面，並隱藏實現細節，這是程式設計的最重要思維。在容器類中，很多類、方法和變數都是私有的，比如迭代器方法，基本都是通過私有內部類或匿名內部類實現的。
繼承和多態：繼承可以復用代碼，便於按父類統一處理，但我們也說過，繼承是一把雙刃劍。在容器類中，Collection是父介面，List/Set/Queue繼承自Collection，通過Collection介面可以統一處理多種類型的集合對象。容器類定義了很多抽象容器類，具體類通過繼承它們以復用代碼，每個抽象容器類都有詳細的文檔說明，描述其實現機制，以及子類應該如何重寫方法。容器類的設計展示了介面繼承、類繼承、以及抽象類的恰當應用。
組合：一般而言，組合應該優先於繼承，我們看到HashSet通過組合的方式使用HashMap，TreeSet通過組合使用TreeMap，適配器和裝飾器模式也都是通過組合實現的。
介面：面向介面編程是一種重要的思維，可降低代碼間的耦合，提高代碼復用程度，在容器類方法中，接受的參數和返回值往往都是介面，Collections提供的通用演算法，操作的也都是介面對象，我們平時在使用容器類時，一般也只在創建對象時使用具體類，而其他地方都使用介面。
設計模式：我們在容器類中看到了迭代器、工廠方法、適配器、裝飾器等多種設計模式的應用。