我正在尝试实现平面扫描算法，为此我需要知道java.util.HashMap class' keySet()方法的时间复杂度。我怀疑它是O（n log n）。我对么？
澄清点：我在谈论keySet（）方法的时间复杂性;迭代返回的Set将显然花费O（n）时间。
实际上，获取密钥集是O(1)和廉价。这是因为HashMap.keyset（）返回与HashMap关联的实际KeySet对象。
返回的Set不是键的副本，而是实际HashMap状态的包装器。实际上，如果你更新集合，你实际上可以改变HashMap的状态;例如在集合上调用clear()将清除HashMap！
肯定会是O（1）。它所做的就是在HashMap上返回一个包装器对象。
如果你正在谈论遍历键集，那么这是O（n），因为每个next（）调用都是O（1），这需要执行n次。
这应该在O（n）时间内可行...哈希映射通常实现为大型桶阵列，桶的大小（通常）与哈希映射的大小成正比。为了检索密钥集，必须迭代桶，并且对于每个集合项，必须检索密钥（通过中间集合或直接访问存储桶的迭代器）...
**编辑：正如其他人所指出的那样，实际的keyset（）方法将在O（1）时间内运行，但是，迭代密钥集或将其转移到专用集合将是O（n）操作。不太确定你要找哪一个**
Java集合有很大的空间，因此不需要花费太多时间。我认为，这种方法是O（1）。这个系列只是坐在那里。
为了解决“迭代返回的Set将需要明显的O（n）时间”注释，根据doc comments的HashMap，这实际上并不正确：
对集合视图的迭代需要与HashMap实例的“容量”（桶的数量）加上其大小（键 - 值映射的数量）成比例的时间。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低）非常重要。
所以换句话说，迭代返回的Set将采取O(n + c)，其中n是地图的大小，c是它的容量，而不是O(n)。如果选择了不适当大小的初始容量或载荷因子，则c的值可能会超过迭代时间方面的实际地图大小。
切线答案：
...迭代返回的
Set显然需要O(n)时间。
实际上并非总是如此：
HashMap创建的new HashMap<>()来说确实如此。最糟糕的情况是让所有N密钥落在同一个哈希链中。但是，如果地图自然增长，则哈希数组中仍会有N条目和O(N)插槽。因此，迭代条目集将涉及O(N)操作。HashMap是用new HashMap<>(capacity)和奇怪的（太大）capacity估计创建的，那就错了。然后，O(Cap) + O(N)操作将迭代条目集。如果我们将Cap视为变量，那就是O(max(Cap, N))，这可能比O(N)更糟糕。但是有一个逃避条款。由于capacity是当前int API中的HashMap，Cap的上限是231.因此，对于非常大的Cap和N值，复杂性是O(N)。
另一方面，N受可用内存量的限制，实际上你需要一个238字节（256GBytes）的堆，N超过最大可能的Cap值。对于大小的地图，最好使用针对大型地图调整的哈希表实现。或者不使用过大的容量估计！