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

Question

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?

Possible solution is to not use a `HashMap` and use a `TreeMap` instead. You can iterate over the keys in their natural order. Further reading: http://stackoverflow.com/questions/922528/how-to-sort-map-values-by-key-in-java — Colin Basnett, Aug 20 '13 at 21:20
If order does not matter, why is it important to give the new client a low number? Why not just allocate any old number to them? — DaveH, Aug 20 '13 at 21:21
*"because the order does not matter"* it does if you want one of the fastest ways to determine the lowest key. — Brian Roach, Aug 20 '13 at 21:43
Your search has an upper bound of the size of the map. How does that work, exactly? — Brian Roach, Aug 20 '13 at 21:53
As @BrianRoach said if it's really what you need (a new unique key, not the lowest one), simple solution would be some FIFO queue. You have keys there once someone logs in you give him a number and when they log out, the number goes back to queue at the end for reuse. It's like at doctors office :) atleast in my country. Such approach have O(1) time complex and O(n) memory for holding keys. — abc, Aug 20 '13 at 21:54

score 5 · Accepted Answer · answered Aug 20 '13 at 21:20

Any reason to use a HashMap? If you used TreeMap instead, the map would be ordered by key automatically. Yes, you end up with O(log n) access instead of O(1), but it's the most obvious approach.

Of course you could always maintain both a HashMap and a TreeSet, making sure you add entries and remove entries from both together, if you really needed to. The TreeSet would just act as an ordered set of keys for the map.

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

1 Answers1

Linked