什麼是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

回答