Hash Set
A collection of unique elements that uses hashing for efficient O(1) checks, insertions, and removals.
Ready
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Think of it like a club guest list. You only care IF someone is on the list, not where they are sitting or how many times they appear (duplicates are ignored). When a guest arrives, you check the list instantly using their name (Hash) to see if they are already inside.
Concept
A Hash Set is essentially a Hash Map where the Key is the element itself, and the Value is ignored (or a dummy placeholder).
- Uniqueness: Stores distinct elements only. Adding a duplicate has no effect.
- Hashing: Uses the same hashing and collision resolution (Chaining/Probing) as Hash Maps to locate elements.
How it Works
Add(Element):
- Compute hash
h = hash(element)for bucket index. - Search bucket/probe sequence for the element.
- If found, do nothing (already exists).
- If not found, insert the element.
Contains(Element):
- Compute hash and find index.
- Search bucket. If found, return true. Else, false.
Step-by-Step Breakdown
Watch the visualization:
- Add Unique: Element is hashed and placed in an empty spot or chain.
- Add Duplicate: System checks, finds it exists, and rejects the addition.
- Remove: Element is found via hash and deleted.
When to Use
Applications:
- Removing duplicates from a collection (deduplication).
- Checking presence/membership (e.g., "Is this IP blocked?").
- Finding intersection/union of datasets.
- Visited tracking in Graph algorithms (BFS/DFS).
When NOT to Use
- Key-Value Pairs: Use Hash Map instead.
- Ordering: If you need elements sorted or in insertion order, use TreeSet or LinkedHashSet.
How to Identify
"Find unique", "Remove duplicates", "Check if visited", "Common elements".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.