Scala immutable Map vs List of tuples

Question

What's the difference between an immutable Map and a List of tuples in Scala? When should I use each of them? Which one is preferable if both are possible?

Answer 1

The two data structures are quite different.

1.Map look up time is O(1). In a list it would be O(n)

Therefore, if you need to look up elements in you key -> value mapping use map.

scala> val myMap = Map("a" -> 1, "b" -> 2, "c" -> 3)
myMap: scala.collection.immutable.Map[String,Int] = Map(a -> 1, b -> 2, c -> 3)

scala> myMap.get("a")
res7: Option[Int] = Some(1)

scala> myMap.getOrElse("a", 0)
res8: Int = 1

scala> myMap("a")
res9: Int = 1

As others have pointed out: Two other major differences are:

2.Keys in Map must be unique

scala> val myList = List(("a", 1), ("b", 2), ("a", 3))
myList: List[(String, Int)] = List((a,1), (b,2), (a,3))

scala> myList.toMap
res0: scala.collection.immutable.Map[String,Int] = Map(a -> 3, b -> 2)

3.Map is un-ordered

scala> Map("a" -> 1, "b" -> 2, "c" -> 3, "d" -> 4, "e" -> 5).toList
res2: List[(String, Int)] = List((e,5), (a,1), (b,2), (c,3), (d,4))

Answer 2

I wouldn't agree (with @Akavall) that the two data structures are quite different. They both represent a sequence (or List in this case) of key-value pairs. In that sense they are entirely homologous. They do have different behaviors, such as the lookup performance that @Akavall mentions. However, that performance is only true for a Map that is implemented as a HashMap (or something similar). That aspect of behavior is not defined by Map itself. There is one other difference with Maps, however. It is customary for the key values in a Map to be distinct (see the definition in Associative Array).

I would suggest that each has its uses. Map[K,V] is best if you are reasonably sure that the keys will be unique and want fast lookup times. Seq[(K,V)] is best where you have no requirement to do fast lookups (or perhaps you know that you might want to do the lookup in either direction, i.e. from K->V or from V->K) or when you expect that keys might be duplicated. Frequently in Scala, a Map is constructed from a sequence of tuples.