How to choose a Map implementation in Scala (Map, ListMap, LinkedHashMap, SortedMap, TreeMap)

By Alvin Alexander. Last updated: August 2, 2022

This is an excerpt from the 1st Edition of the Scala Cookbook (partially modified for the internet). This is Recipe 11.14, “How to Choose a Map Implementation in Scala”

Problem

You need to choose a Scala Map class for a particular problem.

Solution

Scala has a wealth of map types to choose from, and you can even use Java map classes. If you’re looking for a basic map class, where sorting or insertion order doesn’t matter, you can either choose the default, immutable Map, or import the mutable Map, as shown in the previous recipe.

Sort the map by keys

If you want a map that returns its elements in sorted order by keys, use a SortedMap:

scala> import scala.collection.SortedMap
import scala.collection.SortedMap

scala> val grades = SortedMap("Kim" -> 90,
     | "Al" -> 85,
     | "Melissa" -> 95,
     | "Emily" -> 91,
     | "Hannah" -> 92
     | )
grades: scala.collection.SortedMap[String,Int] = Map(
  Al -> 85, 
  Emily -> 91, 
  Hannah -> 92, 
  Kim -> 90, 
  Melissa -> 95
)

Sort the map by values

If you want a map that remembers the insertion order of its values, use a LinkedHashMap or ListMap. Scala only has a mutable LinkedHashMap, and it returns its elements in the order you inserted them:

scala> import scala.collection.mutable.LinkedHashMap
import scala.collection.mutable.LinkedHashMap

scala> var states = LinkedHashMap("IL" -> "Illinois")
states: scala.collection.mutable.LinkedHashMap[String,String] = 
        Map(IL -> Illinois)

scala> states += ("KY" -> "Kentucky")
res0: scala.collection.mutable.LinkedHashMap[String,String] = 
      Map(IL -> Illinois, KY -> Kentucky)

scala> states += ("TX" -> "Texas")
res1: scala.collection.mutable.LinkedHashMap[String,String] = 
      Map(IL -> Illinois, KY -> Kentucky, TX -> Texas)

Scala has both mutable and immutable ListMap classes. They return elements in the opposite order in which you inserted them, as though each insert was at the head of the map (like a List):

scala> import scala.collection.mutable.ListMap
import scala.collection.mutable.ListMap

scala> var states = ListMap("IL" -> "Illinois")
states: scala.collection.mutable.ListMap[String,String] = 
        Map(IL -> Illinois)

scala> states += ("KY" -> "Kentucky")
res0: scala.collection.mutable.ListMap[String,String] = 
      Map(KY -> Kentucky, IL -> Illinois)

scala> states += ("TX" -> "Texas")
res1: scala.collection.mutable.ListMap[String,String] = 
      Map(TX -> Texas, KY -> Kentucky, IL -> Illinois)

The LinkedHashMap implements a mutable map using a hashtable, whereas a ListMap is backed by a list-based data structure. (Personally, I don’t use the List class very often, so I prefer the LinkedHashMap.)

Discussion

Table 11-1 shows a summary of the basic Scala map classes and traits, and provides a brief description of each.

Table 11-1. Basic map classes and traits

Class or trait	Description
collection.immutable.Map	This is the default, general-purpose immutable map you get if you don’t import anything.
collection.mutable.Map	A mutable version of the basic map.
collection.mutable.LinkedHashMap	All methods that traverse the elements will visit the elements in their insertion order.
collection.immutable.ListMap collection.mutable.ListMap	Per the Scaladoc, “implements immutable maps using a list-based data structure.” As shown in the examples, elements that are added are prepended to the head of the list.
collection.SortedMap	Keys of the map are returned in sorted order. Therefore, all traversal methods (such as foreach) return keys in that order.

Although those are the most commonly used maps, Scala offers even more map types. They are summarized in Table 11-2.

Table 11-2. More map classes and traits

Class or trait	Description
collection.immutable.HashMap	From the Scaladoc, “implements immutable maps using a hash trie.”
collection.mutable.ObservableMap	From the Scaladoc: “This class is typically used as a mixin. It adds a subscription mechanism to the Map class into which this abstract class is mixed in.”
collection.mutable.MultiMap	From the Scaladoc: “A trait for mutable maps with multiple values assigned to a key.”
collection.mutable.SynchronizedMap	From the Scaladoc: This trait “should be used as a mixin. It synchronizes the map functions of the class into which it is mixed in.”
collection.immutable.TreeMap	From the Scaladoc: “implements immutable maps using a tree.”
collection.mutable.WeakHashMap	A wrapper around java.util.WeakHashMap, “a map entry is removed if the key is no longer strongly referenced.”

But wait, there’s still more. Beyond these types, Scala also offers several more map types that have parallel/concurrent implementations built into them: