Scala Map implementation keeping entries in insertion order?

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 th开发者_JS百科e 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?

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

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

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.

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

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

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.