Recursion and Hashing

Hashing and hash tables

Turning a key into an address for instant lookup

~12 minLesson 8 of 25Written by Claude Opus 4.8

How a dictionary lookup that could scan a million keys instead finds any one of them in a single step - most of the time.

An array gives you instant access if you already know the index. But your keys are usually names, words, URLs - not integers 0…n. A is the bridge: it turns any key into an array index, so table["owl"] becomes a plain $O (1)$ array fetch. The catch is that different keys can map to the same index - a - and the entire craft of hash tables is keeping those collisions rare enough that lookups stay fast.

The coat-check analogy

At a coat check you don't search every hook for your coat. You hand over a ticket with a number, and the attendant walks straight to hook

#47

. A hash function is the machine that prints the ticket: feed it your key, out comes a hook number. If two coats ever get the same number, you hang them on the same hook and sort it out when you return - that's a collision, and it's survivable as long as no single hook gets overloaded.

A key becomes an index

A hash function $h$ chews on the raw bytes of a key and spits out an integer. To land inside a table of $m$ buckets, we fold that integer down with the modulo operator. That single line is the whole trick:

From key to bucket

index = h (key) mod m

where $h (key)$ is the raw hash (some big integer) and $m$ is the number of buckets. Because the result is a genuine array index, reading or writing that bucket is the same $O (1)$ address arithmetic you saw for arrays - no scan involved. A good hash function has three jobs: be deterministic (same key -> same index, every time), fast to compute, and uniform - scatter keys evenly so no bucket hogs them. A tiny change in the key ideally lands in a totally different bucket.

# Turn any string key into a bucket index.
def bucket_of(key, m):
    h = 0
    for ch in key:            # 'owl' -> 111 + 119 + 108
        h += ord(ch)          # h = 338   (the raw hash)
    return h % m               # 338 % 8 = 2  -> bucket 2

# Real hashers MIX bits instead of just adding, e.g.
#   h = h * 31 + ord(ch)
# so that 'listen' and 'silent' don't collide the way a plain sum does.

The toy hash used in the demo below - sum the character codes, then fold

A plain sum is a bad hash - on purpose

Summing character codes makes collisions easy to see, which is great for learning. But it's genuinely poor: any two anagrams (listen / silent, ant / tan) share the same sum, so they always collide. Production hashes multiply-and-mix the bits (Java's hashCode, Python's SipHash) so that even "cat" and "cau" fly to unrelated buckets. Same idea, far better spread.

Collisions: when two keys want the same box

Uniform or not, collisions are inevitable - with more keys than buckets they're guaranteed. Two strategies dominate. (what the sandbox shows) hangs a little linked list off each bucket; colliding keys just join the chain. keeps one key per bucket and, on a clash, probes onward - linear probing simply tries the next bucket, then the next, until it finds an empty slot. Chaining is simpler and degrades gracefully; open addressing is cache-friendlier because everything lives in the one contiguous array.

Build a hash table by hand

Type a key (or click a preset animal) and watch the hash function compute its bucket live. Keys that collide stack up into visible chains. Keep inserting - or drag the rehash threshold - and when the load factor crosses it, the whole table doubles and every key is re-bucketed into the bigger array before your eyes.

Hash-table sandbox type - insert - rehash

key

Type a key to watch h(key) mod m pick its bucket.

rehash when load factor > 0.75

buckets m = 8keys n = 0load factor α = 0.00

0α = n / m1.5

Empty table with 8 buckets. Insert keys and watch collisions form chains.

Load factor decides the speed

The load factor is simply how full the table is:

α = \frac{n}{m} (keys \div buckets) .

Under uniform hashing the expected length of any chain is exactly $α$ , so an average lookup costs $O (1 + α)$ - the $1$ to compute the hash, the $α$ to walk that bucket's chain. Keep $α$ below a constant (Java uses $0.75$ ) and both terms are constant, giving amortized $O (1)$ . Let $α$ drift upward and chains lengthen, so we rehash: allocate a table roughly twice as big and reinsert every key. That's an $O (n)$ jolt, but like the dynamic-array doubling you already met, doublings are rare enough that the cost amortizes away.

Sets, maps, and the O(n) cliff

The same machinery powers two everyday structures. A stores only keys and answers "is $x$ present?" - Python's set, Java's HashSet. A stores a value alongside each key and answers "what is $x$ mapped to?" - Python's dict, Java's HashMap. A set is just a map whose values you ignore; both hash the key to find the bucket in the same way.

But that cheerful $O (1)$ is an average, not a guarantee. If a bad hash (or an adversary picking keys on purpose) funnels every key into one bucket, the table collapses into a single long chain and every lookup scans it - $O (n)$ , no better than an unsorted list. Good hashing and a bounded load factor are what keep you off that cliff.

The aha

A hash table isn't magic - it's an array plus arithmetic. The hash function manufactures an index so you can skip the search entirely, and rehashing keeps the chains short so that "skip the search" stays true as the table grows. Speed comes from the index being computed, never hunted for.

Check yourself

With a good hash function and the load factor held low, an average hash-table lookup costs:

A hash table degrades to O(n) lookup precisely when:

Recall: what does the load factor α measure, and why do we rehash when it climbs?

Tie the load factor to chain length and lookup cost. Try to state it, then check.

Lock it in

A hash function manufactures an index from a key - $index = h (key) mod m$ - so a lookup is O(1) address arithmetic, never a scan.
A good hash is deterministic, fast, and uniform; collisions are inevitable and are absorbed by chaining or open addressing.
Average cost is $O (1 + α)$ for load factor $α = n / m$ ; keep $α$ bounded by rehashing (double and reinsert) for amortized O(1).
The O(1) is an average, not a guarantee: funnel every key into one bucket and the table collapses to an O(n) linear scan.

Primary source

Princeton's algs4 booksite (the Sedgewick & Wayne Algorithms text) has the definitive treatment of hashing - separate chaining, linear probing, and the load-factor analysis, with clean reference implementations. To watch insertions, collisions, and probing step by step, drive the interactive VisuAlgo Hash Table visualizer.

Ask your teacher

Want to see linear probing's clustering, or why hash tables need resizing to a prime size, or how cryptographic hashes differ from these? Ask and I'll build the follow-up. Here's the thread worth pulling, spelled out in hash tables to vector search and ANN in the LLM course: hashing trades exactness for near-

O (1)

lookup, and vector databases for RAG make the very same bargain. Locality-sensitive hashing and approximate-nearest-neighbor (ANN) indexes retrieve the closest embeddings in sublinear time instead of scanning millions of vectors - accepting "almost the nearest" in exchange for speed, exactly as a hash table accepts occasional collisions.