What makes a good hash function?

Hash functions are the most-used and least-examined tool in software. You have called one a few thousand times today without noticing: every dictionary lookup, every cache hit, every git commit leaned on one. They are the plumbing of computing, and like plumbing, nobody thinks about them until something backs up.

The job description is short. A hash function eats some data and returns a fixed-size number. Feed it "hello" and you get 0x5d41402a; feed it the complete works of Shakespeare and you get another fixed-size number, no larger. Since the inputs are unlimited and the outputs are not, two different inputs must occasionally land on the same number. That collision is the central fact of the whole subject, and almost everything that separates a good hash from a bad one comes down to how rarely collisions happen and how evenly the outputs are spread in the first place.

Where hash functions live

Hash tables use them to pick a bucket. Databases use them to build indexes. Git names every commit after the hash of its contents. Caches, deduplicating backups, Bloom filters, digital signatures, content-addressed storage, the occasional blockchain. All of it rests on the same trick. When a program does something fast that ought to be slow, there is usually a hash function holding it up.

The trick is indirection. Rather than search a collection for an item, you compute a number from the item that tells you where it should be. It is the difference between wandering the shelves of a library and looking the title up in the catalogue first. The catalogue is just arithmetic, and every so often two different books get filed under the same number.

Speed comes first

For almost everything on that list, the first thing you want from a hash function is raw speed. Filling a hash table with a million items means a million hash computations, and the gap between a nanosecond and a microsecond per call is the gap between an instant and a visible stutter.

Password storage is the deliberate exception, where you want the hash to be slow (an attacker grinding through billions of guesses against a leaked database should suffer far more than the server checking one honest login), but that is a separate craft with its own name, the key stretching function, and we will come back to it.

What makes a good hash?

Before taking a hash function apart, it is worth being clear about what it is supposed to do. The arithmetic inside is not arbitrary; it is chosen to hit a few specific properties, and those few properties are what every design gets measured against.

Uniform distribution

A good hash spreads its outputs evenly across the whole range. Hash a million distinct inputs through a 64-bit function and you want the results scattered across the full 2^64, not huddled in one corner of it.

The reason is in how the output gets used. A hash table with 1024 buckets usually picks one with hash % 1024, so if the function quietly prefers certain bit patterns, some buckets overflow while others sit empty, and the constant-time lookup you were promised slides back towards a linear scan.

The awkward part is that real inputs are nothing like uniform. Names pile up around common spellings, file sizes around powers of two, IP addresses around the populated ranges. A good hash swallows all that structure and still hands back something that looks random. Turning lumpy input into smooth output is most of the job.

The avalanche criterion

This is the property that most cleanly tells a good hash from a bad one. The avalanche criterion says that flipping a single input bit should flip about half the output bits, each one changing independently with probability one half. Put another way: every input bit should be able to reach every output bit.

The name is the mechanism. A one-bit nudge at the input sets off a cascade that, by the time the computation finishes, has touched everything. Change one character in a document and a good hash of it should look unrelated to the original, not similar-with-one-edit but different all the way through.

The test writes itself: hash an input, flip one bit, hash again, count the output bits that differ. A good function changes around half of them; a bad one changes a handful, or the same predictable handful every time.

fn test_avalanche(hash: impl Fn(u64) -> u64, input: u64) {
    let original = hash(input);
    for bit in 0..64 {
        let flipped_input = input ^ (1 << bit);
        let flipped_hash = hash(flipped_input);
        let changed_bits = (original ^ flipped_hash).count_ones();
        // For a good hash, changed_bits should be around 32 (half of 64)
        println!("Flip bit {}: {} bits changed", bit, changed_bits);
    }
}

Run that against a deliberately terrible function (the identity, say, or XOR with a constant) and flipping input bit N moves only output bit N. For a hash table that is fatal: inputs that differ only in their high bits all crowd into the same buckets.

Diffusion

Diffusion is the machinery that produces avalanche: each input bit’s influence spreading out across all the output bits. Without it the bits stay in their lanes (a change in bit 47 affects only bit 47), and no amount of wishing gets you to avalanche.

Operations differ wildly in how much they diffuse. XOR offers none; multiplication offers a great deal. Most of hash design is the craft of bolting cheap operations together so that full diffusion shows up in as few steps as possible.

