37Hashing — buying O(1) with space

In Chapter 36 we made things fast by halving: cut the problem in two, throw away the half that can't hold the answer, and pay O(log n). In this chapter we buy speed a different way — we spend memory to abolish searching altogether. Here's why that matters: almost every slow program is slow for one reason. Somewhere inside a loop it is searching, asking "is this thing in here?" and walking the whole collection to find out. The plan is to turn that walk into a jump. Feed a value to a hash, land on its slot, done. And the whole way through we keep asking the one question that matters — what if you never had to look for a thing at all, because you already knew where it lived? By the end you'll spot any nested loop whose inner half is a lookup, and you'll delete that inner loop on sight. That move collapses O(n²) into O(n) with nothing but a set or a dict. Volume 1 chapter 7 showed how a hash table works inside. Here we learn what to do with one.

01The question that costs O(n) — and the trick that makes it free

Let's start with the most ordinary question a program ever asks: "is X in this collection?" Hand that question to a list and watch what Python is forced to do. It has no choice but to look. It starts at index 0 and compares, element by element, until it finds a match or falls off the end. If the thing isn't there, Python has touched every single element just to tell you so. That pattern is called a linear scan. Its cost grows in lockstep with the size of the list — one comparison per item, n items, so the bill is O(n). We refuse to hand-wave a claim like that, so we counted it:

def scan_ops(haystack, needle):
    ops = 0
    for x in haystack:          # look at one element…
        ops += 1
        if x == needle:         # …compare it…
            return ops          # …stop the instant we match
    return ops                  # a MISS touched everything

for n in (10, 100, 1000, 10000):
    print(n, scan_ops(list(range(n)), -1))   # -1 is absent → worst case
# 10 10 · 100 100 · 1000 1000 · 10000 10000

Read the code line by line: the loop visits elements one at a time, and each visit costs exactly one ops += 1. A match lets the function return early, but a value that isn't there forces the loop to the very end. The output tells the whole story, because the comparison count is exactly n. Double the list and you double the work. A million-item list means a million comparisons just to answer one "is it here?".

Now the trick: a set does not store your values in a row to be walked, and neither does a dict, its key-value sibling. Instead, it computes where the value belongs from the value itself. Feed the value to a hash function, get back a number, and use that number to jump straight to one slot. So membership is hash-the-query, jump, and look. That is one hash, one jump, one compare — a cost that does not grow with n at all. We call that O(1), "constant time." We timed the exact same "is this missing value here?" question against both:

Let's make "jump straight to one slot" concrete, because it can sound like magic the first time. A hash table is really just an array of slots, say 8 of them, numbered 0 through 7. The hash function turns any value into an integer, and the table takes that integer modulo the slot count to pick an index. Try it with a number, since Python hashes small integers to themselves. Storing 41 in an 8-slot table means computing 41 % 8, and the remainder is 1, so it lives in slot 1. Check that yourself: 8 goes into 41 five times, which uses up 40 and leaves 1 over. Looking up 41 later repeats the same arithmetic and lands on the same slot, with no search required. That is the whole jump: the address is computed from the data, not discovered by walking.

import timeit
for n in (1_000, 10_000, 100_000, 1_000_000):
    lst, st = list(range(n)), set(range(n))
    t_list = timeit.timeit(lambda: -1 in lst, number=1000) / 1000
    t_set  = timeit.timeit(lambda: -1 in st,  number=1000) / 1000
    print(n, round(t_list*1e9), "ns   vs", round(t_set*1e9), "ns")
# 1000       6006 ns  vs 65 ns
# 10000     61067 ns  vs 37 ns
# 100000   600563 ns  vs 38 ns
# 1000000 6392406 ns  vs 39 ns   (6.4 MILLISECONDS vs 39 nanoseconds)

