Hash functions and collision strategy

What this chapter covers

The last chapter built a hash table and waved at the hash function doing the real work. This chapter looks straight at it, because a hash table is only ever as good as the function spreading keys across its buckets. A good hash scatters keys uniformly and lookups stay O(1); a bad one clusters them and the table quietly collapses into a linear scan. We'll build a few real hash functions and one deliberately bad one, and measure how evenly each spreads a dictionary of words — because "spreads evenly" is the entire specification.

A bit of history

Hash functions have been studied as seriously as any algorithm. Donald Knuth devoted a large part of the third volume of The Art of Computer Programming (1973) to them, analyzing the multiplicative method — multiply the key by a fraction of the golden ratio and take the fractional part — that still bears his name. The polynomial string hash in this chapter is the one Java's String.hashCode has used for decades. FNV, another one here, was designed by Glenn Fowler, Landon Curt Noll, and Kiem-Phong Vo in 1991, prized for being fast with good avalanche. And the hash Python actually uses for strings, SipHash, was published in 2012 by Jean-Philippe Aumasson and Daniel J. Bernstein specifically to stop attackers from crafting keys that collide — a defense against the denial-of-service attack the last chapter warned about. Seventy years in, people are still designing hash functions, because the trade-offs between speed, distribution, and security never fully settle.

The intuition

A hash function has one job: take a key and produce an integer that's spread out evenly over its range, so that when you fold it into buckets, the keys land everywhere instead of piling up. The way you get that is mixing — every part of the key has to influence the result, and small changes to the key should scramble the output completely.

The failure mode is hashing on only part of the key. Imagine a hash that looks at just the first letter of a word. It's fast and deterministic, but English words aren't spread evenly across first letters — far more start with s or c than with x or z — so the buckets for common letters overflow while others sit empty. That's not a contrived example; it's the shape of every real bad hash: it ignores information in the key, so structure in the data leaks straight through into lopsided buckets.

Complexity and quality

Computing a hash costs $O(k)$ for a key of length k — you touch every byte, which is exactly why mixing the whole key is affordable. That cost is paid on every single lookup, insert, and delete, so a hash needs to be fast; this is why hash tables use cheap non-cryptographic hashes and not SHA-256.

But speed isn't the metric that matters most here — distribution is. The way to measure it is to hash a real set of keys into buckets and see how far the loads stray from perfectly even, which the chi-square statistic captures (lower is more uniform). The chart hashes a 180-word dictionary into 16 buckets with each function:

The four good hashes give roughly flat bars — every bucket near the ideal of 11 words. The first-letter hash is a skyline: its worst bucket holds 51 of the 180 words while 11 of the 16 buckets are completely empty. Its chi-square is 509 against FNV-1a's 15 — a thirty-fold difference in how lopsided the table would be. A hash table built on that first-letter hash isn't a hash table anymore; it's a linked list with extra steps.

What it's good at, what it isn't

The hashes you want for a table — polynomial, FNV, SipHash — are all fast, all mix the whole key, and all distribute real-world keys close to uniformly. That's the sweet spot: cheap enough to run on every operation, good enough that collisions stay rare. For a hash table, reach for the one your language gives you (hash() in Python) and don't hand-roll unless you're in a lower-level language without one.

What none of these are is secure. A fast hash is easy to reverse-engineer and forge, so it must never be used where an adversary could exploit predictable collisions or fake a digest — that's the job of a cryptographic hash. And the reverse is just as wrong: a cryptographic hash in a hash table is a performance bug, wasting cycles on security you don't need.

The data, or the inputs

The keys are a dictionary of 180 real English words — the kind of data a spell-checker or search index actually hashes — chosen because their first letters follow English frequency. That skew is invisible to a hash that mixes the whole word and catastrophic to one that looks at the first letter, which is precisely the difference the chapter is measuring. The animation uses the first 40 of those words so you can watch the buckets fill in real time.

Build it, one function at a time

The polynomial hash multiplies the running total by a prime before adding each character, so a character's position affects the result — abc and cba differ:

def poly_hash(s, mod=2 ** 32):
    """Polynomial hash: h = h*31 + c for each character. The classic string hash
    (it's Java's String.hashCode). Multiplying by a prime before adding the next
    character mixes position into the result, so 'abc' and 'cba' land apart."""
    h = 0
    for ch in s:
        h = (h * 31 + ord(ch)) % mod
    return h

FNV-1a mixes by xor-then-multiply per byte, which gives strong avalanche — one flipped input bit changes about half the output bits:

def fnv1a(s, mod=2 ** 32):
    """FNV-1a: for each byte, xor it in then multiply by a large prime. Strong
    avalanche — flipping one input bit flips about half the output bits — and
    fast, which is why it's a popular non-cryptographic hash."""
    h = 2166136261
    for ch in s:
        h = ((h ^ ord(ch)) * 16777619) % mod
    return h

And here's the villain — the hash that looks at only the first character and throws the rest of the key away:

def bad_hash(s, mod=2 ** 32):
    """A deliberately bad hash: it looks at only the FIRST character and ignores
    the rest of the key. On real data this clusters hard — English words are
    dominated by a handful of starting letters — so most keys pile into a few
    buckets and the rest sit empty. The lesson: a hash must mix the WHOLE key."""
    return (ord(s[0]) if s else 0) % mod

