Concurrent add on non threadsafe HashSet - what is the worst that could happen?

hashset, java, multithreading, thread-safety

Solution

That depends on what you consider as being "worst".

I'm not sure whether this question aimed at a detailed, technical analysis of the current implementation considering all possible race conditions and the nitty-gritty details of the Java memory model.

So if the question is: "What can provably happen in the current implementation?" then I have to say: "I don't know". And I assume that hardly anybody knows this for sure in detail. (It's somehow like asking "Which parts of your car will be broken after you hit a wall with 100 mph?" - well, maybe the steering wheel will still be intact, but does this matter?)

But if the question is "What is not unlikely to happen when accessing a not-threadsafe `HashMap` with multiple threads?" then there are many possible answers:

- Deadlocks

- Exceptions

- Missing elements

- Elements being inserted multiple times

- Elements being inserted into the wrong hash bin

- ...

(Roughly ordered by my subjective interpretation of "badness"...)

EDIT: A clarification for the comment: Of course, an element could only be added twice if the call to insert it occurs multiple times. According to the specifiction, the `HashMap` should contain each key at most once. But the call for adding a new entry to the `HashMap` eventually delegates to the call

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

And there is no (obvious) reason why no other thread should cause a rehash (and thus, the creation of a new `table` array) between the first and the second line of this method. Then the `bucketIndex` for this call would be wrong. When the entry is then added a second time, it could use the (then) right `bucketIndex`, and thus, would afterwards be contained twice in the map.

But again: In order to really prove that this might happen, one would have to study the implementation in a detail that is hardly feasible. The bottom line is: Basically anything can go wrong when adding elements with multiple threads to a non-threadsafe `HashMap`.

Problem

Original source