Hash Sets
DSA · Hashing
Theory
A hash set stores unique values with no associated data, using the same hashing idea as a hash table. Adding, removing and checking membership are O(1) on average. Sets also support union, intersection and difference, which makes them ideal for comparing groups.
Why we use it
Sets remove duplicates automatically and answer "have I seen this before?" instantly.
When to use it
Use sets for de-duplication, visited-node tracking in graphs, membership checks and comparing collections.
How it works
- For each item
- Item in set? Yes: Duplicate found / skip. No: Add item to set.
- Set holds unique items
Syntax
s = set()
s.add(x); s.remove(x); x in s O(1) avg
a | b union a & b intersection
a - b difference a ^ b symmetric differenceExample
visits = ["home", "sql", "home", "dsa", "sql", "blog"]
unique_pages = set(visits)
print("Unique pages:", sorted(unique_pages))
asha = {"SQL", "Python", "Power BI"}
ravi = {"SQL", "Snowflake", "Python"}
print("Both know:", sorted(asha & ravi))
print("Only Asha:", sorted(asha - ravi))
print("All skills:", sorted(asha | ravi))
def has_duplicate(nums):
seen = set()
for n in nums:
if n in seen:
return True
seen.add(n)
return False
print("Duplicate in [1,2,3,1]:", has_duplicate([1, 2, 3, 1]))Key points
- Stores unique items only
- O(1) average membership checks
- Supports set algebra
- Perfect for visited tracking