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

Question 1

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.

Question 2

The worst that can happen (besides an erroneous state of course) is probably an infinite loop when adding a value, blocking one of your threads.

See Paul Tyma article for more information on this case.

Question 3

What I have seen happen is you can get a corrupted linked list in your underlying HashMap (for handling collisions) which points back to itself. This is an issue I have seen a number of times over the years and it results in the thread going into an infinite loop.