[concurrency-interest] ConcurrentHashMap entrySet Iterator remove issue?

Ben Manes ben_manes at yahoo.com
Thu Feb 4 14:37:15 EST 2016

This is how the previous ConcurrentHashMap and ConcurrentSkipListMap work. Most 3rd party ConcurrentMap implementations have followed this pattern for consistency (e.g. NonBlockingHashMap and ConcurrentLinkedHashMap, ConcurrentSkipTreeMap, SnapTreeMap). The behavior for Iterator#remove() is unspecified for concurrent collections, so while perhaps surprising I wouldn't call it a bug. 

    On Thursday, February 4, 2016 11:15 AM, Mike Duigou <openjdk at duigou.org> wrote:

 Hello all;

I have found what seems like a bug in the way that the remove() method 
of CHM entrySet iterators works. The bug doesn't require concurrent 
behaviour but realistically that is the most likely way it arises. The 
problem is that the entrySet iterator remove() internally uses the 
chm.remove(key) method rather than the chm.remove(key, value) method. If 
there is an intervening replacement of the mapping for a key between the 
iterator next() and the remove() then it is possible to incorrectly 
remove that mapping.

I have made test program which compares the behaviour of 
entryset().remove(staleMapping) to entrySet().iterator() remove() of the 
same mapping.

I encountered the problem in real world code where the entry was 
replaced concurrently. I don't believe that there should be programs 
which expect the existing behaviour though undoubtedly there are some. I 
believe it is more likely that programs would/should expect the 
behaviour in which remove of a stale entry does nothing.



  * Written by Mike Duigou and released to the public domain, as 
explained at
  * http://creativecommons.org/publicdomain/zero/1.0/

package chm.test;

import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

  * Compares behaviour of removal of a stale entry via entrySet.remove() 
  * entrySet().iterator().remove()
public class ConcurrentHashMapBug {

    public static void main(String... args) {
        ConcurrentHashMap<String, String> chm = new 

        chm.put("fred", "wilma");
        chm.put("barney", "betty");

        Set<Map.Entry<String, String>> entries = chm.entrySet();

        // Attempt removal of a mapping through entrySet with stale 

        Map.Entry<String, String> fredEntry = null;
        for (Map.Entry<String, String> each : entries) {
            if ("fred".equals(each.getKey())) {
                fredEntry = each;
        assert fredEntry != null : "Entry not found";
        assert "wilma".equals(fredEntry.getValue()) : "wrong value";

        // modify fred mapping
        chm.put("fred", "mildred");
        // fredEntry is now stale
        assert "wilma".equals(fredEntry.getValue()) : "live value?";

        // attempt to remove our stale entry.
        assert !entries.remove(fredEntry) : "fred unexpectedly removed";
        // Mapping was not removed because entry value did not match 
current mapping.
        assert chm.containsKey("fred") : "fred mapping missing";
        assert "mildred".equals(chm.get("fred")) : "fred mapping 

        // Attempt remove of a  mapping through entrySet 
iterator.remove() with stale entry.

        Iterator<Map.Entry<String, String>> iter = entries.iterator();
        Map.Entry<String, String> barneyEntry = null;
        while (iter.hasNext()) {
            Map.Entry<String, String> each = iter.next();
            if ("barney".equals(each.getKey())) {
                barneyEntry = each;

        assert barneyEntry != null : "barney entry not found";
        assert "betty".equals(barneyEntry.getValue()) : "wrong value";

        // modify barney mapping
        chm.put("barney", "hortence");
        // barneyEntry is now stale
        assert chm.containsKey("barney") : "mapping missing";
        assert "hortence".equals(chm.get("barney")) : "mapping 
        assert "betty".equals(barneyEntry.getValue()) : "live value?";

        // attempt to remove our stale entry
        assert "betty".equals(barneyEntry.getValue()) : "live value?";
        // XXX Following fails. iter.remove() with stale entry 
incorrectly succeeds.
        // should behave like chm.remove(barneyEntry.getKey(), 
        assert chm.containsKey("barney") : "mapping missing";
        assert "hortence".equals(chm.get("barney")) : "mapping 

Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160204/eff2a18c/attachment-0001.html>

More information about the Concurrency-interest mailing list