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

Question

例如，使用HashSet，我知道获得一个已知元素通常是O(1)，但是我想找出获得所有元素的时间复杂度是什么(不知道它们，因此是一个迭代)。
我在标准库的文档中找不到任何信息。我也看过SwissTable，但没有成功。
它甚至可以测量吗？在哪里可以找到它？

Answer 1

TL； DR :

BTreeSet:O(N)

HashSet:O(容量)

B树集
对于某些K值，B树数据结构是由K个元素组成的数组树。
树的深度为O(log N)，并且当节点的数组不足时，它们会合并在一起。对于我们的情况，我们可以使用以下规则:尽管任何常量都可以工作，但节点必须至少是半满的。
通常，迭代是从最小到最大完成的，这是有序遍历。这意味着从元素到下一个元素的移动并不是严格意义上的O(1)，实际上，从左子树的最右边的元素到根元素的移动意味着O(log N)步。
可以证明，摊销的复杂度为O(1)，这导致O(N)的整体遍历复杂度。
哈希集
哈希映射或哈希集没有一般的迭代复杂性；它因实现而异。
Rust的实现本质上是一个开放式哈希表。这意味着大量的K元素(K =容量)，或多或少稀疏。
与大多数开放式哈希表一样，迭代没有短路。而是依次检查数组的每个元素。
因此，迭代时间与容量成正比，而与元素的数量无关。在稀疏填充的哈希表上，这非常昂贵。
注意:Swiss表使用开放式哈希表的变体，这不会影响各种操作的基本属性。