Data structures · foundation
Set vs map
A set stores unique values and answers membership questions, while a map associates each unique key with a value.
Why it matters
Choosing the narrower abstraction makes intent clear: use a set for existence or uniqueness and a map when each key must retrieve associated data.
Mental model
How to reason about set vs map
A set models a predicate, 'is this value present?'; a map models a function, 'what value is associated with this key?'. Both are often hash- or tree-backed.
Analogy
A guest list is a set of admitted names. A coat-check ledger is a map from each ticket number to a particular coat.
Examples
See the boundary, not just the happy path
Worked example · Remove duplicates
unique_ids = set(user_ids)Only membership matters, so storing a separate value for each identifier would add no information.
Worked example · Index records
user_by_id[id] = userThe identifier is a key and the complete user record is its associated value, so a map expresses the lookup.
Useful contrast · Multiset requirement
{'apple': 3, 'pear': 1}A plain set loses multiplicity. A map from item to count represents a multiset when occurrence counts matter.
Common mistakes
Misconceptions to remove early
Expecting a set to preserve duplicates
Adding an equal value again does not create a second occurrence. Use a list or a map of counts when multiplicity matters.
Assuming a particular iteration order
Order guarantees vary by type and language. Hash-based collections may not provide sorted order; choose an ordered or sorted implementation explicitly.
Quick check
Can you predict the result?
1. Which structure best answers whether an email address has already been seen?
- • A set of email addresses
- • A map from every email to the same constant
- • A priority queue ordered by email length
2. Why is a map appropriate for counting words?
Keep building