The birthday paradox

Collisions turn up far sooner than feels fair. With an n-bit hash, how many inputs can you push through before a collision is likely? The tempting answer is about 2^n. The real answer is roughly 2^(n/2) (the square root of the output space) for an even-money chance.

This is the birthday paradox. In a room of 23 people, there’s a 50% chance two share a birthday: not because 23 is close to 365, but because there are 253 pairs of people. Collisions are about pairs, and pairs grow quadratically.

For a hash table none of this bites; you are not storing 2^32 items, and a few collisions cost almost nothing. For content-addressed storage or deduplication, where billions of items are compared by hash alone, a 64-bit output is alarmingly small. It is part of why Git reached for 160-bit hashes and why content-addressed systems keep their digests long.

The toolkit

Hash functions are built from a small kit of primitive operations, each a different sort of mixer with its own strengths and failings. Knowing what each one brings explains why real designs are shaped the way they are.

The input/output bit diagrams in this section measure diffusion. Each cell is the probability that flipping one input bit (its column) flips one output bit (its row), and the colour is there to flag the bad probabilities. The ideal is an independent 50% on every cell, a true coin-flip and exactly what avalanche asks for, so that midpoint is painted a neutral white and a cell doing its job barely shows up.

Colour only creeps in as a cell strays toward one of the two failures: a cold blue cell means that input bit barely moves that output bit (under-mixing, drifting toward 0%), while a hot red cell means it flips that output bit every single time (a rigid, deterministic link pinned near 100%). Strong colour of either kind marks a defect: a thoroughly mixed function leaves a near-blank white field, and the diagrams only light up where the mixing has failed. Hover any cell for its exact probability.

XOR: combining without bias

XOR is the workhorse. It merges two values bit by bit (1 where they differ, 0 where they agree), and its great virtue is that it does so without introducing bias: if either operand is uniformly random, the result is uniformly random no matter what the other one is.

fn xor_combine(a: u64, b: u64) -> u64 {
    a ^ b
}

Its matching vice is that it provides no diffusion whatsoever. Output bit 0 depends only on input bit 0; output bit 47 only on bit 47. XOR two values that differ in a single bit and the result differs in exactly that bit: the anti-avalanche, in one instruction.

XOR is also its own inverse: a ^ b ^ b = a. That makes it perfect for combining values reversibly, and useless for making anything harder to reverse. It shuffles entropy between operands; it never moves it between bit positions.

So XOR earns its keep by combining the outputs of operations that do diffuse. The pattern you see again and again is multiply, XOR, multiply again: the multiplications fling bits across positions, and the XOR folds the results together.

Rotation and shifts: repositioning bits

Since XOR cannot move information between positions, a hash needs a separate operation that can. Rotation slides every bit along and wraps the ends around, so nothing is lost:

fn example_rotate(x: u64) -> u64 {
    x.rotate_left(17) // bit 0 moves to position 17; the top bits wrap to the bottom
}

Rotate before XORing and positions that were strangers a moment ago can suddenly interact:

fn xor_rotate(a: u64, b: u64) -> u64 {
    a ^ b.rotate_left(17)
}

This XOR-rotate pairing turns up all over hash and cipher design. Rotation realigns the bits, XOR combines them; it is one instruction, reversible, and gives controlled mixing across positions.

Shifts (>> and <<) look similar but throw away the bits that fall off the end rather than wrapping them. A right shift by 32 drops the low 32 bits on the floor. Sometimes that is exactly what you want (dragging the high bits down to where they can meet the low ones), but it destroys information rather than merely relocating it.

Addition: the carry chain

Modular addition (addition that wraps on overflow) manufactures dependencies between positions that XOR cannot, through the carry chain.

fn add_example(a: u64, b: u64) -> u64 {
    a.wrapping_add(b)
}

When two set bits collide, the position emits a 0 and carries a 1 upward. That carry can keep going: add 1 to 0xFFFFFFFF and all 32 bits flip at once. So output bit n depends on every input bit from 0 up to n: influence flows upward, from low positions to high. Call it vertical diffusion.

The snag is that the flow only ever goes one way. A carry never travels downward, so the high input bits cannot touch the low output bits. That is why addition so often travels with rotation: rotate to bring the high bits down to the bottom, then add to push influence back up.

