HashTable synchronized methods and race conditions

Question

I am trying to get a grip on Collections here and found an article at Race condition

It states that the below code may lead to race condition :

if (! hashtable.contains(key)) {
  hashtable.put(key, value);
}

I understood the explanation there to a certain extent but I have a doubt that since the methods of HashTable are synchronized, how is it possible that while thread1 is executing the put() method acquiring the lock on the entire Hashtable, other thread2 can execute the containskey() method? Aren't both these methods synchronized on the hashtable lock?

and what if the thread 1 is already AFTER checking IF condition but BEFORE execution put? In this case it is not inside any synchronizatoion — Maciej, Mar 13 '18 at 10:12
"Aren't both these methods synchronized on the hashtable lock?" Yes, but the lock is released in between the invocation of the two methods. — Andy Turner, Mar 13 '18 at 10:12

Andy Turner · Answer 1 · 2018-03-13T17:25:49.993

The synchronization on HashTable is per method: the lock is acquired and held only for the duration of the method invocation.

The code here is equivalent to:

boolean contains;
synchronized (hashtable) {
  contains = hashtable.contains(key);
}

if (!contains) {
  synchronized (hashtable) {
    hashtable.put(key, value);
  }
}

It is entirely possible that another thread interleaves between these two synchronized blocks, resulting in the race condition.

It is worth noting that HashTable is effectively deprecated, and only retained for legacy reasons. More modern alternatives would be Collections.synchronizedMap(new HashMap<>()) (which behaves basically the same from a synchronization perspective; see this question), or ConcurrentHashMap, which provides methods to update the map atomically, e.g.

concurrentHashMap.putIfAbsent(key, value);

Java 8 maps do provide computeIfAbsent, but it is not guaranteed to be atomic, except for in ConcurrentHashMap.

Gray · Accepted Answer · 2018-03-14T12:41:23.537

how is it possible that while thread1 is executing the put() method acquiring the lock on the entire Hashtable, other thread2 can execute the containskey() method?

It's not possible. The issue here is not about Hashtable class itself which, as you point out, is a synchronized class so will not be corrupted. The race condition is that thread-A may test for a key that doesn't exist. But before it can do the put, thread-B tests for the same key that still doesn't exist. Then both threads put the same value into the table with one of them overwriting the other. This is the race.

1   if (! hashtable.contains(key)) {
2       hashtable.put(key, value);
3   }

To enumerate the race more completely:

Thread-A calls hashtable.contains("foo") which returns false on line #1.
Thread-B runs then also calls hashtable.contains("foo") which also returns false on line #1.
Thread-A calls hashtable.put("foo", "bar") on line 2.
Thread-B calls hashtable.put("foo", "baz") on line 2.

If this happens in this order (and it certainly can), then Thread-B will overwrite Thread-A's value for "foo". Hashtable isn't corrupted but the overwrite may not have been expected by the logic of the code. It might also happen that 4 and 3 are reversed so Thread-A would overwrite Thread-B's value for "foo". The nature of a race condition is that thread run order cannot be predicted and to ensure the right logic you need to apply specific locking.

Btw, Hashtable is an old class and has been superseded by ConcurrentHashMap. But the race condition would still exist with ConcurrentHashMap although it does have atomic operations like concurrentMap.putIfAbsent(key, value) for this reason. See ConcurrentMap javadocs.

HashTable synchronized methods and race conditions

2 Answers2