iThome 網站首載：善用程式庫中的資料結構特性
許多程式庫都提供了資料結構高效實作，然而即便現代開發者不需全盤瞭解資料結構實作細節，但仍需瞭解基本資料結構實作與特性，以在正確場合選用具正確實作，避免時間或空間上的效能問題，或者有能力選用正確的第三方程式庫，避免自行以繁瑣程式實作所需功能。
- 認識Java標準資料結構實作
在我上一篇專欄中，談到了數列（List）、集合（Set）以及對應（Map）三種基本資料型態，實際上這三者是從有序、不重複與鍵值結構的高階特性來大致分類，具體實作方式仍各有差異。以Java中的數列實作來說，實作List介面的類別最基本的就有ArrayList與LinkedList；集合實作方面，實作Set介面的基本上就有HashSet與TreeSet；鍵值對應結構的實作，基本上則有實作Map介面的HashMap與TreeMap。
ArrayList正如其名稱所示，內部實作使用陣列來保存收集之物件，陣列在記憶體中會是連續空間，根據索引隨機存取時速度快，若操作上有這類需求時，像是排序，使用ArrayList可得到較好的速度表現；然而若操作時會引發索引順序調整時，會有較差的表現，特別是移除索引0的元素。陣列長度固定也是要考量的問題，在ArrayList內部陣列長度不夠時，會建立新陣列並複製舊陣列元素參考，如果大致知道物件數量，事先建立足夠長度的內部陣列，可以節省上述成本。相對地，LinkedList內部採用了鏈結（Link）結構，鏈結的每個元素會參考下一個元素，這有利於在數列前端調整元素；然而想要指定索引隨機存取物件時，鏈結方式基本上是從第一個元素開始查找下一個元素的方式，會比較沒有效率，因此像數列排序就不適合使用LinkedList作為實作。
在Set與Map的基本實作方面，以雜湊（Hash）為實作基礎有HashSet與HashMap。雜湊的基本特性就是用記憶體空間換取存取時間，新增物件時，直接根據物件或鍵的雜湊值將之分配至適當位置，因此新增物件時的速度表現較佳，然而物件數量多時必須耗費更多的雜湊空間（Heap space），若有必要迭代整個HashSet或HashMap，效能上的表現也較為不佳。以樹狀結構為實作基礎的TreeSet與TreeMap，雖然在新增或刪除時，必須耗費少量成本來維持樹的節點順序與平衡，然而已排序的結構在進行元素查找時可以有較好的效能。
- 常用操作的效能考量
可以從各種資料型態的內部實作中看出，主要必須瞭解的是它們各自是以陣列、鏈結、雜湊或樹狀哪種結構來實作，才能依需求選用對應特性的實作類型。以單純地新增元素來說，ArrayList、LinkedList、HashSet的add(o)基本上是O(1)，而TreeSet會是O(log n)；使用contains(o)查找元素或remove(o)刪除元素時，線性結構的ArrayList、LinkedList會是O(n)，基於雜湊值來查找的HashSet會是O(1)，而TreeSet會是O(log n)；在使用Iterator的next逐一迭代元素時，ArrayList、LinkedList會是O(1)，HashSet會是與雜湊空間及元素個數相關的O(h/n)，而TreeSet仍是O(log n)。
在基於索引的操作方面，由於數列本身是線性結構，因此對於指定索引位置的add(i, o)與remove(i)等操作來說，ArrayList必須調整索引順序，而LinkedList必須走訪元素以確認索引，因此都是O(n)；indexOf(o)必須逐一比對元素，所以也都會是O(n)，在指定索引以取得元素的get(i)操作上，ArrayList會是O(1)，而LinkedList會是O(n)。
基於以上資料結構的實作特性，也可以推斷出相關類型的變化實作與操作可能耗費的成本。例如Queue或Deque亦有陣列或鏈結相關實作，而LinkedHashSet本身實作了Set介面，內部使用雜湊與鏈結實作，鏈結主要是用來維護迭代順序，使迭代時的元素順序為新增元素時的順序，因此add(o)、contains(o)與remove(o)與HashSet的對應操作同為O(1)，然而使用Iterator的next逐一迭代元素時會是O(1)。
如果要管理一組元素，多數開發者會直覺使用List，然而若該組元素是無序的，且沒有迭代整組元素的需求，應該使用HashSet而不是List相關實作，因為在add(o)、contains(o)、remove(o)都會有很好的表現，然而耗用的記憶體較多。如果元素具有自然順序（Natural order），則可以使用TreeSet。如果元素是有索引順序的，那麼可使用ArrayList或LinkedList，若元素索引不常變動，且經常要隨機指定索引取得元素，那麼使用ArrayList；如果經常要從前端移除元素，那就使用LinkedList。
- 從基本資料結構延伸而出的型態
有些問題，雖然僅使用List、Set以及Map等基本資料型態與相關實作也可以解決，但會撰寫出不易閱讀的複雜邏輯。舉例來說，如果想要統計學生考試分數中，每個得分各有幾人，雖然基本上可以如下使用Map來實現：
Map<Integer, Integer> juni = new HashMap<>();
for(Integer score : scores) {
juni.put(score, juni.get(score) == null ? 1 : juni.get(score) + 1);
}
Integer count = juni.get(93);
for(Integer score : scores) {
juni.put(score, juni.get(score) == null ? 1 : juni.get(score) + 1);
}
Integer count = juni.get(93);
然而這個需求實際上需要的容器，像是個可以分類的袋子（Bag），重複的元素可以丟在相同分類中，最後可詢問每個分類中有幾個元素。guava-libraries對此一型態的實現為Multiset（名稱上容易被人誤會，實際上Multiset不是Set，它是Collection的子介面），例如相同需求使用HashMultiset實作，可以如下簡潔地撰寫：
Multiset<Integer> scoresMultiset = HashMultiset.create();
scoresMultiset.addAll(scores);
Integer count = scoresMultiset.count(93);
scoresMultiset.addAll(scores);
Integer count = scoresMultiset.count(93);
經常地，對於Map中的一個鍵會想要有多個對應的值。例如想統計全國各年度多個地區的最高溫，會想要有{1949=[111, 78, ...], 1950=[22, 30, ...], ...}這種以年份為鍵，而一組各地區最高溫為值的結構。基本上，可以使用Map<Integer, Set<Integer>>或Map<Integer, List<Integer>>，來組合出具有{k1=[v1, v2, v3], k2=[v4, v5, v6],....}的對應關係。guava-libraries對此一型態的實現為Multimap（實際上Multimap也不是Map，它沒有繼承自任何介面），例如可以用Multimap<Integer, Integer> yearToTempers = HashMultimap.create()建立Multimap的實作物件，其put(k, v)方法可以將相同鍵的多個物件管理在一個Collection中，get(k)方法可以取得鍵對應的Colleciton物件。
像Map這種鍵值對應的結構，也常被稱為關聯陣列（Associative array），若把純綷陣列的數字索引當作是鍵，儲存的元素當作值，就可以理解關聯陣列這個名稱的由來。Map基本上是單向關聯，由鍵對應至值，然而有時會想要從值對應至鍵，也就是想要類似一對一雙向關聯的操作。解決方法之一，是透過Map的entrySet方法取回一組Map.Entry<K, V>，在迭代過程中藉由Map.Entry<K, V>的getValue判斷是否為指定的值，若是則使用getKey取得對應的鍵。guava-libraries對此一型態的實現為BiMap（為Map的子介面），其實作物件的inverse方法可以對調鍵與值，例如若原BiMap的鍵為學生而值為宿舍，inverse傳回的BiMap實作物件，就會以宿舍作為鍵，而學生作為值的部份。
- 不重複打造輪子不代表可忽略理論基礎
不少發源於學術界的基礎或高深理論，可能都有相關程式庫加以實作了，現代開發者也許真的沒什麼機會對相關理論進行實作，基本上非必要也不建議重新打造輪子，畢竟許多程式庫都經過一定數量的使用者驗證與改進，自行實作未必能加以超越，然而這並不代表程式設計最後只能是個組裝過程。忽略理論基礎中的特性，容易選用不正確的資料結構，或者採用了不正確的預設值。實務開發若能以理論為基礎，非但可以改進程式運行的時間與空間等效能議題，在必要的時候，也會有能力選用正確的輪子，或者進一步自行封裝程式以改進可讀性，提高程式開發效率。