How does computeIfAbsent fail ConcurrentHashMap randomly?

The problem isn't in the computeIfAbsent call, but rather in the .add(key) at the end: you can have multiple threads trying to add elements to the same HashSet, with nothing to ensure safe concurrent access. Since HashSet isn't threadsafe, this doesn't work properly, and the HashSet sometimes ends up in a corrupt state. Later, when you try to iterate over the HashSet to get a string, it blows up due to this corrupt state. (Judging from your exception, the HashSet thinks its backing array is longer than it actually is, so it's trying to access out-of-bounds array elements.)

Even in the runs where you don't get an exception, you probably sometimes end up "dropping" elements that should have gotten added, but where concurrent updates mean that some updates were lost.

ConcurrentHashMap.computeIfAbsent executes atomically, that is, only one thread can access the value associated with a given key at a time.

However, there is no such guarantee once the value is returned. The HashSet can be accessed by multiple writing threads, and as such is not being accessed thread-safely.

Instead, you can do something like this:

valueKeyMap.compute(value, (k, v) -> {
    if (v == null) {
      v = new HashSet<>();
    }
    v.add(key);
    return v;
});

which works because compute is atomic too.