CODEWITHSUNDEEP
rustcollectionshashmaptime-complexityhashset
Azriel 1rf
Azriel 1rf

Reputation: 177

Computational Complexity of `HashSet::len` in Rust

I'm currently working with Rust's HashSet and I'm trying to understand the computational complexity of the HashSet::len operation.

The Rust documentation provides information about the computational complexity of get and insert operations for HashMap being O(1) on average, but it doesn't explicitly mention the complexity for HashSet or the len operation.

In general, the len operation for many data structures is O(1), but I couldn't find a specific statement confirming this for HashSet::len in Rust. Here's the link to the relevant Rust documentation: Rust Collections

Could anyone clarify the computational complexity of HashSet::len? Is it O(1) as I would expect, or is there a different complexity associated with this operation in Rust's HashSet?

Upvotes: 8

Views: 1272

Answers (1)

dsillman2000
dsillman2000

Reputation: 1026

Had to go down a bit of a rabbit hole for this one. In short, reading the source code from std::collections::HashMap indicates that the standard HashMap inherits its len() functionality from the crate hashbrown, which is a Rust port of the Google HashTable variant, SwissTable (github). Tracking down the implementation of len() in this crate leads down to the underlying class, RawTable, which contains an instance of RawTableInner<A>, generic for the entry type A. This struct contains a slot called items : usize which is returned whenever len() is called. This indicates that the len() function simply returns the value of an internally stored integer count which keeps track of the number of entries.

Overall, this suggests that the time complexity of len() will be O(1), as it isn't doing any iteration or counting, but rather simply return the value of an entry counter which has been maintained over the course of the HashTable's construction.

Upvotes: 15

Related Questions