Guava: ImmutableMap.Builder#containsKey(K) possible?

[JWT007]

I have created several of my own builders for immutable classes.

In the builders I try to use the Guava immutable collection Builder's wherever possible.

If I use the ImmutableMap.Builder, the builder will collect duplicate keys and fail on the "build()". (Similar problem to that was described in https://github.com/google/guava/issues/360).

The proposal in issue 360 was to to immediately throw an IllegalArgumentException from the Builder if a duplicate key was added. This proposal was rejected because of the potential performance impact, which makes sense.

However, would it be possible to add a "containsKey(K)" method to roll through the existing entries looking for any with a matching key? This would be admittedly be an expensive operation, but the caller must decide if he wants to take the performance hit. The current functionality / performance of the Builder#put... would not be impacted.

ImmutableMap.Builder<String, FooBar> foobars = new ImmutableMap.Builder<>();

public void Builder addFoobar(FooBar foobar) {
  String foobarName = foobar.getName();
  if (foobars.containsKey(foobarName)) {
    throw new IllegalArgumentException("Duplicate FooBar name: " + foobarName);
  } else {
    foobars.put(foobarName, foobar);
  }
}

public void FooBarsHolder build() {
   return new FooBarsHolder(foobars.build());
}

As a workaround I am currently using a LinkedHashMap and then a ImmutableMap.copyOf(map); however, it would be nice to deal with the maps in the same manner as the lists, etc.

[Maaartinus]

I ran into this just yesterday and also switched to a mutable Map. IMHO the problem with your proposal is that nobody should ever use ImmutableMap.Builder#containsKey because of its quadratic complexity and because you can do

if (mutableMapUsedAsBuilder.put(foobarName, foobar) != null) {
    throw new IllegalArgumentException("Duplicate FooBar name: " + foobarName);
}

instead. It's even simpler and there's no additional lookup.

It's not exactly equivalent in case of duplicate keys, but you could use your variant as is or mine and put back the original value, if you insist on "first wins". AFAIK the only advantage of using the Builder in this case is that it produces less garbage, which IMHO isn't worth the overhead of containsKey.

[JWT007]

Hello Maaartinus,

Thanks for your quick answer.

The problem I see with your proposal is that in the event that I have a duplicate key, I have now pushed it to the builder and can not remove it - a guaranteed fail if I still get around to "build()" at some point. This would make it impossible to recover from this condition without starting all over with a new builder.

^^ ignore that ... see now that your were indicating I should use my mutable map and not the immutable map

[kluever]

If you need query operations, then +1 to using a mutable map and doing copyOf() at the very end when you're ready to "freeze" it.

[lowasser]

Providing an O(n) containsKey might be actually worse than doing nothing, if people use it without checking the documentation and think it's O(1) instead of falling back to a mutable map.