Repository navigation
ImmutableMap.sortedCopyOf #8552
Description
This comes as a request from an external user. The motivation is to produce a deterministic order while continuing to use hashing for lookups, rather than the O(log N) lookups of ImmutableSortedMap. It is of course already possible to sort before calling ImmutableMap.copyOf, but a method on ImmutableMap might catch users' attention more, prompting them to consider whether sorting is right for them. (As usual, prompting users to consider something can be a small negative in the large majority of cases but a sizable positive in a small number of cases, and that can sometimes be OK. Or maybe users who are concerned enough should soft-ban ImmutableSortedMap and perhaps ImmutableSortedSet, too?) It might also perform better than separate sort+copy operations would, especially if the input is a collection whose stream implementation we have no hope of optimizing. I do see plenty of users of sorted().collect(toImmutableMap(...)), so those are people who either (depending on your perspective) want this or don't need this. [edit: And also as usual, we could worry that users will stress over whether to use sorted().collect(toImmutableMap(...)) or sortedCopyOf in cases where it doesn't matter.]
The new API would be similar to the existing ImmutableList.sortedCopyOf(Iterable), and it could come with the same kind of Comparator-accepting overload. (It's admittedly a little strange that a method named "ImmutableMap.sortedCopyOf" would not return the ImmutableSortedMap class, whereas there is no ImmutableSortedList.)
It also reminds me a bit of how ImmutableMultimap.Builder offers orderKeysBy and orderValuesBy, which I think we envisioned half as a partial replacement for having an ImmutableSortedKeyMultimap, etc. and half as a way of performing a sorting step that today we'd perform with Stream.
This proposal raises a question as to whether we'd want, well, possibly the sort of Builder API that I'd mentioned, but more likely whether we'd want similar sortedCopyOf methods on ImmutableSet, etc.
There is probably a discussion to be had around the idea that ImmutableMap uses hashing for deduplication. For users of buildKeepingLast(), this raises questions about whether the sorting happens first or the deduplication happens first. This is in contrast to the Stream alternative of input.stream().sorted(...).collect(toImmutableMapKeepingLast()) [edit: Oops, that exists only in an internal "contrib" package.], which makes the ordering clear. (Not that I'd expect this to be a major issue, just something for us to consider, test, and document.)
Activity
DerrickUnleashed commentedon Aug 15, 2026
Hey @cpovirk, Can you check out this PR #8591
cpovirk commentedon Aug 15, 2026
At this point, we're still not sure if we want this, but if we decide that we do, we'll have a look.
cpovirk commentedon Aug 21, 2026
I still don't know whether we'll want this, but: One thing for us to remember is that static methods on
ImmutableMapend up inherited byImmutableBiMapandImmutableSortedMap. ForImmutableBiMap, we could consider supporting it. ForImmutableSortedMap, it is of course easy to support, albeit with the same type-safety problem ascopyOfand with questions around whether we should whencopyOfis equivalent.Stephan202 commentedon Aug 22, 2026
Sorry for the off-topic question, but: would that internal package happen to also contain
Collectorvariants forImmutableList.Builder#builderWithExpectedSizeand variants? This topic recently came up in our team. :)cpovirk commentedon Aug 22, 2026
Not to my recollection. I have hoped to someday solve some such problems by making at least our collections return a
Streamthat is smart enough to that (and more) automatically where possible. But my proposal and your proposal both support use cases that the other does not. If you're interested in sharing more, then, well, I can't realistically promise that it will make much difference in what I'm able to do, but I promise to read it :) Maybe open another issue and link back here?Margalit111 commentedon Sep 2, 2026
Design Proposal: Implementing ImmutableMap.sortedCopyOf
Motivation & Context
Currently, ImmutableSortedMap guarantees sorted iteration order at the cost of O(log N) lookup performance due to its underlying binary tree structure. Conversely, ImmutableMap delivers optimal O(1) hash-based lookups, but its iteration order is strictly bound to insertion order.
Obtaining a deterministically sorted ImmutableMap currently requires verbose Stream pipelines (e.g., collecting to an intermediate list/map and building), which introduces unnecessary memory overhead and garbage collection pressure. Providing a direct mechanism to produce a key-sorted ImmutableMap bridges this gap, enabling predictable iteration order (crucial for deterministic serialization and consistent outputs) while retaining O(1) hash lookup performance.
Trade-off Analysis & Core Design Choices
Direct Static Factory vs. Builder Integration:
While supporting sorting in ImmutableMap.Builder offers incremental construction flexibility, starting with static utility methods directly on ImmutableMap addresses the most common use case (transforming an existing map). It keeps the public API surface focused, parallel to ImmutableList.sortedCopyOf, and avoids introducing mutable sorting state to the existing builder implementations.
Restricting Input to Map:
We propose accepting Map<? extends K, ? extends V> rather than a broader Iterable. A Map contractually guarantees key uniqueness, allowing exact pre-allocation of the internal array (O(N)) with zero re-hashing or dynamic array growth.
Eliminating Duplicate Key Ambiguity:
Because an input Map has already resolved key collisions, this eliminates the ambiguity around duplicate handling strategies at this stage.
Collection Consistency (ImmutableSet):
While the same asymmetry exists for ImmutableSet (O(1) hash lookups vs. sorted iteration), we suggest addressing ImmutableSet.sortedCopyOf in a dedicated, follow-up PR to maintain granular and reviewable changes.
Addressing Static Method Inheritance (ImmutableSortedMap & ImmutableBiMap)
Because static methods on ImmutableMap are visible on subclasses, we must prevent type confusion and preserve type safety:
ImmutableSortedMap:
To prevent callers from receiving an ImmutableMap when invoking the method via ImmutableSortedMap, we can hide the method, return the subtype, and mark it @deprecated pointing users to copyOf(Map):
@deprecated
public static <K, V> ImmutableSortedMap<K, V> sortedCopyOf(Map<? extends K, ? extends V> map) {
return copyOf(map);
}
ImmutableBiMap:
BiMap strictly enforces value uniqueness. Inheriting a plain ImmutableMap factory could bypass this expectation. A dedicated override on ImmutableBiMap should sort entries by key while feeding them into an ImmutableBiMap.Builder, preserving bidirectional uniqueness checks and throwing IllegalArgumentException on duplicate values:
public static <K, V> ImmutableBiMap<K, V> sortedCopyOf(
Map<? extends K, ? extends V> map,
Comparator<? super K> comparator) {
ImmutableBiMap.Builder<K, V> builder = ImmutableBiMap.builder();
// Sort entries by key using the comparator and populate builder
builder.putAll(map);
return builder.build();
}
Proposed Signatures on ImmutableMap
public static <K extends Comparable<? super K>, V> ImmutableMap<K, V> sortedCopyOf(
Map<? extends K, ? extends V> map) {
return sortedCopyOf(map, Ordering.natural());
}
public static <K, V> ImmutableMap<K, V> sortedCopyOf(
Map<? extends K, ? extends V> map,
Comparator<? super K> comparator) {
// Extract entries, sort in-place, and construct via internal immutable array delegate
}
Future Work
If there is consensus to extend ordering capabilities to incremental construction later, the builder path can be addressed in a separate phase:
Readiness
If the maintainers are aligned with this scoped static approach and the inheritance safeguards, I would be glad to submit a PR containing the implementation and comprehensive test coverage.