獲取散列表中密鑰列表的時間複雜度？

在很多語言中，您可以從散列表中獲取密鑰列表。像java中hashSet的keySet（）方法一樣。如何從一個填充哈希映射中獲得？是不是不可逆的？你是否也將鑰匙放在單獨的列表中？獲取散列表中密鑰列表的時間複雜度？

所以，當我使用函數來獲得填充哈希表中使用的關鍵字列表該函數的時間複雜度是多少？

對於我特別的問題，我碰巧知道散列表中最大的條目數。這有幫助嗎？

實際上每個散列表除了存儲值之外還存儲密鑰。無論如何，這是需要解決散列衝突（在某些情況下，衝突可能是不可能的，但這需要事先枚舉完整的密鑰集，因此它不適用於通用散列表）。也就是說，哈希表{"foo": 1, "bar": 2}不會是這樣的：

1 
2

而是這樣

("foo", 1) 
("bar", 2)

遍歷鍵然後簡單地遍歷哈希表的底層結構的問題。

2013-12-14 16:31:39 delnan

所以需要時間與表中的條目數成比例的時間？ –

@HenrikSommerland是的。它必須，即使它能夠在無時間的情況下變出密鑰，它仍然必須這樣做n次。更精確的界限是數組中的桶的數量（在開放地址中可以不同） - 但由於該數量應該至多是條目數量的小常數倍（例如爲了避免浪費空間），它不會真的不重要。 – delnan

在任何合理的實現中，以自然順序（不排序）觸摸所有鍵爲O（包括空插槽的表的當前大小）。

在將條目鏈接在一起的實現中（例如，您可以在the LinkedHashMap iterator code here中觀察到的Java），表大小是不相關的。該算法正在遍歷鏈表。

您不需要知道散列鍵，因爲迭代直接觸摸數據結構，而不使用鍵。

2013-12-14 16:22:00 Gene

因此，關鍵詞列表在列表總體中保持不變或者之後解決？ –

回答