Consider LinkedHashMap in ArrayListMultimap

[bjmi]

Almost every time a ListMultimap is suitable I can't use the existing ArrayListMultimap implementation as the insertion order of the keys is not preserved. Then I have to switch to Multimaps.newListMultimap(new LinkedHashMap<>(), ArrayList::new) or MultimapBuilder.linkedHashKeys().arrayListValues().build() that are implemented by CustomListMultimap.

• Is there a compelling reason why ArrayListMultimap is backed by HashMap and not LinkedHashMap?
• Are there any benefits to use the ArrayListMultimap backed by a LinkedHashMap compared to a CustomListMultimap backed by LinkedHashMap and ArrayList? I can't find a rule when to use the MultimapBuilder or the existing implemenations when they have the same criteria for keys and values from the Wiki.

The risks to switch to LinkedHashMap is negligible but gain traceable data (e.g. debugging) and better iteration performance on keys.

Some prominent examples that use LinkedHashMap as their default Map implementation are:

• Kotlin: https://github.com/JetBrains/kotlin/blob/v1.8.10/libraries/stdlib/src/kotlin/collections/Maps.kt#L74
• Groovy: https://docs.groovy-lang.org/docs/groovy-latest/html/documentation/#_maps
• Spring: https://docs.spring.io/spring-framework/docs/current/javadoc-api/org/springframework/beans/factory/config/MapFactoryBean.html#setTargetMapClass(java.lang.Class)

[cpovirk]

Thanks, it's been a while since I thought about this.

We actually did some migrations inside Google from ArrayListMultimap and friends to MultimapBuilder. We should probably recommend that in the docs. I don't think there are any downsides unless you use trimToSize() (which you probably don't). (In a similar case, TreeMultimap, there is the slight potential downside that the MultimapBuilder approach results in a keySet() that isn't a NavigableSet (or maybe it is a NavigableSet but that's not guaranteed by the static types? I forget).)

It's also worth considering making ArrayListMultimap guarantee ordering by using LinkedHashMap. We've tried to guarantee ordering in some of our other hash-based collections (though in Google we have somewhat reduced the danger of changing ordering by randomizing the order of most of our plain HashMap instances during testing). And of course anyone who really doesn't want the overhead of LinkedHashMap could still use MultimapBuilder. It's especially sad and surprising that LinkedListMultimap guarantees ordering throughout but ArrayListMultimap does not....

[bjmi]

Thanks for providing these insights. Based on this, we will switch our code to the MultimapBuilder for now.