Watch it work

Two heatmaps, both filling 16 buckets as the same 40 words stream in. The top row is FNV-1a; the bottom is the first-letter hash. Watch them diverge: FNV-1a stays a cool, even blue — every bucket gaining words at about the same rate — while the first-letter hash lights up a few buckets an angry red and leaves the rest dark, as all the words starting with the same common letters pile into the same slots. Same words, same number of buckets; the only difference is whether the hash looked at the whole key:

The complete code

Both versions in one place — flip between them. The from-scratch tab has the three hashes above. The library tab is what Python gives you: hash(), the fast SipHash the dict uses, and hashlib's SHA-256 for when you need cryptographic strength.

"""Hash functions — the piece the last chapter took for granted.

A hash table is only as good as the function spreading keys across its buckets. A
good hash scatters keys uniformly, so buckets stay balanced and lookups stay O(1);
a bad one clusters them, and the table degrades toward a linear scan. This chapter
builds a few real hash functions and one deliberately bad one, and measures how
evenly each spreads a set of words — because "spreads evenly" is the entire job.
"""


# region: poly_hash
def poly_hash(s, mod=2 ** 32):
    """Polynomial hash: h = h*31 + c for each character. The classic string hash
    (it's Java's String.hashCode). Multiplying by a prime before adding the next
    character mixes position into the result, so 'abc' and 'cba' land apart."""
    h = 0
    for ch in s:
        h = (h * 31 + ord(ch)) % mod
    return h
# endregion


# region: fnv1a
def fnv1a(s, mod=2 ** 32):
    """FNV-1a: for each byte, xor it in then multiply by a large prime. Strong
    avalanche — flipping one input bit flips about half the output bits — and
    fast, which is why it's a popular non-cryptographic hash."""
    h = 2166136261
    for ch in s:
        h = ((h ^ ord(ch)) * 16777619) % mod
    return h
# endregion


# region: bad_hash
def bad_hash(s, mod=2 ** 32):
    """A deliberately bad hash: it looks at only the FIRST character and ignores
    the rest of the key. On real data this clusters hard — English words are
    dominated by a handful of starting letters — so most keys pile into a few
    buckets and the rest sit empty. The lesson: a hash must mix the WHOLE key."""
    return (ord(s[0]) if s else 0) % mod
# endregion


def bucket_of(hash_value, num_buckets):
    """Fold a hash value into a bucket index — the modulo the table applies."""
    return hash_value % num_buckets

"""Python already gives you two kinds of hash, at opposite ends of the trade-off.

`hash()` is the fast, non-cryptographic hash the built-in dict uses. For strings
it's SipHash, seeded with a per-process random key so an attacker can't predict
collisions. `hashlib` gives cryptographic hashes (SHA-256, etc.) — far slower, but
with the best possible distribution and designed so you can't reverse or forge them.

For a hash table you want the first. This chapter's face-off measures how well our
hand-written hashes distribute keys compared to Python's built-in `hash`.
"""
import hashlib


# region: python_hash
def python_hash(s, mod=2 ** 32):
    """Python's built-in hash() — SipHash for strings, randomized per process to
    resist algorithmic-complexity attacks. This is what `dict` uses."""
    return hash(s) % mod
# endregion


# region: sha256_hash
def sha256_hash(s, mod=2 ** 32):
    """A cryptographic hash reduced to an integer. Overkill (and slow) for a hash
    table, but the gold standard for uniform distribution — a useful yardstick."""
    return int(hashlib.sha256(s.encode()).hexdigest(), 16) % mod
# endregion

Scratch vs library

This face-off is about quality, not speed, so the comparison is the distribution chart above — and our polynomial and FNV-1a hashes hold their own against Python's built-in hash, all three landing near-uniform (chi-squares of 18, 15, and 10 against the ideal). That's the reassuring result: a competent hand-written hash is genuinely competitive with the standard library's on distribution, because good mixing is not hard once you know to mix the whole key. Where the library wins is the things you don't see in a distribution chart — SipHash's per-process random seed that ours lacks (so ours would be vulnerable to a collision attack), and a C implementation that's faster than our Python loop. Use hash(); build these to understand what makes it trustworthy.

Where you'll actually meet it

You rely on a hash function every time you use a dict, a set, or a database index — it's the invisible layer under everything the last chapter listed. Beyond tables, hashes are everywhere: content-addressed storage and Git name objects by their hash; distributed systems route keys to servers with consistent hashing; Bloom filters (a later chapter) use several hashes at once; checksums and deduplication compare hashes instead of whole files. And the cryptographic cousins secure your passwords, sign your software updates, and anchor every blockchain. The choice of hash — fast versus secure, and how well it mixes — is a decision hiding inside all of them.

Takeaways

A hash function maps a key to an integer, and the only thing that makes one good for a hash table is uniform distribution: it must mix the whole key so that structure in your data can't survive into lopsided buckets. Computing it is $O(k)$ in the key length, paid on every operation, so it has to be fast — which is why tables use non-cryptographic hashes like FNV, polynomial, and SipHash, and save the slow cryptographic ones for security.

With the hash function understood, the hashing tier has one structure left to build on top of it. Sets and multisets are hash tables that store only keys (or keys with counts), and they turn "have I seen this" and "how many of each" into O(1) questions — the subject of the next chapter.