获取散列表中密钥列表的时间复杂度？

在很多语言中，您可以从散列表中获取密钥列表。像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

因此，关键词列表在列表总体中保持不变或者之后解决？ –

回答