4.8 HashMap v.s. TreeMap

在工作上, 若需要使用到key-value pair的資料結構, 我們常常第一個想到的就是HashMap, 然而, 若想要擁有排序的功能的話, 就可以考慮下TreeMap了, 但由於底層資料結構特性的關係, TreeMap(based on R-B tree)基本上是比HashMap(based on hash table)要來得慢的.

HashMap

  • 基於hash table來實作

  • 常見操作之時間複雜度為O(1) (get and put)

  • 無法保證key的順序性

  • 放入其中的元素必須確實地實作hashCode()方法

  • 是一種non-thread safe collection

TreeMap

  • 基於R-B tree(紅黑樹)來實作

  • 常見操作之時間複雜度為O(logn) (containsKey, get, put and remove)

  • 可以保證key的順序性, 若沒有在建構期間指定comparator, 會使用natural ordering(自行判斷Key的型別並且用ASC排序, 前提是Key的型別必須實作Comparable, 若沒有實作, 在runtime期間會拋出java.lang.ClassCastException)或是自訂的comparator

  • 是一種non-thread safe collection

重點

  • 一般如果不考慮排序的話, 就直接用HashMap吧

  • 若想要排序HashMap的內容, 可以在HashMap集合蒐集完資料後, 將其轉換成TreeMap, 可用TreeMap的putAll()或是constructor方法進行轉換:

    // putAll():
Map<K, V> treeMap = new TreeMap<>();
treeMap.putAll(hashMap);

// constructor:
Map<K, V> treeMap = new TreeMap<>(hashMap);

範例

以下測試程式簡單地示範了這幾個特性:

  • HashMap與TreeMap的put是會更新舊值且回傳舊值的, 同時value允許為null

  • TreeMap會根據natural ordering/自訂義的comparator進行排序

  • 將HashMap轉換成TreeMap後, 也會遵照natural ordering

範例程式點我

參考資料

Previous4.7 HashSet v.s. TreeSetNext4.9 ArrayList v.s. Vector

Last updated

Was this helpful?