Java Synchronized vs ConcurrentHashMap – Usage Comparison

hashmapjavasynchronized

This is the problem: we want a hash table whose entries are thread-safe.

Suppose I have a hash table of <String, Long>, and I want to increase the value of one of the entries thread safely: is the following OK?: 

HashMap<String , Long> hashTable = new HashMap<String, Long>();

Then whenever I want to increase an entry: 

Synchronized (hashTable.get("key"))
{
    Long value = hashTable.get("key");
    value++;
    hashTable.put("key", value);
}

I think it is better than ConcurrentHashMap, as it locks just one entry, unlike ConcurrentHashMap which uses buckets, and lock a group of entries together.

More importantly, I don't know how to increment it using COncurrenHashMap safely. For example I think the following code is not correct: 

 ConcurrentHashMap<String , Long> hashTable = new ConcurrentHashMap<String, Long>();


 Long value = hashTable.get("key");
 value++;
 hashTable.put("key", value);

I think it is not correct, because two threads can read the key one after another, and write one after another and end up in a wrong value.

What do you think guys?

Best Answer

Your proposed approach is not thread-safe because the initial hashTable.get() operation -- by which you obtain the object on which you intend to synchronize -- is not itself synchronized relative to other threads put()ing a value associated with the same key. Moreover, your code does not account for the possibility of new values being added to the map or keys being removed from the map (so-called "structural modifications"). If ever that can happen, regardless of key, then those actions have to be synchronized with respect to all other accesses to the map.

You are right, however, that ConcurrentHashMap does not solve these problems either. It is thread-safe with respect to the individual operations it provides, which include some that Map itself does not define, but series of operations that must be performed as an uninterrupted unit still need to be protected by synchronization.

I suggest a slightly different approach: use a ConcurrentHashMap with AtomicLong, which is mutable, as your value type instead of Long:

ConcurrentHashMap<String, AtomicLong> map;

Then, to update the value for a key, even if you're not confident that the key already has an entry in the map, you do this:

AtomicLong value = map.putIfAbsent(key, new AtomicLong(0));
long updatedValue = value.incrementAndGet();

The putIfAbsent() ensures that value objects are not clobbered by conflicting put operations. The use of AtomicLong avoids the need for multiple operations to be jointly synchronized, because only one map access is needed -- the value retrieved is shared by all threads accessing it, and can itself be atomically updated without further accessing the map.

If you can be certain that the map already has a mapping for the given key, then you can simply do this:

AtomicLong value = map.get(key);
long updatedValue = value.incrementAndGet();

One way or the other, I think this is about the best you can do for the operations you describe and imply.

Update:

You could even consider combining the two approaches like this:

AtomicLong value = map.get(key);

if (value == null) {
    value = map.putIfAbsent(key, new AtomicLong(0));
}

long updatedValue = value.incrementAndGet();

That supposes that it will be comparatively rare that there is not already a mapping for the given key, and it avoids creating a new AtomicLong in that case. If no mapping is found then the map must be accessed a second time to ensure that there is a mapping and to get the corresponding value, but here we still need putIfAbsent() if we want to avoid synchronization, because it is possible for two threads to both try to add a mapping for the same key, at about the same time. That's more costly when a new entry needs to be added, but it's possible that it would turn out to be less costly on average than my first suggestion. As with any performance question, however, it is essential to test.

Related Question