Now read the two columns side by side, because they tell two completely different stories. The list column marches: 6 µs, 61 µs, 600 µs, 6.4 ms, a straight multiple of n, exactly as the op-count predicted. The set column does not move: it answers in ~38 nanoseconds whether it holds a thousand items or a million. At a million items the set is roughly 160,000 times faster at the same question. Timings are from this machine and will vary, but the shape is universal — one line climbing, one line flat.

One question, made free. But the real prize isn't one lookup — it's what happens when a lookup was hiding inside a loop →

02The set: membership and dedup in one pass

A set is a bag of unique, hashable values with no order and no duplicates — a dict that kept only the keys. Hashable simply means Python can turn the value into a stable number, and we'll pay that word its full bill later in this chapter. Two everyday jobs fall out of this design for free. The first is membership, because x in some_set is exactly the O(1) jump you just met. The second is deduplication, which means collapsing a collection down to its distinct values. A set physically cannot hold the same value twice, so adding a value that's already there is a no-op:

plays = ["Levels", "Titanium", "Levels", "Wake Me Up", "Titanium", "Levels"]
unique = set(plays)
print(unique)         # {'Wake Me Up', 'Levels', 'Titanium'}  (order not preserved)
print(len(unique))    # 3  — six plays, three distinct songs

That set(plays) call is a single pass: it hashes each of the six songs and drops it into its slot, while repeats land on an occupied slot and simply vanish. One line, O(n), done. Now compare the beginner's instinct: a nested loop that asks "have I seen this before?" by scanning a growing result list. That approach is O(n²) for the exact same answer, because every new item rescans everything kept so far. The set replaces that inner scan with a hash.

It's worth counting what the beginner's version actually costs, because the numbers are the argument. Say every play in a 1,000-song history is distinct, the worst case for that inner scan. The first item scans a result list of length 0, the second scans 1, and the thousandth scans 999. Add the staircase up and you get 0 + 1 + … + 999, which is 499,500 comparisons. The set version hashes each play once, so the same job costs 1,000 hashes — roughly 500 times less work. Notice the check: 499,500 is 1000 × 999 ÷ 2, the every-pair triangle we will meet again in two-sum.

03The tally: counting with a dict (and Counter)

Keep the keys, but give each one a value that counts. That is a tally: a dict from thing to how-many. For each item you jump to its key and bump the number by one — every step O(1), the whole tally O(n). The idiom uses .get(key, 0), which reads "the current count, or 0 if we've never seen this key":

One line in that idiom deserves a pause: why not just write tally[s] += 1? Try it on an empty dict and Python raises a KeyError, because you're asking to read a count that doesn't exist yet. The very first "Levels" play has no entry to increment, and there is no 0 sitting there waiting for you. That is exactly the hole .get(s, 0) plugs: it returns the stored count if the key exists, and the default 0 if it doesn't. So the first play computes 0 + 1 and writes 1, and every later play reads the real count and bumps it. Same jump, one graceful default.

tally = {}
for s in plays:
    tally[s] = tally.get(s, 0) + 1     # jump to s, read count, add 1, store
print(tally)     # {'Levels': 3, 'Titanium': 2, 'Wake Me Up': 1}

There are only three lines of mechanism here. tally.get(s, 0) fetches the running count in O(1), we add one to it, and tally[s] = … writes the new count back in O(1). No list, no scan, no re-counting — each play is touched exactly once. Python ships this pattern pre-built as collections.Counter, which does the same thing and adds the questions you actually ask of a tally:

from collections import Counter
print(Counter(plays).most_common(1))          # [('Levels', 3)]  — the top song
print(Counter("mississippi").most_common(2))  # [('i', 4), ('s', 4)]

That second line is worth a pause. A whole class of interview questions just got reduced to one line. Think "most frequent character", "top-k words", or "find the anagram groups". Each of those problems is a tally wearing a costume. That is the theme of this whole section: counting is just hashing with a running total.

you type
# ---------- three_patterns.py ----------
from collections import Counter, defaultdict

plays = ["Levels", "Titanium", "Levels", "Wake Me Up", "Titanium", "Levels"]

