Scala Map implementation keeping entries in insertion order?

Question

In Java, I use LinkedHashMap for this purpose. The documentation of Java's LinkedHashMap is very clear that it has "predictable iteration order" and I need the same in Scala.

Scala has ListMap and LinkedHashMap, but the documentation on what they do exactly is poor.

Question: Is Scala's LinkedHashMap or ListMap the implementation to use for this purpose? If not, what other options are available besides using the Java's LinkedHashMap directly?

Woodrum

just to note, I don't recommend using scala's ListMap classes in general. They have linear time complexity for most operations. So unless your map is tiny, logic that uses listmaps will really drag. docs.scala-lang.org/overviews/collections/… – Reformer

Unfortunately, because ListMap is only immutable, it's also hard to "find" like if you make it part of another nested type even for a val, it needs to be imported explicitly. It's not clear to me why it isn't already in scope like List and Map are. – Stoup

Answer 1

From the LinkedHashMap Scaladoc page:

• "This class implements mutable maps using a hashtable. The iterator and all traversal methods of this class visit elements in the order they were inserted."

Sisterly

Answer 2

The difference between the two is that LinkedHashMap is mutable while ListMap is immutable. Otherwise they both are MapLike and also preserve insertion order.

Bjorn

There are both immutable ListMap and mutable ListMap. – Mariel

other difference is that ListMap has linear complexity in lookup and insertion – Cutlor

Answer 3

For LinkedHashMap, the answer is pretty clear that it preserves the order of insertion.

But for ListMap, it seems that there are some confuses here.

Firstly, there are two ListMap.

• scala.collection.mutable.ListMap
• scala.collection.immutable.ListMap.

Secondly, the document for ListMap has something wrong as far as I tried.

mutable.ListMap

The actual order is not the insertion order as it says.

And it is not the inverse order of insertion, either. The result I tried is [forth, second, first, third]

A simple mutable map backed by a list, so it preserves insertion order.

immutable.ListMap

As the document saying that, the order is the insertion order.

One thing to notice is that it is stored internally in reversed insertion order. And the internally stored order and the iterable/traversal order are two things. The internally stored order decides the time complexity of lookup methods such as head/last/tail/init/.

This class implements immutable maps using a list-based data structure. List map iterators and traversal methods visit key-value pairs in the order whey were first inserted.

Entries are stored internally in reversed insertion order, which means the newest key is at the head of the list.

Mariel

Interesting. Did you report the conflict between real and documented behaviour to authors? github.com/scala/bug Edit: Seems someone did, and it's considered for deprecation in 2.13 github.com/scala/bug/issues/9893 – Wymore

Answer 4

ListMap doesn't preserves the order of insertion.

Only LinkedHashMap maintains the order of elements the way they are inserted.

If you want to maintain order in Lists otherthan Map you can use LinkedList

Olimpia

you're evaluating mutable listmaps but most people use the immutable listmaps which is a completely different implementation – Reformer

Answer 5

Scala 2.13 is introducing two new immutable implementations of Map which keep insertion order: VectorMap and SeqMap. See this PR:

Currently there isn't any known immutable map which also maintains key insertion order while keeping effectively constant lookup time on key, so the only known implementations are done by combining a Vector with a HasMap (or in Scala's case HashMap/ChampHashMap)

As of writing, Scala 2.13 is still scheduled to be released in 2018.

UPDATE 2021-04-14: Scala 3.13 does have VectorMap now. SeqMap is just a "generic trait for ordered immutable maps". Besides the new VectorMap and the older ListMap, there is also a new TreeSeqMap.

Note that mutable.ListMap got deprecated with 2.13, but immutable.ListMap is still current.

Woodrum

Answer 6

• LinkedHashmap is in the order it was added
• (immutable) ListMap is in the backward order it was added (i.e. the last one added is first)

LinkedHashmap is only implemented as a mutable map ListMaps are implemented in both the mutable and immutable packages, however only the immutable ListMaps maintain the backwards ordering. (mutable listmaps do not maintain order)

Reformer

this is a nice article that breaks down the various map implementations in scala alvinalexander.com/scala/… – Reformer

ListMap doesn't even maintain order in backward order as you are saying. It randomly displays from the list. – Olimpia

Actually the document of scala api is wrong. And it is different between immutable.ListMap and mutable.ListMap – Mariel

@Olimpia you are referring to mutable listmaps only. I've updated my answer to differentiate between the 2 types (mutable and immutable). – Reformer

just wanted to note that both ListMaps implementations have slow time complexity for most functions so it reduces their practicality in using with large amounts of data. Unless mutability is an absolute deal killer, you should use LinkedHashmap – Reformer