Dictionaries & Sets — Hashing as the Shared Engine

Dicts and sets are Python's hash-based collections, and they share one engine: hashing, which buys near-constant-time lookup. A dict maps keys to values; a set is a dict with keys but no values. Understand hashing once and both their power and their constraints (why keys must be hashable, why sets have no order) follow directly.

This builds on Sequences — especially the tuple-hashability discussion — and on list membership being O(n). Every output below was produced by running the code.

Table of Contents

1. The core idea: hashing
2. Dictionaries: the mapping
3. Safe access: get and setdefault
4. Iterating and comprehensions
5. What can be a key: hashability
6. Merging dicts
7. Sets: membership and algebra
8. The killer feature: O(1) membership
9. frozenset and deduplication
10. Mental-model summary

1. The core idea: hashing

A hash function turns an object into an integer. A hash table uses that integer to decide where to store the object, so finding it later is a direct jump rather than a search.

Output (illustrative — the string hash changes every run):

6479512370364792116
42
-3550055125485641917

Analysis. Hashing maps an object to a bucket index. To look up a key, Python hashes it, jumps to the bucket, and checks — O(1) on average, regardless of how many items are stored. This is the whole reason dicts and sets are fast. (Run the block yourself: hash(42) is always 42, but the string's hash differs each run — Python randomizes string hashing for security.) The catch: only immutable (hashable) objects can be keys.

Intuition. Mechanism. The hash of a key determines which bucket it goes in. Lookup re-hashes the key, jumps straight to that bucket, and checks — so cost is roughly constant no matter how many entries exist. This only works if a key's hash never changes while it's stored; a key whose value (and thus hash) could change mid-storage would become unfindable. That's why keys must be immutable, and Python enforces it up front.

Concrete bite. The enforcement is a hard error, not a silent misfile:

Traceback (most recent call last):
  File "/w/main.py", line 2, in <module>
    d[[1, 2]] = "x"      # a list cannot be a key
    ~^^^^^^^^
TypeError: unhashable type: 'list'

Python refuses a list key rather than let you create an entry that could later be lost in the wrong bucket. (Contrast a tuple key, which is allowed — it can't change.)

2. Dictionaries: the mapping

A dict maps keys → values. Access, insertion, and deletion by key are all O(1) average.

Output:

1
{'a': 1, 'b': 2, 'c': 3}
['a', 'b', 'c']
[1, 2, 3]
[('a', 1), ('b', 2), ('c', 3)]

Insertion order is preserved (Python 3.7+):

Output:

['z', 'a', 'm']

Analysis. d[key] retrieves a value; d[key] = v inserts or overwrites. .keys(), .values(), .items() are live views onto the dict (they reflect later changes and are iterable), and .items() yields (key, value) tuples — perfect for unpacking (Sequences §8). Since Python 3.7, iteration yields keys in insertion order (z, a, m, not sorted). Sets still do not guarantee order.

Intuition. Mechanism. A dict is a lookup table keyed by hash (§1), so d[key] is O(1) average whether the dict holds ten or ten million entries. The views aren't snapshots — they're live, tied to the dict.

Concrete bite. Because views are live, mutating a dict's size while iterating raises mid-loop:

Traceback (most recent call last):
  File "/w/main.py", line 2, in <module>
    for k in d:
             ^
RuntimeError: dictionary changed size during iteration

Adding keys during iteration would invalidate the view's cursor, so Python stops you. (Iterate over list(d) if you must add/remove while looping.)

3. Safe access: get and setdefault

Indexing a missing key raises KeyError. get handles absence gracefully.

Output:

0
{'b': 1, 'a': 3, 'n': 2}

Analysis. d.get(key, default) returns the value if present, else default (default None) — never raises. The counting idiom counts.get(ch, 0) + 1 reads as "current count or zero, plus one," the canonical way to tally without pre-initializing every key. Note the result is in insertion order of first appearance: b, a, n. (collections.Counter and defaultdict automate this — see the stdlib tour.)

Intuition. Mechanism. d[key] demands the key exist and raises KeyError if not. d.get(key, default) instead returns default on a miss — folding "check if present, else use a fallback" into one expression with no branch.

Concrete bite. Without get, the natural first attempt at counting crashes on the very first character:

Traceback (most recent call last):
  File "/w/main.py", line 3, in <module>
    counts[ch] = counts[ch] + 1   # read before the key exists
                 ~~~~~~^^^^
KeyError: 'b'

counts['b'] is read before it's ever written. counts.get(ch, 0) + 1 supplies the implicit zero, so the first occurrence starts at one cleanly.

4. Iterating and comprehensions

Iterating a dict yields its keys. To build dicts concisely, use a dict comprehension (the full toolkit is the next chapter).

Output:

a 1
b 2
c 3
{1: 1, 2: 4, 3: 9, 4: 16}

Analysis. for k in d walks the keys (use d.items() for pairs). A dict comprehension {key_expr: val_expr for ... in ...} builds a dict in one expression — the mapping analog of a list comprehension. You can filter too: {k: v for k, v in d.items() if v > 1}.

Intuition. Mechanism. Iterating a dict yields its keys only — so for k in d and for k in d.keys() are the same. To loop over pairs you must ask explicitly with .items(), which yields unpackable (key, value) tuples.

Concrete bite. Assuming iteration gives pairs fails loudly with non-string keys:

Traceback (most recent call last):
  File "/w/main.py", line 2, in <module>
    for k, v in d:        # iterates int KEYS, then tries to unpack each
        ^^^^
TypeError: cannot unpack non-iterable int object

for k in d hands you 1, then 2 — single keys, not pairs — so unpacking into k, v blows up. The fix is for k, v in d.items(). (Insidiously, with 2-character string keys this accidentally "works" by splitting the key into two chars — masking the bug until your keys change.)

5. What can be a key: hashability

Keys must be hashable, which in practice means immutable. Lists and dicts cannot be keys; numbers, strings, and tuples (of hashables) can.

Output:

TypeError: unhashable type: 'list'

Analysis. A list's contents can change, which would change its hash and break the table, so Python forbids lists as keys (and as set members). Tuples are allowed — if everything inside them is also hashable. This connects straight to the object model: hashability ≈ immutability.

Intuition. Mechanism. Hashability is the storage contract from §1: a key's hash must stay constant for its whole time in the table. Immutable objects satisfy this trivially; mutable ones can't, so they're rejected. Hashability of a container is recursive — a tuple is hashable only if everything inside it is.

Concrete bite. This is exactly why tuples beat lists for composite keys:

{(2, 3): 'wall'}
Traceback (most recent call last):
  File "/w/main.py", line 4, in <module>
    grid[[2, 3]] = "wall"     # list key - error
    ~~~~^^^^^^^^
TypeError: unhashable type: 'list'

grid[(row, col)] = value is the canonical 2D-grid idiom precisely because tuples are hashable; lists can't fill that role. Convert with tuple([2, 3]) when you have a list.

6. Merging dicts

Output:

{'a': 9, 'b': 2}

Analysis. {**d1, **d2} builds a new dict by unpacking both; on key collisions, the later source wins (a becomes 9, not 1). Python 3.9+ also offers d1 | d2 (same semantics) and d1 |= d2 (in-place update). d1.update(d2) mutates d1 with the same last-wins rule.

Intuition. Mechanism. Merging walks the sources left to right, writing each key — so when a key appears in more than one source, the last write wins. {**a, **b} and a | b build a new dict; a.update(b) and a |= b mutate a in place.

Concrete bite. Order is the whole game, and getting it backwards silently discards user input:

{'color': 'blue', 'size': 'M'}
{'color': 'red', 'size': 'M'}

Put the lower-priority source first and the override last; reverse it and your carefully chosen user settings vanish under the defaults.

7. Sets: membership and algebra

A set is an unordered collection of unique, hashable elements. Think of it as a dict with keys and no values. Its strengths are fast membership testing and mathematical set operations.

Output:

{1, 2, 3, 4, 5, 6}
{3, 4}
{1, 2}
{1, 2, 5, 6}

Analysis. Sets support the algebra you'd expect: union (|), intersection (&), difference (-), symmetric difference (^). Each returns a new set. Elements are unique (duplicates collapse) and unordered (no indexing). (The display order above happens to look sorted for these small integers, but set order is not guaranteed — never rely on it.)

Intuition. Mechanism. A set is a hash table storing only keys — so elements are inherently unique (a duplicate hashes to an occupied slot and is dropped) and unordered (storage position follows the hash, not insertion).

Concrete bite. Sets buy uniqueness and one-expression set logic, at the cost of order and indexing — and forgetting the latter raises:

Traceback (most recent call last):
  File "/w/main.py", line 2, in <module>
    print(s[0])            # sets are not subscriptable
          ~^^^
TypeError: 'set' object is not subscriptable

There's no "first element" of a set — position is meaningless. In exchange, "what's common to both?" is a single &:

{3, 4}

8. The killer feature: O(1) membership

The most important practical reason to use a set: x in set is O(1), versus x in list is O(n).

Output:

True
True

Analysis. Both return True, but the list scans element by element (worst case, the whole million) while the set hashes the value and jumps straight to its bucket. For repeated membership tests, this is the difference between a fast program and a slow one — and in a loop it's the difference between O(n) and O(n²).

Intuition. Mechanism. x in list has no structure to exploit, so it compares against each element in turn — up to n checks. x in set hashes x once and jumps to its bucket — ~one check, independent of size.

Concrete bite. Put numbers on it. Testing membership in a million-item list inside a loop over another million items is ~10¹² operations — a program that looks hung. Here stream is your input of n items:

seen = []
for x in stream:        # n items
    if x in seen:       # O(n) scan each time
        handle_dupe(x)
    seen.append(x)
# total ~ O(n^2): fine at n=1,000; effectively frozen at n=1,000,000

Change seen = [] to seen = set() and each in becomes O(1), turning the whole loop into O(n) — instant.

9. frozenset and deduplication

A frozenset is an immutable set — hashable, so it can be a dict key or an element of another set.

Output:

ok

Deduplication — two idioms:

Output:

[1, 2, 3]
[1, 2, 3]

Analysis. A regular set is mutable and therefore unhashable; frozenset is the immutable version you can nest or use as a key. For deduplication, set(x) is fastest but unordered; list(dict.fromkeys(x)) removes duplicates while preserving insertion order, leveraging the dict order guarantee from §2.

Intuition. Mechanism. A regular set is mutable, hence unhashable, hence can't be a key or a member of another set; frozenset is the immutable counterpart that can. For dedup, set(x) collapses duplicates by hashing but discards order; dict.fromkeys(x) uses the keys-are-unique-and-ordered property (§2) to dedup and keep first-seen order.

Concrete bite. The choice matters when order carries meaning — set() will scramble it:

Output (illustrative — the set() line's order is arbitrary and may differ for you):

['b', 'a', 'c']
['c', 'a', 'b']

Dedup a playlist or a log with set() and you may shuffle it; dict.fromkeys preserves the original sequence.

10. Mental-model summary

Gotcha checklist

Your Turn

Before you move on, check your understanding with the coach — explain the idea, apply it, weigh the trade-offs, then defend your reasoning.