print("1. HAVE I SEEN IT?  -- a set: one probe per item, no inner scan")
seen, repeats = set(), []
for s in plays:
    if s in seen: repeats.append(s)
    seen.add(s)
print("   seen    ", sorted(seen), "  (sorted for printing -- a set has no order)")
print("   repeats ", repeats)

print("\n2. HOW MANY OF EACH? -- a Counter: a dict that starts every key at 0")
c = Counter(plays)
print("   Counter ", c)
print("   c['Faded'] ->", c["Faded"], "  (a missing key is 0, never a KeyError)")
print("   most_common(2) ->", c.most_common(2))

print("\n3. WHICH ONES BELONG TOGETHER? -- defaultdict(list): the bucket makes itself")
words = ["listen", "silent", "google", "enlist", "gogole", "banana"]
groups = defaultdict(list)
for w in words:
    groups["".join(sorted(w))].append(w)      # the KEY is the design decision
print("   keyed by sorted letters ->", dict(groups))
print("   the groups themselves   ->", list(groups.values()))

print("\ntwo one-liners the same machinery buys you")
print("   dedupe, order kept  ->", list(dict.fromkeys(plays)))
print("   anagram test        ->", Counter("listen") == Counter("silent"))

$ python three_patterns.py

you see
1. HAVE I SEEN IT?  -- a set: one probe per item, no inner scan
   seen     ['Levels', 'Titanium', 'Wake Me Up']   (sorted for printing -- a set has no order)
   repeats  ['Levels', 'Titanium', 'Levels']

2. HOW MANY OF EACH? -- a Counter: a dict that starts every key at 0
   Counter  Counter({'Levels': 3, 'Titanium': 2, 'Wake Me Up': 1})
   c['Faded'] -> 0   (a missing key is 0, never a KeyError)
   most_common(2) -> [('Levels', 3), ('Titanium', 2)]

3. WHICH ONES BELONG TOGETHER? -- defaultdict(list): the bucket makes itself
   keyed by sorted letters -> {'eilnst': ['listen', 'silent', 'enlist'], 'eggloo': ['google', 'gogole'], 'aaabnn': ['banana']}
   the groups themselves   -> [['listen', 'silent', 'enlist'], ['google', 'gogole'], ['banana']]

two one-liners the same machinery buys you
   dedupe, order kept  -> ['Levels', 'Titanium', 'Wake Me Up']
   anagram test        -> True

Membership, dedup, counting — all one pass because the lookup is free. Now the headline act: a lookup that was trapped inside a second loop, and how a dict sets it free →

04The "seen" dict: how a hash deletes an inner loop

Here is the pattern that separates the two programmers from the volume's opening. Take two-sum: given a list of numbers and a target, find two of them that add to the target. The obvious solution tries every pair — for each number, loop over all the others looking for its partner. That inner loop is a search, and it runs for every element, so the cost is every-pair: n(n−1)/2, which is O(n²). We counted the pair-checks exactly:

Where does n(n−1)/2 come from? It's worth counting honestly once, so the formula stops being a spell. Each of the n numbers can pair with the n−1 others. That gives n(n−1) ordered pairs. But the pair (3, 7) is the same as (7, 3) for us. So every pair got counted twice, and we divide by 2. Check it small with the 4 numbers 2, 5, 8, 11. The formula says 4 × 3 ÷ 2 = 6. List the pairs: (2,5), (2,8), (2,11), (5,8), (5,11), (8,11). That is exactly 6. That count grows like n², and that is why the naive version drowns.

def two_sum_naive(nums, target):          # O(n^2): every pair
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):   # the inner loop IS a search
            if nums[i] + nums[j] == target:
                return (i, j)

def two_sum_hash(nums, target):           # O(n): one pass, a dict remembers
    seen = {}                             # value → index we saw it at
    for i, x in enumerate(nums):
        need = target - x                 # the exact partner x is looking for
        if need in seen:                  # O(1) — ask the dict, don't scan
            return (seen[need], i)
        seen[x] = i                       # write x down; value → index seen