Multiplication: comprehensive mixing

Multiplication is the strongest mixer in the basic kit. Multiply two 64-bit values and each output bit ends up depending on many input bits from both operands, because a multiply is really shift-and-add carried out for every set bit at once: every position gets a chance to interact with every other.

fn multiply_example(a: u64, b: u64) -> u64 {
    a.wrapping_mul(b)
}

Output bit n of a × b depends on input bits 0 through n of both operands, so while the lowest bit only depends on one bit, the high bits of the result depend on essentially everything. One multiply does the work of several XOR-rotates.

The catch is that the constant matters enormously. Multiply by 2 and you have just done a left shift, mixing nothing; multiply by a constant with only a few set bits and influence barely spreads; multiply by zero and your hash collapses to all zeros. Good multipliers are odd (which makes them coprime to 2^64, so the operation is a bijection and loses no information), carry roughly half their bits set, and avoid any obvious pattern.

The first diagram averages over every possible multiplier, so it flatters the operation: it shows multiplication’s potential rather than any real constant. Production code uses a fixed constant, and the later diagrams show the cost: even a well-chosen constant leaves a bare triangle, because carries still only climb and the high input bits never reach the low output bits.

The sharper problem is zero. Anything times zero is zero, and every bit of that hard-won diffusion vanishes in an instant. If an attacker can force one operand to zero at the wrong moment, the output becomes predictable no matter what the other operand was. This zero-collapse is not theoretical: it has been the root of real attacks on hashes that were careless about what they fed into a multiply.

The folded multiply

This one is newer, and it is what the fastest modern non-cryptographic hashes are built around. A 64-bit CPU multiply can produce the full 128-bit product, and instead of binning the upper half the way ordinary 64-bit multiplication does, the folded multiply XORs the two halves together:

fn folded_multiply(a: u64, b: u64) -> u64 {
    let product = (a as u128) * (b as u128);
    let high = (product >> 64) as u64;
    let low = product as u64;
    high ^ low
}

The low half of the product holds the interactions among the low input bits; the high half holds the ones involving the high bits, including exactly the carries that plain multiplication throws away. Fold the halves together with XOR and almost every output bit ends up shaped by almost every input bit of both operands.

The averaged version is close to uniform, and even with a fixed constant the fold reclaims most of the bare triangle that plain multiplication left behind, though a few positions stay weaker than the rest. One folded multiply is good; two or three in a row are better.

All of which buys near-complete diffusion in a single cheap operation; x86 even has a dedicated full-width multiply (mulx) for it. Strip a great many of the fastest non-cryptographic hashes down to their core and you find a carefully arranged run of folded multiplies and XORs.

The fold does inherit zero-collapse from ordinary multiplication: if either operand is zero the 128-bit product is zero, and XORing two zero halves still leaves zero. Anything built on folded multiplies has to stop an attacker forcing a zero operand at a point where it counts.

Putting it together: FxHash

No single operation diffuses cleanly on its own, so a real hash chains a few of them and lets a long input keep the loop turning. FxHash is about as direct as that gets. It is the hash behind Firefox and rustc’s FxHashMap, and its entire per-word step is three operations from this section in a row: rotate the running hash, XOR in the next word of input, then multiply by a fixed constant.

const K: u64 = 0x517cc1b727220a95; // odd, with a good spread of bits

fn fxhash_step(hash: u64, word: u64) -> u64 {
    (hash.rotate_left(5) ^ word).wrapping_mul(K)
}

Each operation pulls exactly the weight the toolkit predicted. The multiply does the heavy diffusion but only ever pushes influence upward, leaving the empty triangle where high bits never reach low ones. The rotate-left is the cure: it slides the high bits back down to the bottom, so the next word’s multiply can lift them again from there. The XOR folds in the new word without bias. Rotate to reposition, XOR to combine, multiply to spread, the same loop most fast hashes run, written about as plainly as it ever gets.

There are no fixed rounds to count, though. FxHash runs that step once per word and never circles back, so how well a given bit of input ends up mixed comes down to how early it arrived. A bit in the very last word is XORed in and meets only the closing multiply on its way out, which is the bare multiply triangle again: the low bits climb, the high bits go nowhere. A bit a few words earlier survives that many more rotates and multiplies, each rotate handing the high bits to the next multiply, until its influence has reached everywhere. The diagrams shrink the step to eight bits, the way the multiply diagrams did, and walk backwards from the end of the input:

