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?

Solution 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."

Solution 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.

Solution 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.

Solution 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

Solution 5

• 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)

View more solutions

Comments

[Andrew Norman]

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/…

[Andrew Norman]

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

[Nandakishore]

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

[Michelle]

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

[Michelle]

There are both immutable ListMap and mutable ListMap.

[Andrew Norman]

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

[Andrew Norman]

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

[Andrew Norman]

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

[Murat Mustafin]

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

[akauppi]

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