java.util.HashMap类'keySet()方法的时间复杂度是多少？

Question

我正在尝试实现平面扫描算法,为此我需要知道java.util.HashMap类'keySet()方法的时间复杂度.我怀疑它是O(n log n).我对么？

澄清点:我在谈论keySet()方法的时间复杂性; 迭代返回的Set将显然花费O(n)时间.

Answer 1

实际上,获取密钥集O(1)并且便宜.这是因为HashMap.keyset()返回与HashMap关联的实际KeySet对象.

返回的Set 不是键的副本,而是实际HashMap状态的包装器.实际上,如果你更新集合,你实际上可以改变HashMap的状态; 例如,调用clear()该集将清除HashMap!

Answer 2

肯定会是O(1).它所做的就是在HashMap上返回一个包装器对象.

如果你正在谈论遍历键集,那么这是O(n),因为每个next()调用都是O(1),这需要执行n次.