Skip to content
Hello Python
7/8

Dictionaries & Sets

Topic 7 of 8, with 4 concept checks. Hashing, membership, and merging

Model lookup, membership, and uniqueness

Lookup and membership

Use dictionaries when a key should locate a value and sets when only membership matters, while keeping hashability, missing keys, and mutation during iteration visible.

Core lesson 01

Hashable = stable hash value used for fast lookup. Mutable types (list, dict, set) aren't hashable and can't be dict keys.

A dict is backed by a hash table: each key's hash() determines which internal bucket it lives in, giving O(1) average lookup instead of scanning every entry. This only works if a key's hash never changes while it's stored — otherwise the dict would be searching the wrong bucket after a mutation. That's why Python only allows immutable (or user-defined, deliberately-hashable) types as keys.

Python example
d = {(0, 0): "origin", "name": "Ada"}
print(d[(0, 0)])          # origin

try:
    bad = {[1, 2]: "x"}
except TypeError as e:
    print("TypeError:", e)   # unhashable type: 'list'

What to remember

Why must dictionary keys be hashable?

Common footguns

  • Trying to use a list as a dict key or set member because it 'looks like' a tuple — convert to tuple() first if you need this.
key "age" -> hash() -> 93458123 -> bucket[3] -> ("age", 30)
O(1) average lookup vs a list's O(n) linear scan

Core lesson 02

dict[key] raises KeyError if missing. dict.get(key, default) returns default (None if unspecified) instead of raising.

Both retrieve a value by key, but they express different intent. `dict[key]` says 'this key should be here — error loudly if it's not', useful when a missing key indicates a real bug. `.get(key, default)` says 'this key might legitimately be absent — give me a sensible fallback', which is usually what you want when handling optional or user-provided data.

Python example
user = {"name": "Ada"}
print(user.get("age", 0))      # 0 -- no KeyError
try:
    print(user["age"])
except KeyError as e:
    print("KeyError:", e)

What to remember

What happens with dict[key] vs dict.get(key) when the key is missing?

Common footguns

  • Using `dict[key]` for genuinely optional data and having to wrap every access in try/except instead of just using .get().

Core lesson 03

Sets: unordered, unique, O(1) average membership check. Lists: ordered, allow duplicates, O(n) membership check.

A set is, like a dict's keys, backed by a hash table — so checking `x in my_set` hashes `x` and looks directly in the right bucket, O(1) on average regardless of set size. A list has no such structure, so `x in my_list` must scan elements one by one until it finds a match or reaches the end, O(n). For large collections checked repeatedly, this difference is significant.

Python example
import time
big_list = list(range(200000))
big_set = set(big_list)

print(199999 in big_set)   # near-instant
print(199999 in big_list)  # measurably slower for large n

What to remember

How is a set different from a list for membership testing?

Common footguns

  • Reaching for a list when you actually need fast membership checks or deduplication — sets exist exactly for that.

Core lesson 04

3.9+: merged = d1 | d2. Earlier: merged = {**d1, **d2} or d1.update(d2).

Python 3.9 added `|` (and `|=`) as a dedicated dict-merge operator, mirroring set union syntax and making merge intent explicit. Before that, the common idiom was double-star unpacking two dicts into a new literal, or calling `.update()` to merge one dict into another in place. In all cases, keys from the right-hand/argument dict win on conflict.

Python example
d1 = {"a": 1, "b": 2}
d2 = {"b": 20, "c": 3}

print(d1 | d2)             # {'a': 1, 'b': 20, 'c': 3}  (3.9+)
print({**d1, **d2})        # same result, any version

d1.update(d2)              # mutates d1 in place
print(d1)

What to remember

How do you merge two dicts in Python 3.9+, and how was it done before?

Common footguns

  • Using `.update()` when you actually wanted a new merged dict without touching the original — .update() mutates in place.

Python lab

Browser Python lab

Runtime · idle

Python loads on your first run. Your code stays in this browser.

Best practices

  • Use .get() or dict.setdefault() instead of `if key in dict` followed by indexing (avoids a double lookup).
  • Use collections.defaultdict when building up grouped or counted data.
  • Use sets for membership testing and deduplication when order doesn't matter.
  • Use collections.Counter for frequency counting instead of manual dict-counting loops.

References

Python Docs — Mapping Types (dict)Real Python — Dictionaries in Python

Apply the concept in Interview practice

Two SumeasyLeetCode #1 · O(n) time

Use a dict mapping value→index built in a single pass, checking for the needed complement before inserting.

Open problem
Group AnagramsmediumLeetCode #49 · O(n·k log k) time

Key a dict by the sorted-tuple of each word's letters, appending each original word to its group.

Open problem
Top K Frequent ElementsmediumLeetCode #347 · O(n log k) time

Count with Counter, then use a heap (heapq.nlargest) or bucket sort by frequency to get the top k.

Open problem
Contains DuplicateeasyLeetCode #217 · O(n) time, O(n) space

Add elements to a set while scanning; if an element is already in the set, a duplicate exists.

Open problem
Intersection of Two ArrayseasyLeetCode #349 · O(n+m) time

Convert both arrays to sets and use set intersection (&) to get the unique common elements.

Open problem

Concept checks

Q01

Why must dictionary keys be hashable?

Q02

What happens with dict[key] vs dict.get(key) when the key is missing?

Q03

How is a set different from a list for membership testing?

Q04

How do you merge two dicts in Python 3.9+, and how was it done before?