Dictionaries and Sets: Lookup That Doesn't Slow Down

11.1The problem this solves

Week 10 left us with an uncomfortable fact: x in my_list is O(n). Put that inside a loop over m queries and you have O(n × m) — the shape that turns a working prototype into a frozen laptop.

known_emails = list_of_100000_addresses
new_signups  = list_of_10000_addresses

duplicates = []
for address in new_signups:            # 10 000 times ...
    if address in known_emails:        # ... a scan of 100 000
        duplicates.append(address)

A billion comparisons for a job that sounds like nothing. This week's tool reduces it to about a hundred and ten thousand — roughly ten thousand times less work — by changing one word.

11.2Sets: a bag with instant membership

A set is an unordered collection with no duplicates, written with curly braces.

enrolled = {"Ada", "Bilal", "Cem"}

enrolled.add("Dilek")
enrolled.add("Ada")            # already there — no effect, no error

print("Cem" in enrolled)       # True   — and this is O(1)
print(len(enrolled))           # 4

a = {1, 2, 3}
b = {3, 4}
print(a & b, a | b, a - b)     # {3} {1,2,3,4} {1,2}

The last line — intersection, union, difference — often replaces an entire nested loop with one character.

11.3Dictionaries: a label on every value

grades = {"Ada": 88, "Bilal": 72, "Cem": 91}

print(grades["Ada"])              # 88     — O(1)
grades["Dilek"] = 67              # add    — O(1)
print("Ece" in grades)            # False  — O(1), checks the keys
print(grades.get("Ece", 0))       # 0      — a safe default

for name, score in grades.items():
    print(f"{name}: {score}")

A dictionary maps keys to values. Keys must be unchangeable things — text, numbers, tuples — and each appears once. Looking one up costs the same whether the dictionary holds ten entries or ten million.

11.4Counting, done properly

Tallying how often each thing occurs is the single most common use of a dictionary, and it replaces a lot of clumsy list code. Three ways, worst to best:

text = "the quick brown fox jumps over the lazy dog the end"

counts = {}
for word in text.split():
    counts[word] = counts.get(word, 0) + 1     # O(1) per word

print(counts["the"])       # 3

One pass over n words, constant work each: O(n) for the whole tally. The list-based equivalent — searching a list of seen words each time — is O(n²).

get(word, 0) is the idiom to remember: "the current count, or nought if we have not seen this word before". A close cousin, setdefault, does the same job when the value is a list you want to grow:

students = [("maths", "Ada"), ("history", "Bilal"), ("maths", "Cem")]

by_subject = {}
for subject, name in students:
    by_subject.setdefault(subject, []).append(name)   # make the list if absent, then append

print(by_subject)

And when all you want is a count, the standard library hands it to you outright. Counter is a dictionary that already knows how to tally:

from collections import Counter

text = "the quick brown fox jumps over the lazy dog the end"

counts = Counter(text.split())     # one pass, O(n), written in C

print(counts["the"])               # 3
print(counts["missing"])           # 0   — never a KeyError
print(counts.most_common(2))       # [('the', 3), ('quick', 1)]

Same class as the hand-written loop — O(n) — but a smaller constant, because the counting happens in C, and most_common saves you a sort. This is the same space-for-time trade you met with the anagram counter in week 9.

11.5How can lookup not depend on size?

It feels like a trick. Here is the idea, without any mathematics.

Imagine a cloakroom with 1 000 numbered hooks. Instead of searching for a free hook, the attendant computes one from your name: add up the letters, divide by 1 000, take the remainder. "Bilal" always gives the same number — say 417 — so your coat goes on hook 417 and is found on hook 417 later. No searching, ever. The computation is called a hash, and it takes the same time regardless of how many coats are already hanging.

Two names can compute to the same hook — a collision. The structure keeps a small chain there and checks it, which is why the honest statement is "O(1) on average". With a good hash function, collisions are rare enough that this holds up in practice, and Python's is very good.

11.6Inside the table: buckets and collisions

Let us make the cloakroom concrete and small enough to trace by hand. Build a tiny table of eight buckets and drop five integers into it, sending each number key to bucket key % 8. Integers are perfect for a trace because in Python hash(n) == n for a small integer, so the arithmetic is reproducible.

size = 8
buckets = [[] for _ in range(size)]     # eight empty chains

