ImmutableMultimap builders do not specify ordering guarantees

[gabbard]

Neither ImmutableListMultimap.Builder nor ImmutableSetMultimap.Builder explicitly specify what the iteration order of the resulting Multimap is if orderKeysBy or orderValuesBy is not specified. Neither build nor put nor the class-level Javadoc on the builder itself says anything about ordering; ImmutableListMultimap also mentions no guarantees. ListMultimap does guarantee it “maintains the insertion ordering of values for a given key” but says nothing about the ordering of the keys themselves.

It is possible that these classes intentionally don’t give ordering guarantees, but it seems like it might be an accidental omission in the documentation because some sort on the ordering seems implicit in putAll(Multimap):

The generated multimap's key and value orderings correspond to the iteration ordering of the `multimap.asMap()` view, with new keys and values following any existing keys and values.

and also ImmutableMultimap.copyOf:

Returns an immutable multimap containing the same mappings as multimap. The generated multimap's key and value orderings correspond to the iteration ordering of the `multimap.asMap()` view.

And even if there is no intention to guarantee anything, saying so explicitly would be nice.

(use case: for an internal utility library, I am writing Kotlin extension functions to have versions of associateBy for multimaps and am trying to determine how much to guarantee in the documentation)

[amsukdu]

Hello sir,
I checked the code and seems ImmutableListMultimap and ImmutableSetMultimap mapping is built upon LinkedHashMap.

This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order)

It will use this ordering unless you specify orderKeysBy.
And FYI, value is an ArrayList so it will be also an insertion-order.

I can document this on a Javadoc but don't know the perfect place to put it. Can you suggest me where to put it?

[gabbard]

@amsukdu : I think you are correct what the current implementation is. This issue is a little bit different, though - the question is whether the Guava developers wish this behavior to be guaranteed as part of the public API (in which case it would be good to clearly document it) or not (in which case the behavior could change in the future).

[aepshteyn]

The ImmutableCollection javadoc specifies (for all immutable collections) the iteration order to be insertion order at creation time, "unless an explicit ordering is otherwise specified":

guava/guava/src/com/google/common/collect/ImmutableCollection.java

Lines 60 to 64 in 99a4d3a

	* <li><b>Deterministic iteration.</b> The iteration order is always well-defined, depending on
	* how the collection was created. Typically this is insertion order unless an explicit
	* ordering is otherwise specified (e.g. {@link ImmutableSortedSet#naturalOrder}). See the
	* appropriate factory method for details. View collections such as {@link
	* ImmutableMultiset#elementSet} iterate in the same order as the parent, except as noted.

It would make sense for the ImmutableMultimap builders to also describe this behavior in their own javadocs, because it's not easy to find otherwise.