HashingData structureaka set, unordered_set, HashSet

Hash Set

A collection of unique keys backed by a hash table, with expected O(1) add, contains, and remove.

▶ VisualizePattern: HashingPractice (5)
Progress

Definition

A hash set stores keys without associated values and guarantees each key appears at most once. It is a Hash Table whose entries are just keys; adding an existing key is a no-op.

The three operations that matter are add, contains, and remove, each expected O(1). Set algebra (union, intersection, difference) runs in O(|A| + |B|).

Typical roles: the visited set in graph traversals, deduplication, "have I seen this before?" checks in one-pass algorithms, and constant-time existence tests that replace an inner loop.

membershipuniqueO(1) averagededuplicationvisited

Intuition

A mental model before the formal terms.

A guest list at a door. The bouncer does not scan the list top to bottom; the list is organised so that a name can be checked instantly. Adding a name already on the list changes nothing.

It is a hash map whose values are all "present" — the only question it can answer is yes/no.

How it works

  1. Hash the key to a bucket.
  2. add(k): if the key is already in the bucket, return false; otherwise insert and return true, resizing when the load factor is exceeded.
  3. contains(k): scan the bucket for an equal key.
  4. remove(k): unlink the key from its bucket.
  5. Set operations iterate one set and probe the other.

Why it works

Uniqueness is enforced at insert time by the equality check inside the bucket; since equal keys hash equally, they always land in the same bucket and are detected.

Expected O(1) follows from the bounded load factor exactly as for the Hash Table.

Operations

OperationDescriptionCost
add(k)Insert if absent; returns whether it was inserted.O(1) average
contains(k)Membership test.O(1) average
remove(k)Delete if present.O(1) average
union / intersection / differenceSet algebra with another set.O(|A| + |B|)
size()Number of distinct keys.O(1)

Recognition

How to tell a problem wants this.

  • "Contains duplicate", "first unique", "distinct elements", "intersection of two arrays".
  • A graph or grid traversal must avoid revisiting nodes (visited set).
  • Cycle detection in sequences (happy number, linked list cycle without pointer tricks).
  • You need to test existence of x + k, x - 1, or a complement in O(1).
“have you seen this before” → Hashing“minimum steps” → Breadth-First Search

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Hash Table visualization.

a
∅
0
∅
1
∅
2
∅
3
∅
4
∅
5
∅
6
bucket 0
∅
0
bucket 1
∅
0
bucket 2
∅
0
bucket 3
∅
0
bucket 4
∅
0
bucket 5
∅
0
bucket 6
∅
0
1/41Empty table with m = 7 buckets. Colliding keys share a bucket as a linked chain, so the table never "fills up" — only the chains grow.
Hashed bucketChain node comparedMatchInserted / removed
PseudocodeLearn Hash Table →
1h = key % m
2insert: scan bucket[h]; if key present: done, else append to the chain
3search: scan bucket[h] comparing each key
4delete: scan bucket[h]; unlink the matching node
Variables
m7
size0
load0.00
Complexity
access O(1)
search O(1)
insert O(1)
delete O(1)
Speed

Pseudocode

1class HashSet:
2  table = HashTable()
3  add(k): if table.contains(k): return false; table.put(k, true); return true
4  contains(k): return table.contains(k)
5  remove(k): return table.remove(k)

Implementation

1def demo() -> None:
21 · Create and insert
3    seen: set[int] = set()
4    seen.add(3)
5    size_before = len(seen)
6    seen.add(3)                         # no-op: already present
7    inserted = len(seen) > size_before  # False
8 
92 · Membership and erase
10    has3 = 3 in seen
11    seen.discard(3)                     # remove() would raise if missing
12 
133 · Deduplicate a list (keeps first occurrence)
14    nums = [4, 1, 4, 2, 1]
15    unique = list(dict.fromkeys(nums))  # set(nums) alone loses order
16 
174 · Set algebra (intersection)
18    a, b = {1, 2, 3}, {2, 3, 4}
19    common = a & b                      # also a | b, a - b, a ^ b, a <= b
20    print(has3, inserted, unique, sorted(common))
21 
22 
23demo()
Walkthrough
  1. set() creates an empty set ({} would be a dict); add is a no-op for duplicates.
  2. discard silently ignores missing elements; remove raises KeyError.
  3. set does not preserve order, so order-preserving dedupe uses dict.fromkeys.
  4. Set operators & | - ^ and comparisons <= < implement set algebra directly.
Complexity (this implementation)
time O(1) average per operation · space O(n)
Language notes
  • frozenset is hashable, so sets of sets are possible.
  • Set comprehensions {f(x) for x in xs} build sets concisely.
  • Members must be hashable — use tuples for coordinates.
Common mistakes in this language
  • Writing s = {} for an empty set.
  • Expecting set iteration order to be stable across runs (string hashes are randomized).
  • Adding a list to a set (TypeError).
Language differences that matter here
  • Insertion feedback: C++ insert returns a bool; JS add returns the set; Python add returns None — compare sizes in JS/Python.
  • Order: JS Set is insertion-ordered; Python set and C++ unordered_set are not.
  • Set algebra: Python has operators; ES2025 adds methods to JS; C++ needs manual loops for unordered sets.
  • Composite members: Python tuples hash structurally; JS and C++ need string/number encoding or a custom hash.

Complexity

OperationAverageWorstNote
Access——No positional access; membership only.
SearchO(1)O(n)
InsertO(1)O(n)Amortized; resize is O(n).
DeleteO(1)O(n)
Update——Keys are immutable; remove and re-add.
ContainsO(1)O(n)
Union / IntersectionO(|A| + |B|)O(|A| · |B|)
SpaceO(n)

Advantages & disadvantages

Advantages
  • Constant-time membership with automatic deduplication.
  • Less memory than a hash map when values are unneeded.
  • Set algebra is built in and readable.
Disadvantages
  • Unordered: no min/max, no sorted iteration, no range queries.
  • Worst case O(n) under adversarial hashing; resize pauses.
  • Cannot store duplicates or multiplicities — use a counting Hash Map (multiset) for that.

Use cases

Use it when
  • Membership tests and deduplication with no need for values.
  • Visited tracking in graph and grid searches.
  • Set algebra between collections.
Avoid it when
  • You need counts per element — use a Hash Map counter.
  • Elements are small integers with a known range — a boolean Array or bitset (Bit Masks) is faster and denser.
  • You need ordered iteration or range queries — use a TreeSet / balanced BST.
  • Approximate membership at huge scale is acceptable — a Bloom Filter uses far less memory.

Alternatives

Hash MapArrayBit MasksBloom FilterAVL Tree

Common mistakes

  • Building a set inside a loop, making the algorithm O(n²) instead of building once and querying.
  • Using a mutable object as a set element and then mutating it.
  • Using a list for membership in Python (x in list is O(n)).
  • Marking nodes visited on dequeue rather than on enqueue in BFS, which lets duplicates flood the queue.
  • Expecting JavaScript Set to deduplicate structurally equal objects or arrays — it uses reference identity.

Interview patterns

  • Contains Duplicate: add each element, return true if add fails.
  • Longest Consecutive Sequence: only start counting from x if x - 1 is absent, giving O(n).
  • Intersection of Two Arrays: set of the smaller array, filter the larger.
  • Happy Number / cycle in a function iteration: store seen states.
  • Word Ladder: word set for O(1) neighbour validity, visited set for BFS.
Interview questions on this
Mock interviews

Interview problems

Repeated DNA SequencesmediumNumber of IslandsmediumWord LadderhardClone GraphmediumSingle Numbereasy