迭代 BTreeSet 和 HashSet 的时间复杂度是多少？

Question

例如，使用HashSet，我知道获取一个已知元素通常是 O(1)，但我想找出获取所有元素的时间复杂度是多少（不知道它们，所以是迭代）。

我在标准库文档中的任何地方都找不到此信息。我也看过 SwissTable，但没有成功。

它甚至可以衡量吗？我在哪里可以找到它？

Answer 1

特尔；博士：

• BTreeSet： 在）
• HashSet：O（容量）

树集

B-Tree 数据结构是 K 个元素的数组树，对于 K 的某个值。

Tree的深度为O(log N)，当节点数组不够满时，将节点合并在一起。对于我们的情况，我们可以使用节点必须至少是半满的规则，尽管任何常量都有效。

一般情况下，迭代是从小到大进行的，是一种中序遍历。这意味着从元素移动到下一个元素并不是严格的O(1)，实际上，从左子树的最右边元素移动到根意味着 O(log N) 步。

可以证明摊销复杂度为 O(1)，这导致 O(N) 的整体遍历复杂度。

哈希集

哈希映射或哈希集没有一般的迭代复杂度；它因实施而异。

Rust 中的实现本质上是一个开放式哈希表。这意味着一个非常大的 K 个元素数组（K = 容量），或多或少地人口稀少。

与大多数开放式哈希表一样，迭代没有短路。而是依次检查数组的每个元素。

因此，迭代时间与容量成正比，与元素数量无关。在人口稀少的哈希表上，这是相当昂贵的。

注意：Swiss 表使用开放式哈希表的变体，这不会影响各种操作的基本属性。