That is the whole personality of FxHash. The early words of a key get thoroughly mixed; the last word or two barely at all, because there is no finalising pass to even them out. It is a deliberate trade: one rotate-XOR-multiply per word and nothing spare is exactly what makes FxHash so fast (and, not unrelatedly, predictable enough to be a poor choice the moment an adversary is choosing the keys). A handful of cheap operations, run once each and no more, is what most non-cryptographic hashing comes down to.

Different jobs, different hashes

No single hash is right for every job. What a hash table wants and what a digital signature wants barely overlap, and reaching for the wrong kind is a dependable way to ship a bug that only shows up under load, in production, at the worst possible moment.

What a hash table actually wants

Start with the most common job. For a hash table a collision is a nuisance, not a disaster: two items share a bucket, the table compares both, and performance sags gracefully from constant-time towards linear as collisions pile up. You want uniform distribution and good avalanche, and that is the whole list. Cryptographic strength buys you nothing here.

What you do want, badly, is speed, because the table calls the function on every insert, lookup, and delete. A hash that is 10% faster makes the structure 10% faster on its hottest path. This is the entire reason hash tables do not use SHA-256: it would be like fitting a bank-vault door to a kitchen cupboard, slower to open and guarding against a threat that, for an ordinary hash table, simply is not there.

When the input is adversarial

Until it is. In 2011, researchers showed you could topple a web server by sending it requests whose keys all hash to the same bucket. The table collapses from constant-time to linear, the server starts doing quadratic work on input the attacker picked for free, and over it goes. This is HashDoS, and the later articles in this series take it apart in detail; the short version is that a fast, predictable hash turns into a liability the moment your inputs arrive from strangers.

The defence is keyed hashing: fold a secret value (a key, or a seed) into the computation, so an attacker cannot work out which inputs collide. Pick a fresh random seed when the program starts and the pre-baked collision set is worthless.

What you are reaching for here has a name: a pseudorandom function, or PRF. A PRF takes a key and an input and returns output that looks random to anyone who does not hold the key, which is precisely the property a HashDoS-resistant table needs, since an attacker who cannot predict the output cannot engineer collisions. SipHash is the popular example: a keyed PRF, fast enough to live on a hash table’s hot path yet built so that, without the key, finding collisions is hopeless. It is the default hasher in a lot of languages now, and it helps to see it for what it is: a cryptographic primitive sized for hash tables, rather than a general-purpose cryptographic hash like SHA-256 jammed into the role.

Not every defence is as solid as it looks. Some hashes that took a seed turned out to have seed-independent collisions (input pairs that collide whatever the seed is), so the protection engineers thought they had bought was never actually there. Several MurmurHash, wyhash, and rapidhash variants had exactly this problem, and it is a recurring theme later in the series.

Stable or ephemeral?

There is a second axis here, orthogonal to security, and mixing it up is its own class of bug. Sometimes an input must hash to the same value forever, on every machine and every run. This is stable or portable hashing, and distributed systems live on it: every node has to agree on which shard owns a key, and in content-addressed storage the hash is the name of the data.

Other times you want the exact opposite, a fresh mapping on every run, which is precisely what foils HashDoS. This is ephemeral hashing, and it is why Rust’s standard library randomises its hash seed by default.

The failure mode is using one where you needed the other. Pick a randomised hash for a distributed sharding key and your nodes quietly disagree about who owns what. Pick a stable hash for untrusted request parameters and you have hand-delivered HashDoS straight back to the attacker.

The cryptographic kind

SipHash earned the word “cryptographic” on a narrow technicality: keep the key secret and the attacker is stuck. The classic cryptographic hashes (SHA-256, SHA-3, BLAKE3) are playing a much harder game. They are unkeyed, so the attacker knows everything about how they work, and they still have to hold up. They get there by brute persistence: SHA-256 runs 64 rounds of its compression function where a fast non-cryptographic hash might only do a handful of operations in total.

In exchange they promise three properties that go well past uniform distribution and avalanche, and real systems lean on each one.

