什么是java.util.HashMap类的keySet（）方法的时间复杂度？ [英] What is the time complexity of java.util.HashMap class' keySet() method?

问题描述

我试图实现一个平面扫描算法，为此我需要知道时间复杂度 java.util.HashMap类的keySet（）方法。我怀疑它是O（n log n）。我是否正确？

澄清点：我正在讨论keySet（）方法的时间复杂度;迭代通过返回的Set将需要明显的O（n）时间。其实，获取键集是 O（1）且便宜。这是因为HashMap.keyset（）返回与HashMap关联的实际KeySet对象。

返回的Set不是键的副本，而是实际HashMap状态的包装。的确，如果你更新了这个集合，你实际上可以改变HashMap的状态;例如在集合上调用 clear（）将清除HashMap！

I am trying to implement a plane sweep algorithm and for this I need to know the time complexity of java.util.HashMap class' keySet() method. I suspect that it is O(n log n). Am I correct?

Point of clarification: I am talking about the time complexity of the keySet() method; iterating through the returned Set will take obviously O(n) time.

解决方案

Actually, getting the keyset is O(1) and cheap. This is because HashMap.keyset() returns the actual KeySet object associated with the HashMap.

The returned Set is not a copy of the keys, but a wrapper for the actual HashMap's state. Indeed, if you update the set you can actually change the HashMap's state; e.g. calling clear() on the set will clear the HashMap!

这篇关于什么是java.util.HashMap类的keySet（）方法的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！