Efficiently "modifying" an ImmutableMap

Question

We're currently using Guava for its immutable collections but I was surprised to find that their maps don't have methods to easily create new maps with minor modifications. And on top of that, their builder doesn't allow assigning new values to keys, or removing keys.

So if I wanted to modify just one value, here's what I would like to be able to do:

ImmutableMap<Guid, ImmutableMap<String, Integer>> originalMap = /* get the map */;
ImmutableMap<Guid, ImmutableMap<String, Integer>> modifiedMap =
    originalMap.cloneAndPut(key, value);

Here's what it looks like Guava are expecting me to do:

ImmutableMap<Guid, ImmutableMap<String, Integer>> originalMap = /* get the map */;
Map<Guid, ImmutableMap<String, Integer>> mutableCopy = new LinkedHashMap<>(originalMap);
mutableCopy.put(key, value);
originalMap = ImmutableMap.copyOf(mutableCopy);
/* put the map back */

By doing this I get a new copy of the map with the modification I want. The original copy is untouched and I will be using an atomic reference to put the thing back so the whole setup is thread-safe.

It's just slow.

There is a lot of wasted copying going on under the covers here. Suppose there's 1,024 buckets in the map. That's 1,023 buckets which you're unnecessarily creating all over again (twice each, too), when you could have used those immutable buckets as-is and cloned only one of them.

So I guess:

1. Is there a Guava utility method buried somewhere for this sort of thing? (It isn't in Maps or on the ImmutableMap.Builder.)

2. Is there any other Java library which gets this sort of thing right? I am under the impression that Clojure has this sort of thing under the hood but we're not ready to switch languages just yet...

Answer 1

A bit unexpected the map of Functional Java is mutable like Guava's. The list is immutable though as I would expect.

Googling for "persistent collection java" brought up: pcollections. There are's a Map implementation.

Before actually using any other implementation I would benchmark the memory and performance characteristics against Guava. I would not be surprised if it's still better.

Answer 2

One may go with the following, to just duplicate the map once instead of twice:

ImmutableMap<String, Object> originalMap = /* get the map */;
Map<String, Object> modifiedMap = ImmutableMap.<String, Object>builder().putAll( originalMap )
   .put( "new key", new Object() )
   .build();

However, removing a value looks quite less beautiful with an iteration over the existing map, e.g. like this:

ImmutableMap<String, Object> originalMap = /* get the map */;
if( !originalMap.containsKey( "key to remove" ) ) {
   return;
}
ImmutableMap.Builder<String, Object> mapBuilder = ImmutableMap.builder();
for( Map.Entry<String, Object> originalEntry : originalMap.entrySet() ) {
   if( originalEntry.getKey().equals( "key to remove" ) ) {
      continue;
   }
   mapBuilder.put( originalEntry );
}
Map<String, Object> modifiedMap = mapBuilder.build();