Preimage resistance. Given only an output, you cannot find any input that produces it: not just the original, any input at all. It is why a server can store the hash of your password rather than the password itself: even a fully leaked database of hashes does not hand the passwords back. There is a catch, which is that passwords carry so little entropy that an attacker can simply hash every likely guess, something a fast one-way function does nothing to slow down, so real password storage uses a slow, salted hash rather than a bare SHA-256.

Second-preimage resistance. Given a specific input and its hash, you cannot find a different input with the same hash. It sounds like the previous property wearing a new hat, but it is a distinct and harder-to-exploit one: the attacker now has a concrete file in hand to study. This is what integrity checks lean on. When you verify a download against a published hash, you are betting nobody could take the genuine file and forge a malicious twin with a matching hash.

Collision resistance. You cannot find any two distinct inputs that hash to the same value. This is the strongest of the three, because the attacker chooses both inputs and so has the most room to manoeuvre. The birthday paradox sets the bar uncomfortably low: a collision is expected after about 2^(n/2) tries, not 2^n, so a 128-bit hash offers only around 2^64 of collision resistance, within reach of hardware that does billions of hashes a second, which is why serious hashes run to 256 bits and beyond. Collision resistance is what stands behind digital signatures: you sign a document by signing its hash, so anyone who can find two documents with one shared hash (a loan agreement for £100 and one for £100,000, say) can lift your signature off the first and drop it onto the second.

The three sit in a hierarchy. Collision resistance is the hardest to keep, and being able to find collisions can crack the door open for the other attacks. Real hashes have tended to fall in that order: collisions first, in theory and then in practice, with preimage attacks trailing far behind if they arrive at all. MD5’s collision resistance fell in 2004; its preimage resistance is dented but, twenty years on, still standing.

The practical reason any of this matters is cost: a cryptographic hash runs perhaps 5 to 20 times slower than a good non-cryptographic one. Spend that on populating a hash table and you are paying for protection against an adversary who never shows up.

The deliberately slow kind

Which brings us back to the hashes that are slow on purpose. Passwords are the headline case. Because a password carries so little entropy, the only real defence is to make each guess expensive, so the key stretching functions (bcrypt, scrypt, Argon2) are engineered to be slow, and the newer ones memory-hungry too, so that an attacker with a warehouse of GPUs gains as little as possible over the server checking a single login.

They sit inside a broader family of key derivation functions, or KDFs, whose job is to turn one secret into usable key material: stretching a weak password into a key, or expanding a single shared secret into a fistful of independent ones (HKDF being the usual choice). It is the same hashing machinery (diffusion, irreversibility) aimed at a different target and tuned for a different notion of “good”. Fast is a feature in a hash table and a bug in a password hash.

Hash functions and random numbers

The link between hashing and randomness is more than a cute analogy; it shapes how operating systems actually make random numbers.

The properties that make a hash good are the ones a pseudorandom number generator (PRNG) needs: avalanche, so a small change in input scrambles the output; uniform distribution, so the output is indistinguishable from random; and irreversibility, so nobody can run it backwards to the seed. Both constructions are trying to produce output that looks random and resists analysis, so the techniques cross over freely.

ChaCha20, which generates secure random numbers in most operating systems and crypto libraries, is essentially a keyed hash (a PRF again) run in counter mode: hand it a key and a counter, get random-looking output; bump the counter for more. Its core is nothing but add, rotate, and XOR, followed by a feed-forward step that adds the initial state back into the mixed state. That final addition is what makes the function non-invertible, the one-way property turning up where you least expect it.

The Linux kernel wears the connection on its sleeve. Version 4.8 (2016) moved random number generation to ChaCha20; version 5.17 (2022) adopted BLAKE2s, a member of the BLAKE hash family, for the entropy pool that seeds it. Hash functions all the way down.

Mostly just mixing

A hash function looks trivial, turns intricate the moment you open it up, then settles back into something simple from a higher vantage point. Turning data into a number quickly is easy. Making that number uniform, wildly different for nearly identical inputs, and cheap to compute is where all the engineering hides.

Avalanche and diffusion are the centre of gravity. Every other decision (which operations, in what order, with which constants) bends towards one goal: spreading each input bit’s influence across every output bit. The fast hashes, the keyed ones, the cryptographic ones, the deliberately slow ones, are all the same stirring motion, run at different speeds, for different goals, against different fears. The trick is mostly knowing which job you are doing before you reach for one.