Dictionaries and Sets: Faster Lookups

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 fast average 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 hashable values — ordinary text and numbers, or tuples whose components are all hashable — and each key appears once. Lookup is O(1) on average in the number of stored keys, assuming hashing and equality checks that each take constant time; a worst-case lookup can be O(n).

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 costs O(nu), where u is the number of distinct words: quadratic when u grows with n, but linear in n if u stays fixed.

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, while ranking with most_common has its own cost; requesting all ranks may require sorting the distinct counts. 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. The computation is called a hash. It chooses where to begin checking, avoiding a scan of unrelated keys. Computing a hash can depend on key length, even when it does not depend on the number of stored keys.

Two names can compute to the same hook — a collision. The structure resolves collisions and checks key equality, which is why the honest statement is "O(1) on average" under ordinary hashing assumptions. The chained buckets below are a teaching model; Python dictionaries and sets use a different probing layout internally. 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. For these small nonnegative integer examples, hash(n) == n, so the arithmetic is reproducible. This is not a rule for every integer.

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. The trade includes additional memory and unique keys. Dictionaries preserve insertion order, including when a key's value is updated; sets provide no insertion-order or sorted-order guarantee. Choose according to the required output.

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 avoids preparation and may be faster; both complete strategies have O(n) worst-case work in the usual model. 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 of hashable components 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.13Optional Studio Extension

11.14Words from this week