在Java HashMap中确定最低可用键的最快方法是什么？

Question

想象一下这样的情况： 我有一个 HashMap<Integer, String>，其中存储了连接的客户端。它是 HashMap，因为顺序不重要，我需要速度。它看起来像这样：

{
    3: "John",
    528: "Bob",
    712: "Sue"
}

大多数客户端已经断开连接，这就是为什么我有一个很大的空档期的原因。

如果我想添加新的客户端，我需要一把钥匙，显然使用 _map.size() 来获取一把钥匙是不正确的。

所以，目前我使用这个函数来获取最低可用的钥匙：

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;
}

在某些情况下，这种方法真的很慢。有没有更快或更专业的方法来获取HashMap中最低的空闲键？

- Gábor DANI

---

可能的解决方案是不使用 HashMap，而改用 TreeMap。这样可以按照键的自然顺序迭代键。更多阅读：https://dev59.com/WnNA5IYBdhLWcg3wh-cC - Colin Basnett

如果顺序不重要，为什么给新客户一个低编号很重要？为什么不能随意分配一个编号给他们？ - DaveH

因为顺序无关紧要，但如果你想要一种最快的方法来确定最低键值的话，顺序就很重要。 - Brian Roach

你的搜索具有地图大小的上限。那是如何工作的，确切地说？ - Brian Roach

正如@BrianRoach所说，如果这确实是您需要的（一个新的唯一键，而不是最低的键），简单的解决方案是使用FIFO队列。一旦有人登录，您就会给他一个号码，当他们退出时，该号码将返回队列末尾以供重用。就像在医生办公室一样:)至少在我的国家是这样的。这种方法具有O(1)时间复杂度和O(n)内存来保存键。 - abc

Answer 1

如果你使用TreeMap，那么地图将自动按键排序。是的，你最终会得到O（log n）访问而不是O（1），但这是最明显的方法。当然，如果你真的需要的话，你可以同时维护一个HashMap和一个TreeSet，确保同时从两者中添加条目和删除条目，TreeSet只是地图键的有序集合。

- Jon Skeet