Sets and dictionaries
Sets and dictionaries: hash-based collections for uniqueness, fast lookup, mapping keys to values, with syntax, operations, and exam-ready examples.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Engineers use sets and dictionaries to manage data efficiently: sets to keep only unique items and test membership quickly, dictionaries to map keys (like IDs, sensor names) to values (like readings). They underpin fast algorithms, configuration handling, counting, indexing, and de-duplication in real-world Python projects.
Key ideas
- Hashable (object) — Definition: An object is hashable if it has a hash value that does not change during its lifetime and can be compared to other objects; in Python this means implementing a stable
__hash__and compatible__eq__. Built-in hashable types includeint,float,str,tuple(if all its elements are hashable), andfrozenset. Unhashable (mutable) types includelist,dict, andset. - frozenset — Definition: An immutable set; once created, its elements cannot change. It is itself hashable if all its elements are hashable, so it can be used as a key in a dictionary or as an element of another set.
- Dictionary (dict) — Definition: A dictionary is a mapping from unique, hashable keys to values. Assumptions: keys must be hashable and unique; values can be any type. Since Python 3.7, dictionaries preserve insertion order (the order in which keys were first inserted). Operations for key lookup, insertion, and deletion have average-case O(1) time complexity. In the worst case, these can degrade to O(n).
- Uniqueness constraint — For sets: duplicates collapse to a single element. For dictionaries: inserting a value with an existing key replaces the old value.
- Unordered vs ordered — Sets are unordered and do not preserve insertion order; therefore indexing like
s[0]is invalid. Dictionaries preserve insertion order for keys, but they are still conceptually mappings; random access by numeric index is not allowed. - Set operations — Precise definitions for two sets A and B:
- Union:
A ∪ B = { x | x ∈ A or x ∈ B } - Intersection:
A ∩ B = { x | x ∈ A and x ∈ B } - Difference:
A − B = { x | x ∈ A and x ∉ B } - Symmetric difference:
A Δ B = { x | (x ∈ A) xor (x ∈ B) }Python provides operators|,&,-,^implementing these exactly.
- Union:
- Subset and superset — For sets A and B:
- Subset:
A ⊆ Bif every element of A is also in B. - Proper subset:
A ⊂ BifA ⊆ BandA ≠ B. - Similarly, superset
A ⊇ Band proper supersetA ⊃ B. Python provides methods:A.issubset(B),A.issuperset(B), and operators<=,<,>=,>.
- Subset:
- Dictionary entries (items) — Each key-value pair is called an item.
dict.items()returns a dynamic view of items; changes in the dict reflect in the view. - Key lookup semantics —
d[k]raisesKeyErrorifkis absent;d.get(k, default)returnsdefault(orNoneif not given) instead of raising an error. - Mutability — Sets and dictionaries are mutable: you can add/remove elements/items.
frozensetis immutable;tupleis immutable but only hashable if all its elements are hashable. - Equality — Sets: equality is by element equality ignoring order. Dicts: equality is by key set and corresponding value equality.
- Comprehensions — Compact syntax to build collections:
- Set comprehension:
{expr for var in iterable if condition} - Dictionary comprehension:
{key_expr: value_expr for var in iterable if condition}
- Set comprehension:
- Iteration semantics — Iterating a set visits elements in an arbitrary order; do not assume any order. Iterating a dict yields keys in insertion order. Iterating
dict.items()yields(key, value)pairs in insertion order. - Common derivation/trace asked in exams — “Show how duplicates are removed using sets and why time complexity is improved compared to lists.”
Step-by-step derivation:
- Given list L of length n, checking membership with
x in Lis O(n) worst- and average-case (linear scan). - Converting to set S = set(L) costs O(n) average, builds a hash table of unique elements (duplicates collapsed during insertion).
- Now membership
x in Sis O(1) average due to hashing (constant expected time per lookup), so repeated membership tests across m queries cost O(m) average versus O(m·n) for list.
- Given list L of length n, checking membership with
- Diagram to draw (if asked “illustrate hashing for dict”) — Draw a rectangle labeled “Hash table (array of buckets)”. Inside, draw numbered slots 0..N−1. From a sample key (e.g., key="ENGR101"), show an arrow: key → hash(key) → index = hash(key) mod N → slot. At the slot, draw a small list/chain or open-address probe sequence showing the stored (key, value). Label: hash function, index computation, collision handling (probing or chaining), and that equality is checked to confirm the correct key after a collision.
Formulas
- Empty set:
set()(not{}which is an empty dict) - Set constructor:
set(iterable) - Add/remove:
s.add(x),s.update(iterable),s.remove(x)(KeyError if absent),s.discard(x)(no error if absent),s.pop()(removes and returns an arbitrary element),s.clear() - Set relations and queries:
len(s),x in s,x not in s,s.issubset(t),s.issuperset(t),s.isdisjoint(t) - Set operations (operators):
s | t,s & t,s - t,s ^ t - Set operations (methods):
s.union(t, ...),s.intersection(t, ...),s.difference(t, ...),s.symmetric_difference(t)and their in-place formss |= t,s &= t,s -= t,s ^= t - frozenset:
fs = frozenset(iterable) - Dict literals:
{'a': 1, 'b': 2} - Empty dict:
{}; constructor:dict()ordict(a=1, b=2) - Dict comprehension:
{k: v for k, v in iterable} - Access:
d[k](KeyError if absent),d.get(k, default) - Insert/update:
d[k] = v,d.update(other_or_kwargs) - Remove:
d.pop(k)(KeyError if absent),d.pop(k, default)(returns default if absent),d.popitem()(removes and returns the last inserted (key, value) pair),del d[k](KeyError if absent),d.clear() - Views:
d.keys(),d.values(),d.items() - Safe insert-if-absent:
d.setdefault(k, default) - Iteration:
for k in d:,for k, v in d.items():
Worked examples
Example 1: Remove duplicates and perform set algebra Complete Python program:
# Program: Read two lines of integers, build sets, and print union, intersection, difference, symmetric difference.
# Input format (two lines):
# 10 20 20 30 40
# 30 40 50
# Read two lines and split into ints
A = set(map(int, input().split()))
B = set(map(int, input().split()))
print("A:", A)
print("B:", B)
print("Union:", A | B)
print("Intersection:", A & B)
print("A-B:", A - B)
print("B-A:", B - A)
print("Symmetric difference:", A ^ B)
print("Is A subset of B?", A <= B)
print("Are A and B disjoint?", A.isdisjoint(B))
Sample input:
10 20 20 30 40
30 40 50
Exact output (order of set elements may differ because sets are unordered, but structure will match):
A: {40, 10, 20, 30}
B: {40, 50, 30}
Union: {50, 20, 40, 10, 30}
Intersection: {40, 30}
A-B: {10, 20}
B-A: {50}
Symmetric difference: {50, 10, 20}
Is A subset of B? False
Are A and B disjoint? False
Note: Your printed sets may show elements in a different order, which is correct.
Example 2: Word frequency using dictionary (case-insensitive, punctuation-stripped) Complete Python program:
# Program: Count word frequencies in a single input line, case-insensitive.
# Input: a single line of text.
# Output: each word with its count in insertion order of first appearance.
import string
text = input().strip()
# Normalize: lowercase, remove punctuation
translator = str.maketrans('', '', string.punctuation)
words = text.lower().translate(translator).split()
freq = {}
for w in words:
# Insert or increment using get
freq[w] = freq.get(w, 0) + 1
# Print results in insertion order of first appearance of each word
for w, c in freq.items():
print(f"{w} {c}")
Sample input:
To be, or not to be: that is the question.
Exact output:
to 2
be 2
or 1
not 1
that 1
is 1
the 1
question 1
Example 3: Reverse a mapping and use frozenset as a key Complete Python program:
# Program: Given student -> branch mapping, make branch -> set of students using dict and set.
# Then, construct an immutable key (frozenset of top scorers) and store a summary in another dict.
# Input format:
# First line: n (number of students)
# Next n lines: name branch score
# Example:
# 5
# Ayan ECE 8.7
# Beena CSE 9.1
# Charan ME 8.7
# Divya CSE 9.5
# Ekta ECE 8.3
n = int(input())
by_branch = {}
by_name = {}
for _ in range(n):
name, branch, score_s = input().split()
score = float(score_s)
by_name[name] = (branch, score) # dict: name -> (branch, score)
# build branch -> set of names
s = by_branch.setdefault(branch, set())
s.add(name)
# find max score and the set of toppers (names with that score)
max_score = max(sc for (_, sc) in by_name.values()) if by_name else 0.0
toppers = {name for name, (_, sc) in by_name.items() if sc == max_score}
# use frozenset as a key in a summary dict
summary = {frozenset(toppers): ("max_score", max_score)}
print("Branches:", by_branch)
print("Toppers:", toppers)
print("Summary:", summary)
Sample input:
5
Ayan ECE 8.7
Beena CSE 9.1
Charan ME 8.7
Divya CSE 9.5
Ekta ECE 8.3
Exact output (set element order may vary; dicts preserve insertion order of keys):
Branches: {'ECE': {'Ekta', 'Ayan'}, 'CSE': {'Divya', 'Beena'}, 'ME': {'Charan'}}
Toppers: {'Divya'}
Summary: {frozenset({'Divya'}): ('max_score', 9.5)}
Common mistakes
- Assuming sets or dicts are sorted. Sets are unordered; dicts preserve insertion order (not sorted order). Do not index sets (
s[0]is an error). - Using unhashable types as set elements or dict keys, e.g.,
set([[1, 2]])or{[1, 2]: 'x'}causeTypeError. Use tuples instead of lists when you need to hash a sequence. - Forgetting
KeyError: usingd[k]for possibly-missing keys. Preferd.get(k)ord.setdefault(k, default)or checkif k in d:. - Confusing
removeanddiscardon sets.removeraisesKeyErrorif the element is absent;discarddoes nothing if absent. - Expecting a stable order in printed sets and then writing exact-order-dependent test output. For exams, write that set output order may vary.
- Misusing
updateon dict thinking it appends items like a list; it merges another mapping, overwriting existing keys. - Expecting
1andTrueto be distinct dict keys: bool is a subclass of int (True == 1andhash(True) == hash(1)), so they collide and the later assignment overwrites the former. - Assuming
popitem()removes a random item. In current Python, it removes the last inserted item (LIFO), not arbitrary. - Writing a tuple with one element as
(1)which is just1. Must write(1,)to get a 1-tuple; relevant when using tuples as dict keys. - Forgetting that equality of sets/dicts compares contents, not identity; two separately created dicts with same items are equal (
==) but not the same object (is).
For your exam
- Short notes: Properties of sets (uniqueness, unordered), dictionary order guarantee, difference between
removeanddiscard, views (keys,values,items). - Programs: Remove duplicates, set algebra; frequency count with dict; reverse mapping (value to set of keys) using
setdefault; comprehension-based construction. - Diagram: Hash table for dict with labeled hash → index → collision resolution → equality check.
- Reasoning/derivation: Time-complexity advantage of sets/dicts vs lists; why keys must be hashable; immutability and hash-stability link.
- Full-marks answers include: correct syntax, explanation of behavior (errors/exceptions where relevant), mention of order properties (set unordered, dict insertion order), and example outputs that acknowledge unordered display for sets.
Quick check
- Which statement correctly creates an empty set, and which creates an empty dict?
- What is the difference between
s.remove(x)ands.discard(x)for a sets? - In Python 3.7+, does a dict preserve insertion order? What does
popitem()remove?
Answers: 1) set() is an empty set; {} is an empty dict. 2) remove raises KeyError if x is absent; discard does nothing if x is absent. 3) Yes, dicts preserve insertion order; popitem() removes the last inserted item (LIFO).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?