The document says that get and insert for HashMap (not HashSet) are Ο(1)-like, but not for HashSet or len.
What is the computational complexity of HashSet::len?
Usually, the computational complexity of len is Ο(1). Is there a statement that indicates this?
https://doc.rust-lang.org/stable/std/collections/index.html#maps
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.
