Map

A Map provides a mapping from a key to the associated value. Lookups into a Map based on a key have a generally constant time of O(1). A Map is an important data structure that has many applications in the real world.

Let's look at some simple Map usage using Scala REPL:

scala> val countryToCurrency = Map(("US" -> "USD"), ("DE" -> "EUR"), ("FR" -> "EUR"), ("IN" -> "INR")) // Mapping from country code to currency code
countryToCurrency: scala.collection.immutable.Map[String,String] = Map(US -> USD, DE -> EUR, FR -> EUR, IN -> INR)

scala> countryToCurrency.keys // country codes
res4: Iterable[String] = Set(US, DE, FR, IN)

scala> countryToCurrency.values // currency codes
res5: Iterable[String] = MapLike.DefaultValuesIterable(USD, EUR, EUR, INR)

scala> countryToCurrency("US") // lookup currency code for US
res6: String = USD

In Scala, there are many different types of map, each with its own set of characteristics. We will cover the following three:

 

The following are some general considerations to bear in mind regarding the performance of each of these Map types:

• HashMap is the best choice in most cases, particularly for lookup-centric use cases. HashMap does not preserve key insertion order or sort keys.
• TreeMap is suitable for use cases where keys need to be sorted.
• LinkedHashMap is most suited when the key insertion order needs to be preserved.

Let's explore some of these map types in Scala REPL using the following code:

1. Import HashMap, TreeMap, and LinkedHashMap from Scala's collection.mutable package. Each represents Map type but with a slightly different flavor:

scala> import collection.mutable.{HashMap,TreeMap,LinkedHashMap}
import collection.mutable.{HashMap, TreeMap, LinkedHashMap}

1. Create a HashMap that maps a number to its English word equivalent. Notice that the order of keys is not preserved. The number 8 was at position 8 in our constructor however in the object created it is at the first position:

scala> val numHashMap = HashMap((1->"one"), (2->"two"), (3->"three"), (4->"four"), (5->"five"), (6->"six"), (7->"seven"), (8->"eight"), (9->"nine")) // keys can be in any order
numHashMap: scala.collection.mutable.HashMap[Int,String] = Map(8 -> eight, 2 -> two, 5 -> five, 4 -> four, 7 -> seven, 1 -> one, 9 -> nine, 3 -> three, 6 -> six)

1. Add a new entry of 0. This got added at the very end however this is just a coincidence, it could have been anywhere:

// add new mapping, keys can be any order
scala> numHashMap += (0->"zero") 
res5: numHashMap.type = Map(8 -> eight, 2 -> two, 5 -> five, 4 -> four, 7 -> seven, 1 -> one, 9 -> nine, 3 -> three, 6 -> six, 0 -> zero)

1. Create a TreeMap similar to HashMap. Note that the order of keys is preserved. In fact, this is due to keys automatically being sorted by TreeMap. Our object construction had provided the keys in ascending order:

// keys must be sorted
scala> val numTreeMap = TreeMap((1->"one"), (2->"two"), (3->"three"), (4->"four"), (5->"five"), (6->"six"), (7->"seven"), (8->"eight"), (9->"nine")) 
numTreeMap: scala.collection.mutable.TreeMap[Int,String] = TreeMap(1 -> one, 2 -> two, 3 -> three, 4 -> four, 5 -> five, 6 -> six, 7 -> seven, 8 -> eight, 9 -> nine)

1. Add a new entry to TreeMap with key as 0. This gets added to the beginning because of key sorting in a TreeMap:

// add a new mapping, keys must get sorted
scala> numTreeMap += (0->"zero") 
res6: numTreeMap.type = TreeMap(0 -> zero, 1 -> one, 2 -> two, 3 -> three, 4 -> four, 5 -> five, 6 -> six, 7 -> seven, 8 -> eight, 9 -> nine)

1. Create a LinkedHashMap similar to HashMap and TreeMap. Note that keys appear exactly as it was specified in the constructor:

// order must be preserved
scala> val numLinkedHMap = LinkedHashMap((1->"one"), (2->"two"), (3->"three"), (4->"four"), (5->"five"), (6->"six"), (7->"seven"), (8->"eight"), (9->"nine")) 
numLinkedHMap: scala.collection.mutable.LinkedHashMap[Int,String] = Map(1 -> one, 2 -> two, 3 -> three, 4 -> four, 5 -> five, 6 -> six, 7 -> seven, 8 -> eight, 9 -> nine)

1. Add new entry to LinkedHashMap with key as 0. This gets added at the very end because LinkedHashMap preserves the order of key insertion:

// this must be the last element
scala> numLinkedHMap += (0->"zero") 
res17: numLinkedHMap.type = Map(1 -> one, 2 -> two, 3 -> three, 4 -> four, 5 -> five, 6 -> six, 7 -> seven, 8 -> eight, 9 -> nine, 0 -> zero)

Scala offers a good number of choices in terms of Map implementation. You can choose the best option based on the usage pattern. Similar to the design choices between arrays and lists, at times there are trade-offs that need to be considered in deciding the best Map implementation.