The Hashing Mental Model

The promise from lesson 1-1 was an explanation of how the dict jumps straight to where a key lives.

The list scan checked 10,000 entries because it had no idea where the key was, so it looked everywhere. The dict checked one because it computed the location instead of searching for it.

This unit opens up that machine. A hash function turns the key itself into an array index, which turns lookup back into the O(1) address arithmetic from unit 2.

From key to index

Arrays taught the fastest possible lookup: compute an address, jump there, O(1). The obstacle is that array indexes are the numbers 0 through n−1, while dict keys are things like "ana".

A hash table bridges that gap with two pieces.

1. An ordinary array of n slots, called buckets.
2. A hash function, a deterministic recipe turning any key into a number, which % n then squeezes into a valid bucket index.

Deterministic is the load-bearing word. The same key must always yield the same number, so the bucket written into is the bucket that will be read from later.

A classic recipe for strings runs through the characters, multiplying a running total by 31 and adding each character's code from ord(ch). The multiplication is what makes order matter, so "ab" and "ba" land in different places.

Storing the pair ("ana", 91) hashes "ana" to bucket 4 and drops the pair there. Looking up "ana" hashes it again, gets 4 again, and jumps straight to that bucket without ever examining another one.

The hash recipe on four names

Four names, eight buckets, same recipe for every key.

def simple_hash(key, buckets):
    total = 0
    for ch in key:
        total = total * 31 + ord(ch)
    return total % buckets

for name in ["ana", "ben", "cai", "dee"]:
    print(name, "->", "bucket", simple_hash(name, 8))

Output

ana -> bucket 4
ben -> bucket 3
cai -> bucket 3
dee -> bucket 4

Run this a thousand times and the numbers never move. That is determinism in practice, and it is what makes the bucket a reliable place to look rather than a guess.

Two pairs of names share a bucket here. ben and cai both landed in 3, and ana and dee both landed in 4, which is called a collision.

Nothing in the recipe prevents that, since it maps an unlimited set of strings onto eight numbers. Lesson 6-2 is about what a table does when two keys arrive at the same slot.

Watching collisions change with the bucket count

bucket_of is the recipe from the demo, and find_collisions files each name under its bucket and reports only the shared ones.

def bucket_of(key, buckets):
    total = 0
    for ch in key:
        total = total * 31 + ord(ch)
    return total % buckets

def find_collisions(names, buckets):
    landed = {}
    for name in names:
        landed.setdefault(bucket_of(name, buckets), []).append(name)
    return {b: group for b, group in landed.items() if len(group) > 1}

names = ["ana", "ben", "cai", "dee", "eve", "flo"]
print("collisions in 8 buckets:", find_collisions(names, 8))
print("collisions in 11 buckets:", find_collisions(names, 11))

Output

collisions in 8 buckets: {4: ['ana', 'dee', 'eve'], 3: ['ben', 'cai']}
collisions in 11 buckets: {}

landed.setdefault(b, []).append(name) files a name under bucket b, creating the empty list the first time that bucket comes up, and the dict comprehension keeps only groups of two or more.

The two results are the same six names with the same hash function. With 11 buckets they happen to spread out perfectly, which shows that collisions are a property of the table's size as much as of the keys.

The deeper consequence is in the formula. Since bucket = hash % buckets, changing the bucket count changes every bucket number, not just the crowded ones.

That is why growing a hash table cannot simply copy the old buckets across. Every key has to be re-filed under its new index, a point lesson 6-2 returns to.

A hash function must be deterministic because lookup re-hashes the key to find the bucket, so it has to land where the store landed.

The table never remembers where a key went. It keeps no directory and no back-reference, and it recomputes the bucket from the key on every single operation.

So if "ana" hashed to 4 while storing but 6 while looking up, the value would be sitting in bucket 4 and unreachable forever, with no error raised to say so.

This is why hashing an object whose contents can change is dangerous, and why Python refuses to use a list as a dict key. Mutate the key and its hash moves, which strands the value in a bucket nothing will ever check again.