The insight is small and total. In the naive version, when we hold x we don't know where its partner is, so we search for it. But we know exactly what the partner must be: target - x. So instead of searching, we keep a "seen" dict of every number we've passed, and simply ask it "have you got target - x?" — an O(1) jump. The inner loop doesn't get faster. It disappears. We ran both and counted operations at the worst case (the answer is the last pair):

# n     naive ops     hash ops
# 10          45          10
# 100       4,950         100
# 1000    499,500        1000     ← n(n-1)/2 vs n

At n=1000 the nested loop does 499,500 pair-checks, while the dict version does just 1,000 lookups. That is not a tweak: it is 500× at a thousand items, and it grows to 500,000× at a million. Two-sum is stepped line by line in trace T31, so step it and watch the "seen" dict fill as the loop walks. The point here is the move itself, not this one problem.

"""seen_and_group.py -- two classics, each one of the three idioms wearing a costume."""
import random, time
from collections import defaultdict

def first_duplicate(items):
    """The first value that shows up a SECOND time, or None. One pass, O(n)."""
    seen = set()
    for x in items:
        if x in seen:              # O(1) probe -- the whole point
            return x
        seen.add(x)                # write it down and walk on
    return None

def group_anagrams(words):
    """Words that are the same letters rearranged, grouped together. One pass."""
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)   # the canonical form IS the key
    return list(groups.values())

print("first_duplicate('playlist')      ->", repr(first_duplicate("playlist")))
print("first_duplicate([3, 1, 4, 1, 5]) ->", first_duplicate([3, 1, 4, 1, 5]))
print("first_duplicate([1, 2, 3])       ->", first_duplicate([1, 2, 3]))
print("group_anagrams([...])            ->",
      group_anagrams(["listen", "silent", "google", "enlist", "gogole", "banana"]))

def first_duplicate_brute(items):          # the oracle: obviously right, obviously slow
    out = []
    for x in items:
        if x in out: return x              # a LIST scan: O(n) per item
        out.append(x)
    return None

def group_anagrams_brute(words):           # the oracle: compare every pair
    groups, used = [], [False] * len(words)
    for i, w in enumerate(words):
        if used[i]: continue
        g, used[i] = [w], True
        for j in range(i + 1, len(words)):
            if not used[j] and sorted(words[j]) == sorted(w):
                g.append(words[j]); used[j] = True
        groups.append(g)
    return groups

random.seed(37)
for _ in range(2_000):                     # property test, both functions, 2,000 cases
    xs = [random.randrange(12) for _ in range(random.randint(0, 15))]
    assert first_duplicate(xs) == first_duplicate_brute(xs), xs
    ws = ["".join(random.sample("abcde", random.randint(1, 4))) for _ in range(6)]
    assert sorted(map(sorted, group_anagrams(ws))) == sorted(map(sorted, group_anagrams_brute(ws)))
print("\n2,000 random cases against the brute-force oracle: 0 mismatches")

items = random.sample(range(10 ** 7), 20_000)   # worst case: the repeat is the LAST item
items.append(items[0])
for fn in (first_duplicate_brute, first_duplicate):
    t0 = time.perf_counter(); hit = fn(items); dt = (time.perf_counter() - t0) * 1000
    print(f"  {fn.__name__:<22} n={len(items):,}  found {hit}  {dt:>9.2f} ms")

words = ["".join(random.sample("abcdefghijkl", 6)) for _ in range(3_000)]
for fn in (group_anagrams_brute, group_anagrams):
    t0 = time.perf_counter(); g = fn(words); dt = (time.perf_counter() - t0) * 1000
    print(f"  {fn.__name__:<22} {len(words):,} words -> {len(g):,} groups  {dt:>9.2f} ms")


