Atomically searchKeys() and put() in a ConcurrentHashMap

Using string concatenation is a bad choice for a compound key. String concatenation is an expensive operation and it doesn’t guaranty uniqueness, as the key becomes ambiguous when one of the strings contains the separator of your choice.

Of course, you can forbid that particular character in user names, but this adds additional requirements you have to check, whereas a dedicated key object holding two references is simpler and more efficient. You may even use a two element List<String> as an add-hoc key type, as it has useful hashCode and equals implementations.

But since you want to perform lookups for both parts of the compound key anyway, you should not use a compound key in the first place. Just associate both user names with the same Challenge object. This still can’t be done in a single atomic operation, but it doesn’t need to:

final ConcurrentHashMap<String, Challenge> challenges = new ConcurrentHashMap<>();

Challenge startNewChallenge(String user1, String user2) {
    if(user1.equals(user2))
        throw new IllegalArgumentException("same user");

    Challenge c = new Challenge();

    if(challenges.putIfAbsent(user1, c) != null)
        throw new IllegalStateException(user1+" has an ongoing challenge");

    if(challenges.putIfAbsent(user2, c) != null) {
        challenges.remove(user1, c);
        throw new IllegalStateException(user2+" has an ongoing challenge");
    }

    return c;
}

This code will never overwrite an existing value. If both putIfAbsent were successful, both user definitely had no ongoing challenge and are now both associated with the same new challenge.

When the first putIfAbsent succeeded but the second fails, we have to remove the first association. remove(user1, c) will only remove it when the user still is associated with our new challenge. When all operations on the map follow the principle to never overwrite an existing entry (unless all prerequisites are met), this is not necessary, a plain remove(user1) would do as well. But it doesn’t hurt to use the safe variant here.

The only issue with the non-atomicity is that two overlapping attempts involving the same user could both fail, due to the temporarily added first user, when actually one of them could succeed. I do not consider that a significant problem; the user simply shouldn’t attempt to join two challenges at the same time.

You must review your code.

You cannot do this in one time as you have two names to check. Even in a conventional (iterating) way you would have in the best case two operation. So anyway you will need to do at least two access on the map. I suggest you to use your actual map without the concatenation of strings, so yes, one Challenge will appear two time in the map, one for each participant. Then you will be able to check easily if a user is engaged.

If you need to know with whom he is engaged, simply store the both names in the Challenge class.

Of course lock your map when you are looking for both entries. A function who return a Boolean will do the job !

From my perspective it's possible, but the map has to use individual player names as keys, so for both players we have to put one challenge twice. Having this, we can introduce additional async checking whether the new challenge was successful stored for the both players.

private boolean put(Map<String, Challenge> challenges, String firstPlayerName,
        String secondPlayerName,
        Challenge newChallenge) {

    if(firstPlayerName.compareTo(secondPlayerName) > 0) {
        String tmp = firstPlayerName;
        firstPlayerName = secondPlayerName;
        secondPlayerName = tmp;
    }

    boolean firstPlayerAccepted = newChallenge == challenges.merge(firstPlayerName, newChallenge,
            (oldValue, newValue) -> oldValue.isInitiated() ? oldValue : newValue);
    boolean secondPlayerAccepted = firstPlayerAccepted
            && newChallenge == challenges.merge(secondPlayerName, newChallenge,
            (oldValue, newValue) -> oldValue.isInitiated() ? oldValue : newValue);

    boolean success = firstPlayerAccepted && secondPlayerAccepted;
    newChallenge.initiate(success);
    if (firstPlayerAccepted) {
        // remove unsuccessful
        challenges.computeIfPresent(firstPlayerName, (s, challenge) -> challenge.isInitiated() ? challenge : null);
        if (secondPlayerAccepted) {
            challenges.computeIfPresent(secondPlayerName, (s, challenge) -> challenge.isInitiated() ? challenge : null);
        }
    }
    return success;
}

class Challenge {

    private final CompletableFuture<Boolean> initiated = new CompletableFuture<>();

    public void initiate(boolean success) {
        initiated.complete(success);
    }

    public boolean isInitiated() {
        try {
            return initiated.get();
        } catch (ExecutionException e) {
            throw new IllegalStateException(e);
        } catch (InterruptedException e) {
            return false;
        }
    }
    enter code here
...
}