for key in [10, 18, 3, 26, 7]:
    home = key % size                   # the "hook number"
    buckets[home].append(key)
    print(f"{key:>3}  ->  bucket {home}")

print(buckets)

Work the arithmetic yourself: 10 % 8 = 2, 18 % 8 = 2, 3 % 8 = 3, 26 % 8 = 2, 7 % 8 = 7. Three keys — 10, 18 and 26 — all landed in bucket 2. That is a collision, and the bucket holds a short chain of them.

Now watch a lookup. To find 26 the table computes 26 % 8 = 2, goes straight to bucket 2, and walks its tiny chain — three items — until it matches. To decide that 99 is absent it computes 99 % 8 = 3, looks in bucket 3, finds only [3], and stops. Neither lookup ever touched the other buckets. That is the whole secret: the hash jumps you to a tiny neighbourhood, and only the neighbourhood is searched.

Two things keep the neighbourhoods tiny. First, a good hash function scatters keys evenly, so chains stay short. Second, when the table starts to fill up Python quietly builds a bigger one and re-files everything — this is called resizing, and it is why a set needs spare room and therefore extra memory. If chains were ever allowed to grow long, lookup would slide back towards O(n); the average-case O(1) promise depends on keeping them short.

11.7What each operation costs

Keep this table beside you when you reach for a container. "Average" is the honest word: a pathological run of collisions can degrade any single operation, but in practice Python holds these costs.

Read the first row downwards: it is the entire reason this week exists. Everything a set and dictionary give you is bought with the memory and the lost order in the bottom rows — a trade that is almost always worth it once you are searching inside a loop.

11.8The measurement

import time

for n in [10000, 100000, 1000000]:
    as_list = list(range(n))
    as_set = set(as_list)
    target = -1                     # missing: the worst case

    start = time.perf_counter()
    for _ in range(100):
        target in as_list
    t_list = (time.perf_counter() - start) / 100

    start = time.perf_counter()
    for _ in range(100):
        target in as_set
    t_set = (time.perf_counter() - start) / 100

    print(f"n={n:>8}  list {t_list*1e6:10.2f} µs   set {t_set*1e6:6.2f} µs   ratio {t_list/t_set:,.0f}x")

The list column multiplies by ten every row. The set column does not move at all — and so the ratio column multiplies by ten instead. This is what a difference in class looks like when you see it directly: not "faster", but "stops caring how much data there is".

Now the disaster from §11.1, repaired:

known_set = set(known_emails)          # O(n), paid once

duplicates = [a for a in new_signups if a in known_set]   # O(m)

Total cost O(n + m) instead of O(n × m). On the numbers from §11.1 that is about 110 000 operations instead of a billion — and the code is shorter.

11.9Choosing the container

11.10Common mistakes, and when a set is the wrong answer

A set is a hammer that makes a lot of problems look like nails. Four situations where reaching for one is a genuine error:

• Duplicates carry meaning. set(votes) to "clean up" a list of votes silently throws away every repeat — and repeats were the whole point. A set answers "which values appear?", never "how many times?".
• Order matters. A leaderboard, a queue, a log, anything the user reads top to bottom: a set scrambles it. If you need both fast membership and order, keep the list and build a set alongside it for the lookups.
• You only look once or twice. Building a set is a full O(n) pass. For a single membership test, x in my_list is simpler and no slower. The set only pays off when the build cost is spread over many lookups.
• You need order questions. Nearest value, next larger, everything between two dates — a hash table cannot answer any of these. That is next week's subject.

And two mistakes that produce wrong answers rather than slow ones:

seen = set()
seen.add([1, 2])            # TypeError: unhashable type: 'list'

scores = {"Ada": 88}
scores["Ada"] = 91          # not a new entry — it overwrites 88
print(len(scores))          # 1, not 2: keys are unique

A list cannot go into a set or be a dictionary key, because it can change and so its hash would move — Python refuses outright with TypeError. Use a tuple when you need a compound key. And assigning to an existing key replaces its value; it does not add a second entry. Both of these surprise people exactly once.

11.11Try it yourself

common_slow = []
for x in a:                       # O(n × m)
    if x in b:
        common_slow.append(x)

common_fast = list(set(a) & set(b))    # O(n + m)

print(sorted(common_slow) == sorted(common_fast))

from collections import Counter
print(Counter(rolls).most_common(1))      # e.g. [(4, 167012)]

11.12Self-check

11.13Homework

11.14Words from this week