Rust 中 `HashSet::len` 的计算复杂度

Question

我目前正在使用 Rust HashSet，并试图了解该HashSet::len操作的计算复杂性。

Rust 文档提供了有关get和insert操作的HashMap平均计算复杂度为 O(1) 的信息，但没有明确提及HashSet或len操作的复杂度。

一般来说，许多数据结构的 len 操作都是 O(1)，但我在 Rust 中找不到确认这一点的具体语句HashSet::len。以下是相关 Rust 文档的链接：Rust Collections

谁能澄清 的计算复杂性HashSet::len？是否如我所期望的 O(1)，或者 Rust 中的此操作是否有不同的复杂性HashSet？

Answer 1

为了这个，不得不深入一点兔子洞。简而言之，阅读源代码std::collections::HashMap表明标准 HashMaplen()从 crate 继承了其功能，crate 是 Google HashTable 变体 SwissTable ( githubhashbrown )的 Rust 端口。跟踪此箱中 的实现可找到底层类 ，其中包含条目类型的泛型 的实例。该结构包含一个被调用的槽，每当被调用时都会返回该槽。这表明该函数只是返回内部存储的整数计数的值，该计数跟踪条目的数量。len()RawTableRawTableInner<A>Aitems : usizelen()len()

总的来说，这表明 的时间复杂度len()将为 O(1)，因为它不进行任何迭代或计数，而只是返回在 HashTable 构造过程中维护的条目计数器的值。