据我了解，Hashmap 比标准映射更可取，因为您可以在接近 O(1) 的时间内找到元素。这是通过使用散列或键作为数组查找来完成的。然后我们解决任何冲突并提取值。
这对查找很有用，但是如果我们在其中进行哈希查找的数组空间是稀疏填充的，那么 hashmap/unorderedmap 如何有效地迭代我们的 hashmap 中的所有元素，而无需详尽地遍历我们的数组空间？
编辑：但 Boost、SGI 和 C++11 哈希映射/无序映射有迭代器，那么它们是如何工作的？
问问题
473 次
2 回答
2
除非存在并行结构（例如 a 中的链表LinkedHashMap），否则它不能：迭代将需要检查每个存储桶的内容。
因此，如果您的存储桶人口非常稀少，这可能会成为一个因素。这就是您不想选择太高的存储桶计数的原因之一（较大的存储桶显然会浪费内存）。
于 2011-08-31T10:27:41.157 回答
1
迭代为 O(n)，其中 n 是地图的容量（即桶数）。但通常情况下，您不应该有 100000 的容量来存储 6 个密钥。这意味着 O(size) 应该是 O(capacity)，这意味着迭代通常也是 O(size)。
于 2011-08-31T10:31:23.267 回答