Hash Sets vs Maps
Overview
Both Hash Maps (Dictionaries) and Hash Sets are powered by hash tables under the hood. A Hash Map binds a unique key to an associated value (e.g., UserID -> Profile). A Hash Set stores ONLY unique keys, with no associated values.
You use a Map when the data has inherent duality—you need to look up a key to retrieve a specific payload. You use a Set when you purely need to answer a binary existence query: 'Have I seen this exact item before?'
Where used: Sets: Identifying the boundaries of sequences by checking if `num - 1` exists in O(1) time., Maps: Grouping anagrams by mapping a sorted signature string to a list of matching words.
Why learn this
- Choosing the correct semantic data structure signals competence to an interviewer. Using a Map when a Set would suffice indicates a lack of precision.
- Many modern language implementations of Hash Sets (like Java's `HashSet`) literally just use a Hash Map under the hood with dummy values, proving the underlying mechanics are identical.
- Sets are the ultimate tool for O(n) array deduplication.
Aha moment
# Deduplicating an array in Python
raw_data = [1, 2, 2, 3, 4, 4, 4, 5]
# The O(n) magic trick:
clean_data = list(set(raw_data))
print(clean_data) # [1, 2, 3, 4, 5]Prediction: You have to write a loop to filter out duplicates.
Common guess: Deduplication requires sorting the array first or using nested loops.
Because a Set mathematically cannot contain duplicates, simply casting an array to a Set automatically deduplicates it in a single O(n) pass. It is the cleanest, fastest way to extract unique elements in any language.
Common mistakes
- Iterating over a map to find a key: If you write `if key in my_map.values():`, you have fundamentally broken the hash table. Values are not hashed. Searching values takes O(n) linear time. You must search by keys.
- Forgetting Sets enforce uniqueness: Adding the same element to a Set 100 times results in a Set of size 1. If you need to track how many times an element appeared, you must use a Hash Map where the value is an integer counter.
Glossary
- inherent duality
- Having two connected parts, like a paired key and its corresponding value.
- semantic data structure
- A way of organizing data that clearly communicates the programmer's intent.
- binary existence query
- A simple yes-or-no question asking whether an item is present or not.
Recall questions
- What is the primary structural difference between a Hash Map and a Hash Set?
- If you need to know if a specific username has already been taken, which structure is more semantically correct?
Understanding checks
A developer wants to count how many times each word appears in a book. They try to use a Hash Set, adding each word as they read it. Why does this fail to solve the problem?
Sets enforce strict uniqueness and discard duplicates. At the end, the developer will only have a list of unique words, with no record of their frequencies. They need a Hash Map mapping `Word -> Count`.
This distinction is the crux of choosing between the two structures. Frequencies require a payload (the count), mandating a Map.
You have an array of 100,000 user IDs, and you need to repeatedly check if incoming requests match any of these IDs. Does using a Hash Set or a Hash Map make more sense here?
A Hash Set makes more sense. You only need to verify existence (is the ID in the allowed list?), which requires no associated value.
Sets are the standard data structure for fast O(1) membership testing where no payload is required.
Practice tasks
Array intersection
Given two arrays, `arr1` and `arr2`, return a list of elements that appear in both arrays in O(n + m) time.
Continue learning
Previous: Hash Tables