vec_vs_hashset.md (3763B)
1 # Vec vs HashSet 2 3 [HashSet - Rust By Example](https://doc.rust-lang.org/rust-by-example/std/hash/hashset.html) 4 5 Sets have 4 primary operations (all of the following calls return an iterator): 6 7 - union: get all the unique elements in both sets. 8 9 - difference: get all the elements that are in the first set but not the second. 10 11 - intersection: get all the elements that are only in both sets. 12 13 - symmetric_difference: get all the elements that are in one set or the other, 14 but not both. 15 16 ### Question: Is HashSet O(1) and Vec O(n) in rust? 17 18 In Rust, the O(1) versus O(n) comparison between a `HashSet` and a `Vec` 19 primarily refers to lookup operations, such as checking if a collection contains 20 a specific element. While a `HashSet` provides O(1) average time complexity for 21 lookups, a `Vec` requires O(n) time because it must perform a linear search. 22 23 | Operation | `Vec<T>` | `HashSet<T>` | 24 | :---------------------- | :----------------------------------------------- | :--------------------------- | 25 | **Lookup (`contains`)** | O(n) [^7] | O(1) average [^7][^9] | 26 | **Add Element** | O(1) amortized (`push`) [^8] | O(1) average (`insert`) [^9] | 27 | **Remove Element** | O(n) (`remove`), O(1) (`pop`/`swap_remove`) [^8] | O(1) average (`remove`) | 28 29 ## Lookup Performance 30 31 Checking if an element exists using `contains()` is where the O(n) vs O(1) 32 difference is most prominent. A `HashSet` computes a hash to instantly find the 33 element's bucket, offering O(1) average lookup time regardless of the 34 collection's size. In contrast, a `Vec` must iterate through its elements one by 35 one until a match is found, resulting in O(n) time complexity where the search 36 time grows linearly with the number of elements.[^3][^7][^10] 37 38 ## Insertion and Removal 39 40 Appending an element to a `Vec` using `push()` operates in amortized O(1) time, 41 though occasional capacity reallocations can cause brief performance spikes. 42 `HashSet` insertions are also O(1) on average, but the operation carries a 43 higher "constant factor" because computing the hash and handling potential 44 bucket collisions requires more CPU work than simply placing an item at the end 45 of a vector. For removals, `HashSet` operates in O(1) average time, whereas 46 removing an element from a specific index in a `Vec` using `remove()` is O(n) 47 because it requires shifting all subsequent elements to fill the gap.[^8][^10][^3] 48 49 [^1]: https://users.rust-lang.org/t/hashset-foo-vs-vec-foo-as-a-key/103281/2 50 51 [^2]: https://users.rust-lang.org/t/iterating-through-hashmap-approx-twice-the-time-of-vec/75964/4 52 53 [^3]: https://stackoverflow.com/questions/72877598/hashset-is-slower-than-bruteforce-in-rust 54 55 [^4]: https://stackoverflow.com/questions/3185226/huge-performance-difference-between-vector-and-hashset 56 57 [^5]: https://wkaisertexas.github.io/blog/hashmaps-versus-vectors/ 58 59 [^6]: https://stackoverflow.com/questions/39803237/build-hashset-from-a-vector-in-rust 60 61 [^7]: https://zenn.dev/iriko/articles/d06fdc5a3de863 62 63 [^8]: https://oneuptime.com/blog/post/2026-02-01-rust-collections/view 64 65 [^9]: https://dev.to/alexmercedcoder/working-with-collections-in-rust-a-comprehensive-guide-3c9f 66 67 [^10]: https://nindalf.com/posts/optimising-rust/ 68 69 [^11]: https://users.rust-lang.org/t/vec-vs-hashmap-vs-hashset-for-unique-named-items/106615 70 71 [^12]: https://users.rust-lang.org/t/question-about-hashset/7779/2 72 73 [^13]: https://www.reddit.com/r/rust/comments/1c6h18a/hashset_method_slower_than_naive_method_when/ 74 75 [^14]: https://doc.rust-lang.org/rust-by-example/std/hash/hashset.html 76 77 [^15]: https://users.rust-lang.org/t/idiomatic-way-to-get-difference-between-two-vecs/48396