Sets & Frozensets
A set is an unordered collection of unique, hashable elements backed by a hash table — giving average O(1) membership tests, one-step de-duplication and fast set algebra.
Learning objectives
- › Explain why set membership is average O(1) and when to prefer a set over a list
- › Deduplicate data and perform union, intersection and difference operations
- › State why set elements must be hashable and what frozenset adds
- › Avoid the empty-set literal trap and mutation-during-iteration errors
Prerequisites
Version notes
- · The `{...}` set literal and set comprehensions exist since Python 2.7 / 3.0 — but there is still no literal for the empty set, so use `set()`.
- · Set iteration order is unspecified and affected by hash randomization for str/bytes (PYTHONHASHSEED); never rely on it.
Simple explanation
What it is. A set is an unordered collection of distinct, hashable elements. Think of it as a dict with keys but no values: each element is stored in a hash table, so a set can answer 'is x in here?' in average constant time and it silently rejects duplicates.
Why it exists. A huge number of problems are really membership or uniqueness questions — 'have I seen this?', 'what do these two collections share?', 'what is unique to one?'. Sets answer them in average O(1) or near-linear time instead of the O(n) or quadratic cost of doing it with lists.
The problem it solves. Sets replace slow `x in list` scans with fast hashed lookups, deduplicate a sequence in a single step, and express relationships between collections directly as operators (| & - ^).
How it works. Each element's __hash__ selects a slot and __eq__ resolves collisions. Because an element's position is derived from its hash, a set has no defined order and every element must be hashable (effectively immutable). frozenset is the immutable, hashable variant — so it can itself be a dict key or an element of another set.
Analogy: A set is a guest list checked at the door: the bouncer hashes your name to see instantly whether you are already inside — no duplicates and no scanning the whole list — but the list itself has no meaningful order.
Common misconceptions
- "{} makes an empty set." — It makes an empty dict. The empty set is set(); the braces literal is reserved for dicts.
- "Sets keep insertion order like dicts do." — They do not; a set is unordered and its iteration order is unspecified.
- "You can put anything into a set." — Only hashable elements; a list, dict, or another (mutable) set cannot be a member — use a tuple or frozenset instead.
- "Sets are always the better choice." — For membership and dedup, yes; but they use more memory, drop order, and cannot hold unhashable items.
Common alternatives
- dict.fromkeys(seq) to deduplicate while PRESERVING insertion order
- frozenset for an immutable, hashable set (dict keys, or a set of sets)
- a sorted list plus bisect when you need ordered membership queries
Code examples
Note: A set has no order, so print(sorted(s)) instead of print(s) whenever you need deterministic output.
Behind the scenes
- ▸A set is essentially a dict with keys but no values: the same open-addressing hash table gives average O(1) add, discard and membership.
- ▸Because an element's slot is derived from hash(element), sets have no meaningful order and every element must be hashable with a stable __hash__.
- ▸`x in a_set` is average O(1) while `x in a_list` is O(n); for repeated lookups over large data, building the set once pays for itself many times over.
- ▸Set algebra is efficient: a & b iterates the smaller operand and probes the larger, so intersection is roughly O(min(len(a), len(b))).
- ▸frozenset computes its hash from its elements, which is precisely why it (unlike a plain set) can be a dict key or an element of another set.
Interview insights
Key definitions
- · Set: an unordered, mutable collection of distinct, hashable elements backed by a hash table.
- · frozenset: the immutable, hashable version of a set — usable as a dict key or as an element of another set.
When would you use a set instead of a list?
Concise answer: When you need fast membership tests, automatic de-duplication, or set algebra (union / intersection / difference). Sets give average O(1) `in`; lists are O(n). Prefer a list when order or duplicates matter.
Detailed answer: The classic win is repeated membership testing: `if x in big_list` inside a loop is O(n) per check, so filtering one collection against another is quadratic; converting to a set makes each check O(1) and the whole job linear. Sets also dedupe in a single call and express relationships directly. The trade-offs are that a set is unordered, uses more memory, and can only hold hashable elements.
Common mistake: Testing membership against a large list in a loop (O(n*m)) when a set would make it O(n).
Follow-ups:
- · Why must set elements be hashable?
- · How do you dedup while keeping order?
What is the difference between a set and a frozenset, and why does it matter?
Concise answer: A set is mutable and therefore unhashable; a frozenset is immutable and hashable. Only a frozenset can be a dict key or an element of another set.
Detailed answer: Both support the read-only operations (membership, union, intersection, difference), but only a set supports add/remove/discard. Because a mutable object cannot have a stable hash, a plain set cannot be hashed — so when you need a 'set of sets' or a set-valued dict key, you reach for frozenset, whose hash is derived from its (fixed) contents.
Common mistake: Trying to use a plain set as a dict key or nesting a set inside another set.
Follow-ups:
- · Can a set contain a list?
- · Which operations does frozenset lack?
How do you create an empty set, and why not {}?
Concise answer: Use set(). `{}` creates an empty dict — the braces literal is claimed by dict, so empty braces default to a dict, not a set.
Detailed answer: A non-empty literal like {1, 2} is unambiguously a set and {'k': 1} is unambiguously a dict, but the empty case {} is defined to be a dict. Writing s = {} then s.add(x) is a frequent beginner bug that fails with AttributeError. set() is always unambiguous.
Common mistake: Writing s = {} and then calling s.add(x), which raises AttributeError.
Follow-ups:
- · What does {1, 2} create?
Knowledge check
What does this print?
s = {3, 1, 2, 2, 1}
print(len(s))What type does `x = {}` create?
What does this print?
a = {1, 2, 3}
b = {2, 3, 4}
print(sorted(a & b))Score: 0/3