# ---------- what it printed (milliseconds are this machine's; the ratios are the lesson) ----------
#
# first_duplicate('playlist')      -> 'l'
# first_duplicate([3, 1, 4, 1, 5]) -> 1
# first_duplicate([1, 2, 3])       -> None
# group_anagrams([...])            -> [['listen', 'silent', 'enlist'], ['google', 'gogole'], ['banana']]
#
# 2,000 random cases against the brute-force oracle: 0 mismatches
#   first_duplicate_brute  n=20,001  found 5190241    1368.68 ms
#   first_duplicate        n=20,001  found 5190241       2.06 ms
#   group_anagrams_brute   3,000 words -> 884 groups     589.66 ms
#   group_anagrams         3,000 words -> 884 groups       1.32 ms
#
#
# ---------- the two questions, answered from those numbers ----------
#
# WHERE THE 1,368 MILLISECONDS WENT.
#   The list version rescans everything it has kept so far, so item k costs k-1
#   comparisons. The total is the staircase 0 + 1 + ... + 19,999 = n(n-1)/2 =
#   199,990,000 comparisons -- the same every-pair triangle as two-sum. The set
#   version does 20,001 hashes and 20,001 probes. That is 664x here, and the
#   multiplier is n/2, so it doubles every time the input doubles.
#
# WHY sorted(w) IS STILL THE RIGHT KEY.
#   It looks like a betrayal: we came here to delete work, and the key does
#   k*log(k) of it per word. But look at what it buys. Anagrams are exactly the
#   words with the same multiset of letters, and sorting is a canonical form --
#   one string that every anagram of a word maps to, and nothing else does.
#   With it, each word is touched once: total n*k*log(k), linear in the number
#   of WORDS. Without it you must compare words pairwise, which is n^2/2
#   comparisons that each cost a sort anyway. Here: 3,000 words, 884 groups,
#   1.32 ms against 589.66 ms. A cheap canonical key beats a cheap comparison,
#   because the key is paid n times and the comparison n^2 times.
#   (tuple(sorted(w)) works identically -- a tuple is hashable, a list is not.
#    For fixed alphabets, a 26-slot count tuple is the O(k) version of the key.)

Remembering what you've seen kills the search. Remembering what you've already computed kills something bigger — repeated work →

05The cache: answer each question once

The "seen" dict remembers values you've passed. A cache remembers answers you've computed, so you never compute the same one twice. This is memoization, and it is the same dict trick pointed at a function. The classic victim is naive recursive Fibonacci, which re-solves the same subproblems an exponential number of times. A dict cache turns the tree of repeated calls into a straight line:

Before the fix, feel the disease at a size small enough to check by hand. fib(5) calls fib(4) and fib(3). Then fib(4) calls fib(3) again, so fib(3) is already being solved twice in this tiny computation. Count every call in the tree and you get 15 of them for fib(5), yet there are only 6 distinct values from fib(0) to fib(5). The waste roughly doubles with every step up, because each new call spawns two more below it. That doubling is what "exponential" means in practice, and it is why the counter below reads in the millions. The cache's promise is simple: each distinct value gets solved once, so 6 distinct values should cost about 6 real computations.

cache = {}
def fib(n):
    if n < 2:
        return n
    if n not in cache:                    # already answered? jump to it
        cache[n] = fib(n-1) + fib(n-2)    # first time only: compute, store
    return cache[n]

Walk the lines: the base cases return immediately, and otherwise we ask the cache in O(1) whether we've solved this n before. If we haven't, we compute it once and write the answer down in the dict. Every later request for the same n is then a free jump straight to that stored answer. The effect is violent, and to prove it we instrumented both versions with a call counter:

# fib(30):
#   naive recursion : 2,692,537 calls
#   with the cache  :        59 calls

Two and a half million calls become 59. The naive tree recomputes fib(28) tens of thousands of times; the cache computes it once and answers the rest from memory. (The recursion tree exploding then collapsing is a live widget in the Algorithms Lab, and stepped in the traces.)

06The bill: space, hashable keys, and the worst case

O(1) is bought, not free. Three costs come with it. An engineer names them out loud.

