RFC: Adding ConcurrentModificationException for HashMap.computeIfAbsent(), and JDK-8071667

[Stuart Marks]

On 2/3/15 4:01 PM, Brent Christian wrote:
> The code in bug 8071667 [1] passes a mappingFunction to computeIfAbsent() which
> itself put()s a sufficient number of additional entries into the HashMap to
> cause a resize/rehash.  As a result, computeIfAbsent() doesn't add the new entry
> at the proper place in the HashMap.
>
> While one should not (mis)use the mappingFunction in this way,
> HashMap.computeIfAbsent() (and similar HashMap methods which accept Lambda
> expressions) could check for and throw a ConcurrentModificationException on a
> "best-effort" basis, similar to iterators.  This is already done in bulk
> operations HashMap.forEach() and HashMap.replaceAll().
>
> I think it's also worth making mention of this in the JavaDoc.

I think we need to have the specification discussion *first* before we decide 
what HashMap should do with side-effecty computations that are passed to 
computeIfAbsent and friends. Unfortunately the API specification for 
Map.computeIfAbsent is largely silent about what should happen. I don't know 
whether that means that the result should be undefined, or that passing a 
function with side effects is implicitly allowed and should therefore be defined.

I'd think it would be quite unpleasantly surprising to find that passing a 
mapping function with side effects -- especially on keys other than the current 
operation -- results in essentially a corrupted map. Then again, I'm surprised 
that somebody would think to pass a mapping function that does have side 
effects. However, this is what people do, and they expect the library to behave 
reasonably.

I can think of an (only moderately contrived) use case that's probably behind 
the bug report. Suppose I want to have a map that starts empty but which is 
lazily initialized, and when it's initialized, it should contain entries for all 
keys A, B, C, D, and E. Furthermore, it should be lazily initialized when any 
one of these keys is put into the map. Of course, you can write this out easily 
yourself. But hey, there's this new computeIfAbsent() method that should let me do

     map.computeIfAbsent(key, k -> {
         /* put all entries A..E except k */
         return value_for_k;
     });

Based on the @implSpec for Map.computeIfAbsent, I'd expect this to work. And if 
your map inherits the Map.computeIfAbsent default implementation, it probably 
does work. Indeed, the workaround given in the bug report is essentially to 
implement your own method that duplicates the logic of the @implSpec and the 
default method. So, I'm leaning toward specifying that side effects should be 
supported, and that ConcurrentModificationException should not be thrown.

That implies that HashMap will have to detect the concurrent modification and 
deal with it instead of throwing an exception.

If we do clarify the spec to support this case, it probably shouldn't make any 
guarantees about what should happen if the mapping function puts the *same* key. 
That is, if

     map.computeIfAbsent(key, k -> {
         put(k, value1);
         return value2;
     });

it seems reasonable that it not be defined which of value1 or value2 ends up 
getting mapped to the key.

s'marks


> Here's an example of what might be done, using computeIfAbsent() as an example:
>
> http://cr.openjdk.java.net/~bchristi/8071667/webrev.0/
>
> I would update HashMap and Hashtable.  It looks like
> ConcurrentHashMap.computeIfAbsent() already forbids such usage, stating that the
> computation "must not attempt to update any other mappings of this map."
>
>
> Comments on this approach?
>
> Thanks,
> -Brent
>
> 1. https://bugs.openjdk.java.net/browse/JDK-8071667
>     "HashMap.computeIfAbsent() adds entry that HashMap.get() does not find."