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). Here we buy speed a different way. We spend memory to get rid of searching altogether. Almost every slow program is slow for the same 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. The whole way through, we keep asking the one thing 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 delete that inner loop on sight, collapsing 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 Python has no choice but to look. It starts at index 0 and compares element by element, until it either finds a match or falls off the end. If the thing isn't there, it has touched every single element just to tell you so. That is a linear scan. Its cost grows in step with the size of the list: one comparison per item, n items, O(n). No hand-waving — 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

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

Now the trick. A set (and a dict, its key-value sibling) does not store your values in a row to be walked. 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, look: one hash, one jump, one compare. The cost does not grow with n at all. That is O(1), "constant time." We timed the exact same "is this missing value here?" question against both:

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)

Read the two columns. 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: about 38 nanoseconds whether it holds a thousand items or a million. At a million items the set answers the question roughly 160,000 times faster. (Timings are from this machine and will vary. The shape is what's 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. Two everyday jobs fall out of it for free. First, membership: x in some_set is the O(1) jump you just met. Second, deduplication, which means collapsing a collection to its distinct values. This works because a set physically cannot hold the same value twice. Adding a value that's already there does nothing:

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) is a single pass. It hashes each of the six songs and drops it into its slot; repeats land on a slot that's already taken and vanish. One line, O(n), done. Compare the beginner's instinct: a nested loop that asks "have I seen this before?" by scanning a growing result list. That is O(n²) for the exact same answer. The set replaces that inner scan with a hash.

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 is O(1), so the whole tally is O(n). The idiom uses .get(key, 0), which reads "the current count, or 0 if we've never seen this key":

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}

Three lines of mechanism: tally.get(s, 0) fetches the running count in O(1); we add one; tally[s] = … writes it 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 a whole class of interview questions — "most frequent character", "top-k words", "find the anagram groups" — reduced to one line. That's because counting is just hashing with a running total.

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:

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, where 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; the dict version does 1,000 lookups. That is not a tweak. It is 500× at a thousand items and 500,000× at a million. Two-sum is stepped line by line in trace T31. The point here is the move, not this one problem.

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:

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]

Line by line: base cases return immediately. Otherwise we ask the cache in O(1) whether we've solved this n before. If not, we compute it once and write it down. Every later request for the same n is a free jump. The effect is dramatic. 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 is stepped in the traces.)

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

O(1) is bought, not free. Three costs come with it, and 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 its hash never changes underneath the table. That means immutable keys only. Lists are mutable, so they're barred — 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

A list's __hash__ is literally None: it refuses to be a key. Tuples of immutable things are the standard fix. That's why grid coordinates, dates, and (name, version) pairs are so often tuples.

Cost three — O(1) is the average, not a guarantee. The jump is fast only when values scatter across slots. If many keys land in the same slot — a collision — the table has to walk that pile-up. In the worst case, where everything collides, the lookup degrades to the very linear scan we were escaping. We forced it, 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.

That attack has a name: hash flooding. Around 2011, researchers showed that many web platforms — Python, PHP, Java, Ruby, ASP.NET and more — built dicts from untrusted input (POST fields, JSON keys, HTTP headers) with a fixed, published hash function. 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. Python's fix is simple: 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, a different hash in every process — that unpredictability is the defense. (Integers hash to themselves, which is why the crafted-collision demo above needed a broken __hash__: CPython's probing scatters even adversarial integer keys.) This is why you must never rely on a set or dict's iteration order being stable across runs, and 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 → →