What map does scala choose to use?

Question

Hi so I know Scala comes with multiple types of maps including HashMap, TreeMap (which I believe is a Trie), BitMap, and ListMap.

So when you create a Map in scala using you basic factor of Map(1 -> 2, 2 -> 3), which implementation does Scala choose to use? I'm guessing the scala has some set of rules for choosing out of the types of maps listed above, but what are those rules? Obviously to use a hash, there needs to be some sort of hashing strategy defined somewhere. Or does scala just default to one of the implementations?

Thanks

Answer 1

According to the documentation on HashTries (scroll to section of HahsTries) the default implementation used by Scala is HashMap.

Scala, however returns the so called specialised representations of HashMap implementation in some cases like Maps that contains up to (and including 4 elements, this is also in the documentation link)

You can verify this by doing:

  val map: Map[Int, Int] = Map(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5)
  val map2: Map[Int, Int] = Map(List(1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6): _*)

  println(map.getClass.getName)
  println(map2.getClass.getName)

And the output is:

scala.collection.immutable.Map$Map4
scala.collection.immutable.HashMap$HashTrieMap

If you use and IDE that can decompile code you see that the way keys are managed in instances of Map1, Map2, Map3 and Map4 is by equality because internally this collections is represented by a sequence (not a Scala Seq) of tuples.

The default HashMap implementation uses the hashes of the keys and the details are in the link I posted.