Hash Set
A hash map that stores only keys, no values — membership (contains), insert, and remove all average O(1) via the same hashing and collision-handling machinery as a hash map.
A hash set is a hash map with the values stripped away: it answers "is x in this collection?" rather than "what value is x mapped to?". Internally it is typically implemented literally as a hash map whose values are ignored (or a unit type), reusing every mechanism — bucket hashing, chaining, resizing — from the hash map.
The operations that make sense change accordingly: add, remove, and contains replace put/get/remove; set operations (union, intersection, difference) become natural additions no key-value map needs.
Same trade-offs as a hash map apply: average O(1) for the core operations, degrading toward O(n) under a bad hash function or after a load factor exceeds the resize threshold, at which point a rehash (O(n)) happens.
Operations
| Operation | Complexity |
|---|---|
| add | O(1) average |
| contains | O(1) average |
| remove | O(1) average |
| union / intersection | O(n + m) average |
Where it's used
Deduplication, "have I seen this before" checks, fast membership testing, set algebra (tags, permissions, visited-node tracking in graph algorithms).