The Core Idea
A Collection That Only Promises Two Things
A set is a collection with exactly two defining guarantees: every element is unique (no duplicates are ever stored, even if you try to add the same value twice), and it supports fast membership testing ('is this value present?'). Notably, a set makes no promise at all about ordering — unlike an array or list, you generally can't ask for 'the 3rd element of the set,' because that concept doesn't meaningfully apply.
Most set implementations are built directly on top of a hash table internally, using only the keys and discarding any associated value — which is exactly why sets inherit the hash table's average O(1) performance for adding, removing, and checking membership.
💡 Memory Trick
Think of a set as a bouncer's guest list at a club door — the bouncer doesn't care what order names were added in, and if your name is already on the list, adding it again changes nothing. The bouncer's only job, done instantly, is answering one question: 'is this specific name on the list, yes or no.'
The Core Operations
Membership, Insertion, and Set Algebra
1
Membership Test — average O(1)
Checking whether a value exists in the set hashes the value and checks the corresponding bucket, exactly like a hash table lookup — because that's precisely what's happening under the hood.
2
Add / Remove — average O(1)
Adding a value that's already present has no effect (uniqueness is automatically preserved); adding a new value or removing an existing one both cost the same as a hash table insertion or deletion.
3
Union — combining two sets
Produces a new set containing every element that appears in either original set, with duplicates automatically collapsed since a set can't contain the same value twice.
Example: {1, 2, 3} ∪ {2, 3, 4} = {1, 2, 3, 4}.
4
Intersection and Difference
Intersection produces a new set containing only elements present in BOTH original sets. Difference (A − B) produces a new set containing elements present in A but NOT in B.
Example: {1, 2, 3} ∩ {2, 3, 4} = {2, 3}, while {1, 2, 3} − {2, 3, 4} = {1}.
Set vs. List vs. Hash Table
Choosing the Right Collection
Choose a set when you specifically need uniqueness enforcement and fast membership testing, but don't care about order and don't need to associate each item with a separate value — 'has this user already voted,' 'which words have I already seen while processing this text,' and 'find all unique visitors to a website' are all textbook set use cases.
Choose a hash table (map/dictionary) instead when you need to associate each key with some additional value — a set only stores the keys themselves. Choose a list or array instead when order matters or duplicates are meaningful and need to be preserved — sets discard both of those properties by design, not as a limitation to work around, but as the entire reason sets are fast at what they do.
🖥️ Applied Scenario
You're processing a massive log file to determine how many distinct IP addresses accessed your server, out of billions of total log lines (many IPs appearing repeatedly).
1
You reject storing every IP address in a plain list, since checking whether a given IP has already been seen (to avoid double-counting) would require an O(n) scan through everything seen so far, for every single log line.
2
You use a set instead: for each log line, you attempt to add that IP address to the set — if it was already present, the set silently ignores the duplicate; if it's new, it's added.
3
Because the set enforces uniqueness automatically, at the end of processing, the set's final size IS the exact count of distinct IP addresses — no separate deduplication step needed.
4
Conclusion: the set's average O(1) membership check per log line, combined with its automatic uniqueness guarantee, turns what would otherwise be an O(n²) deduplication problem into an O(n) pass through the log.
📌 Exam Application
Exam questions often ask you to identify whether a set, list, or hash table (map) is the appropriate structure for a described scenario, expecting you to reference the specific combination of uniqueness, ordering, and key-value association the scenario requires. You may also be asked to compute the result of a union, intersection, or difference between two given small sets.
⚠️ Most Common Sets Mistakes
The most common mistake is using a set when insertion order or duplicate counts actually matter to the problem — a set silently discards both, which can produce subtly wrong results if the problem needed 'how many times did X appear' rather than just 'did X appear at all.' Another frequent error is assuming a set preserves any particular order when iterating over it — most set implementations make no ordering guarantee at all, and code that depends on iteration order behaving consistently is relying on an implementation detail, not a guaranteed property.
✓ Quick Self-Test
Can you compute the union, intersection, and difference of two small sets by hand? Can you explain, in one sentence, the key difference between a set and a hash table, given that both are typically implemented the same way internally?
Next Lesson
ACID Properties
→
← All Data Structures Lessons