Fastest way to determine the lowest available key in JAVA HashMap?

Fastest way to determine the lowest available key in JAVA HashMap?

Imagine a situation like this: I have a HashMap<Integer, String>, in which
I store the connected clients. It is HashMap, because the order does not
matter and I need speed. It looks like this:
{
3: "John",
528: "Bob",
712: "Sue"
}
Most of the clients disconnected, so this is why I have the large gap. If
I want to add a new client, I need a key and obviously the usage of
_map.size() to get a key is incorrect.
So, currently I use this function to get he lowest available key:
private int lowestAvailableKey(HashMap<?, ?> _map) {
if (_map.isEmpty() == false) {
for (int i = 0; i <= _map.size(); i++) {
if (_map.containsKey(i) == false) {
return i;
}
}
}
return 0;
}
In some cases, this is really slow. Is there any faster or more
professional way to get the lowest free key of a HashMap?