CODEWITHSUNDEEP
scala
Emma Liu
Emma Liu

Reputation: 33

Why element order is not preserved when converting a list of pairs to Map in Scala?

Example: 

val occ = List(('l', 2), ('n', 1), ('r', 1), ('u', 2), ('x', 1))
occ.toMap
// Map(x -> 1, n -> 1, u -> 2, l -> 2, r -> 1)

The elements are no longer sorted in alphabetical order. Why does this happen?

Upvotes: 2

Views: 1856

Answers (3)

som-snytt
som-snytt

Reputation: 39577

Edit: there's a LinkedMap coming in 2.13 with different trade-offs.

Edit: the question is really that you might expect list.toMap to produce a ListMap. Why doesn't it?

The doc says "inserting or removing entries, are also O(n), which makes this collection suitable only for a small number of elements."

So that's another sensitivity to size. Often you create a collection as pairs resulting from other operations and you just want to dump them into a map, often a large one.

--

There is sensitivity to size due to specialization. There are custom maps for the smallest sizes. This isn't guaranteed, but is confusing if you notice the pattern.

scala $ ~/scala-2.12.6/bin/scala -Dscala.repl.info
Welcome to Scala 2.12.6 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_144).
Type in expressions for evaluation. Or try :help.
[info] started at Wed Jun 20 00:17:33 PDT 2018

scala 2.12.6> val m = List(1->10,2->20,3->30,4->40).toMap
m: scala.collection.immutable.Map[Int,Int] = Map(1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40)

scala 2.12.6> val m = List(1->10,2->20,3->30,4->40,5->50).toMap
m: scala.collection.immutable.Map[Int,Int] = Map(5 -> 50, 1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40)

scala 2.12.6> :quit
scala $ ~/scala-2.13.0-M4/bin/scala -Dscala.repl.info
[info] started at Wed Jun 20 00:18:41 PDT 2018
Welcome to Scala 2.13.0-M4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_144).
Type in expressions for evaluation. Or try :help.

scala 2.13.0-M4> val m = List(1->10,2->20,3->30,4->40).toMap
m: scala.collection.immutable.Map[Int,Int] = ChampHashMap(1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40)

scala 2.13.0-M4> val m = List(1->10,2->20,3->30,4->40,5->50).toMap
m: scala.collection.immutable.Map[Int,Int] = ChampHashMap(5 -> 50, 1 -> 10, 2 -> 20, 3 -> 30, 4 -> 40)

Upvotes: 2

Svitovyda
Svitovyda

Reputation: 26

You can use ListMap instead of Map, it keeps items in the order they were inserted. To convert List to ListMap:

val occ = List(('l', 2), ('n', 1), ('r', 1), ('u', 2), ('x', 1))
ListMap(occ: _*)

In case you don't know what _* means - repeated parameters

Upvotes: 1

Tim
Tim

Reputation: 27356

Maps are not sorted and the keys may be in any order depending on implementation.

However a ListMap preserves the order of addition. You can build a ListMap using the normal Map operations, or you can create one from a List like this:

ListMap(occ:_*)

Upvotes: 5

Related Questions