什么是java.util.HashMap类的keySet（）方法的时间复杂度？

我想实现一个平面扫描算法，为此我需要知道java.util.HashMap class' keySet()方法的时间复杂性。我怀疑它是O（n log n）。我对么？什么是java.util.HashMap类的keySet（）方法的时间复杂度？

要点澄清：我说的是keySet（）方法的时间复杂度;遍历返回的Set将需要明显的O（n）时间。

我不认为穿过这一组需要'显然'O（n）时间。该集合可能实际上不会生成。它可能只是一个可用于迭代的对象。而且，这里是什么？物品或桶？ – Ray 2012-09-03 06:06:10

这里n是散列表中条目的数量。如果集合有n个元素，为了迭代n个元素的集合，时间复杂度将是O（n）。 – agrawalankur 2012-11-01 22:05:21

其实，得到的键集是O(1)而且便宜。这是因为HashMap.keyset（）返回与HashMap关联的实际KeySet对象。

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

2009-12-05 01:59:20

这应该是可行的O（n）时间...哈希映射通常实现为一个大桶阵列，该桶的大小（通常）直接与哈希映射的大小成正比。为了检索密钥集，必须迭代桶，并且对于每个设置项，必须检索密钥（通过中间集合或直接访问存储桶的迭代器）...

* *编辑：正如其他人指出的，实际的keyset（）方法将在O（1）时间内运行，但是，遍历键集或将其转移到专用集合将是O（n）操作。不太确定你正在寻找哪一个**

2009-12-05 01:49:51 LorenVS

肯定会是O（1）。它所做的只是在HashMap上返回一个包装器对象。

如果您正在谈论走过键集，那么这是O（n），因为每个next（）调用都是O（1），并且这需要执行n次。

2009-12-05 01:51:38

Java集合有很多空间，因此不需要太多时间。我相信，这个方法是O（1）。收藏品就在那里。

2009-12-05 01:51:46 bmargulies

回答