善用程式庫中的資料結構特性

資料結構是電腦科學重要基礎學科，許多程式庫都提供了資料結構高效實作，然而即便現代開發者不需全盤瞭解資料結構實作細節，但仍需瞭解基本資料結構實作與特性，以在正確場合選用具正確特性的實作，避免時間或空間上的效能問題，或者有能力選用正確的第三方程式庫，避免自行以繁瑣程式實作所需功能。

認識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的juni來實現，像是for(Integer score : scores) { juni.put(score, juni.get(score) == null ? 1 : juni.get(score) + 1); }。最後juni.get(93)就可得知93分的人數。

然而這個需求實際上需要的容器，像是個可以分類的袋子（Bag），將重複元素加以分類，最後可詢問各分類的元素個數。

guava-libraries對此一型態的實現為Multiset（實際上不是Set，它是Collection的子介面），例如相同需求可以Multiset scoresMultiset = HashMultiset.create()建立HashMultiset實作，接著scoresMultiset.addAll(scores)在Multiset中，加入所有分數，然後以scoresMultiset.count(93)，來取得93分的人數。

經常地，對於Map中的一個鍵會想要有多個對應的值。

例如想統計全國各年度多個地區的最高溫，會想要有{1949=[111, 78, ...], 1950=[22, 30, ...], ...}這種以年份為鍵，而一組各地區最高溫為值的結構。基本上，可以使用Map>或Map>，來組合出具有{k1=[v1, v2, v3], k2=[v4, v5, v6],....}的對應關係。guava-libraries對此一型態的實現為Multimap（實際不是Map，它沒有繼承自任何介面），例如可以用Multimap yearToTempers = HashMultimap.create()建立Multimap的實作物件，其put(k, v)方法可以將相同鍵的多個物件管理在一個Collection中，get(k)方法可以取得鍵對應的Colleciton物件。

Map基本上是單向關聯，由鍵對應至值，然而有時會想要從值對應至鍵，也就是想要類似一對一雙向關聯的操作。

解決方法之一，是透過Map的entrySet方法取回一組Map.Entry，在迭代過程中藉由Map.Entry的getValue判斷是否為指定的值，若是則使用getKey取得對應的鍵。guava-libraries對此一型態的實現為BiMap（為Map的子介面），其實作物件的inverse方法可以對調鍵與值，例如若原BiMap的鍵為學生而值為宿舍，inverse傳回的BiMap實作物件，就會以宿舍作為鍵，而學生作為值的部份。

不重複打造輪子不代表可忽略理論基礎
現代開發者也許沒什麼機會對相關理論進行實作，非必要也不建議重新打造輪子，畢竟許多程式庫都經過一定數量的驗證，自行實作未必能加以超越，然而這並不代表程式設計只能是組裝過程。忽略理論基礎中的特性，容易選用不正確資料結構、採用了不正確的預設值。

實務開發若能以理論為基礎，可改進程式運行的時間與空間等效能議題，也會有能力，選用正確輪子，或者自行封裝程式，改進可讀性，提高程式開發效率。