CODEWITHSUNDEEP
scala
Kevin Meredith
Kevin Meredith

Reputation: 41909

When to Use Scala TreeMap?

Given the following example of TreeMap:

scala> import scala.collection.immutable.TreeMap
import scala.collection.immutable.TreeMap

scala> val tm = TreeMap( ("foo" -> List(2,1) ) )
tm: scala.collection.immutable.TreeMap[String,List[Int]] = Map(foo -> List(2, 1))

scala> tm + ("bar" -> List(300, 4) )
res0: scala.collection.immutable.TreeMap[String,List[Int]] = Map(bar -> List(300, 4), foo -> List(2, 1))

scala> res0 + ("bippy" -> List(4) )
res1: scala.collection.immutable.TreeMap[String,List[Int]] = Map(bar -> List(300, 4), bippy -> List(4), foo -> List(2, 1))

It's not clear to me as to when it's advantageous to use a TreeMap over a Map. When is it?

Upvotes: 3

Views: 6776

Answers (1)

mohit
mohit

Reputation: 4999

TreeMap guarantees that the entries that are in the map are in a sorted order using keys, where as Map does not make any such guarantee.

So, if you want an ordering of keys in a map use TreeMap otherwise a normal Map will suffice. A place where I use TreeMap is generating tokens for Twitter's API . To create a token, it is required that a string be created using url params which are sorted lexigraphically. I get the url params in a map,then put it in a TreeMap to get it sorted.

Going a little deep -

Scala uses Hash Tries to create a HashMap(which is the default implementation of a Map) where the data structure is a Trie and the keys are hashed. Also, Scala optimizes the HashMap when the size is less than 5(source). It provides a constant look up and insertion cost in normal cases.

On the other hand, TreeMaps are constructed using Red Black trees. Red Black tree has a look up and insertion cost of O(ln n).

So, use Map when you don't want the keys to be sorted for better performance.

More details are in the collection docs

Upvotes: 13

Related Questions