Cost one — space. A set or dict holds your data plus a table of slots that is deliberately kept larger than the data (so collisions stay rare — Volume 1 chapter 7). Trading memory for time is the whole deal; on a huge dataset that memory can be the thing you don't have.

Cost two — the keys must be hashable. To hash a key, its value must be fixed, so that its hash never changes underneath the table. If a key could mutate after it was filed, its hash would point at the wrong slot and the table would lose it. That means immutable keys only, and lists are mutable, so Python bars them loudly:

{ ["Levels", 200]: 1 }         # TypeError: unhashable type: 'list'
{ ("Levels", 200): 1 }         # fine — a tuple is immutable, so hashable
print([].__hash__)             # None   — lists opt out of hashing entirely

Look at that error, because it is a design choice and not an accident. A list's __hash__ is literally None — the type refuses to be a key. Tuples of immutable things are the standard fix when you need a compound key. That's why grid coordinates, dates, and (name, version) pairs are so often tuples in real code.

Cost three — O(1) is the average, not a guarantee. The jump is fast only when values scatter nicely across the slots. If many keys land in the same slot, we call that a collision, and the table has to walk the pile-up one entry at a time. In the pathological case where everything collides, the lookup degrades to the very linear scan we were escaping. We forced that case on purpose, using keys whose hash is a constant so they all target one slot:

class AllSame:                       # a deliberately terrible key
    def __init__(self, v): self.v = v
    def __hash__(self): return 42    # EVERY instance → the same slot
    def __eq__(self, o): return self.v == o.v

# building a set of these, timed on the test machine:
#   n=1000   0.030 s      n=2000   0.109 s      n=4000   0.442 s
#   → doubling n roughly QUADRUPLES the time: O(n^2) build, O(n) per op

When every key collides, doubling the data quadruples the work — the signature of O(n²). The O(1) promise didn't just weaken; it collapsed all the way back to a scan. In normal use this never happens, because a good hash function scatters keys evenly. But "normal use" assumes nobody is choosing the keys on purpose.

The quadrupling isn't mysterious once you count the pile-up. When every key targets one slot, the k-th insertion has to walk past the k−1 entries already parked there. The total is the staircase again: 0 + 1 + … + (n−1), which is n(n−1)/2. Plug the numbers in: n=1000 gives 499,500 steps, and n=2000 gives 1,999,000, which is almost exactly 4×. Doubling n quadruples the bill because the cost formula holds an n² inside it. So "doubling the data quadruples the work" is not just an observation — it is the fingerprint of O(n²), and you can read it off any timing table.

That attack has a name: hash flooding. Around 2011, researchers showed that many web platforms built dicts straight from untrusted input. Python, PHP, Java, Ruby, ASP.NET and more all hashed POST fields, JSON keys, and HTTP headers with a fixed, published hash function. So an attacker could craft thousands of keys that all collide, turning one small request into an O(n²) grind that pinned a server's CPU. The fix Python shipped is quietly brilliant: randomize the hash. Each process seeds its string hash with a secret chosen at startup, so an attacker can't predict which keys collide. You can watch the seed change between runs:

# two separate Python processes, same line:
hash("Levels")   #  4417089987191320694   (first process)
hash("Levels")   #   -41086165888829000   (second process — different!)
hash(200)        #  200   (integers still hash to themselves, both runs)

Same string, different hash every process — that unpredictability is the defense. One aside on the earlier demo: integers hash to themselves, which is why the crafted-collision demo needed a broken __hash__. CPython's probing manages to scatter even adversarial integer keys on its own. This randomization is also why you must never rely on a set or dict's iteration order being stable across runs. And it is why security-sensitive code exists to make hashing unguessable.

Hashing bought O(1) by scattering keys to random slots — deliberately destroying order for speed. The next chapter asks the opposite question: the next chapter buys that same speed for free — no extra memory at all — with two pointers and a sliding window: array sweeps that compute the change between overlapping states instead of restarting the work each time → →