[concurrency-interest] Bug in ConcurrentHashMap

Eric Zoerner eric.zoerner@gemstone.com
Thu, 20 Nov 2003 15:16:28 -0800


The following junit test exposes a bug in ConcurrentHashMap. This test failed on
the preliminary test release 2, but the same defect appears to be in the current
version of ConcurrentHashMap in the CVS repository.

The problem is the implementation of the setValue method in the Map.Entry that
you get back from entrySet. The entry returned is a reference to a HashEntry
that can get cloned when there is a removal or a rehash on the map. If that
occurs, then the setValue method does not write-through to the map, violating
the contract of the setValue method.


    private static ConcurrentHashMap longChainMap() {
      ConcurrentHashMap map = new ConcurrentHashMap(2, 5.0f, 1);
      assertTrue(map.isEmpty());
      for (int i = 0; i < 20; i++)
        map.put(new Integer(i), new Integer(i));
      assertFalse(map.isEmpty());
      return map;
    }


    public void testSetValue() throws InterruptedException {
      final Map map = longChainMap();
      Map.Entry entry1 = (Map.Entry)map.entrySet().iterator().next();

      // assert that entry1 is not 16
      assertTrue("entry is 16, test not valid",
        !entry1.getKey().equals(new Integer(16)));

      // remove 16 (a different key) from map in another thread,
      // which just happens to cause entry1 to be cloned in map
      Thread t = new Thread() {
         public void run() {
           map.remove(new Integer(16));
         }
      };
      t.start();
      t.join();

      entry1.setValue("XYZ");
      assertTrue(map.containsValue("XYZ")); // fails
    }


An idea for a fix is to implement setValue by doing a put directly on the map
in addition to setting the value in the entry, however HashEntry is a static
inner class and does not have a reference to the map. Making it non-static
would add additional overhead to each entry object that I would prefer to
avoid. Furthermore, the put should only succeed on the map if the entry is still
present.

Which leads me to another comment. It would be useful to have a "putIfPresent"
method on ConcurrentMap in addition to the putIfAbsent that is already there,
for the case where you require the entry to already exist when replacing a
value.