Hash Function Design

Chris Wellons wanted to understand how hash functions work, so he did what a programmer would do: built a tool to generate random hash functions, JIT-compile them to native code, evaluate their statistical properties, and search for good ones automatically. This software-engineering approach to a mathematical problem turned up results that surprised everyone, including Wellons himself.¹

The Prospector

The Hash Prospector generates random integer hash functions — functions that take an N-bit integer and return an N-bit integer, bijectively (no collisions). The bijection property is easy to guarantee: just compose reversible operations. XOR with a constant reverses itself. Addition reverses with subtraction. Multiplication by an odd number reverses with multiplication by its modular inverse. XOR-right-shift, XOR-left-shift, addition-left-shift — all reversible. Chain a random selection of these operations with random constants, and you get a random bijective hash function.¹

The measure of quality is avalanche bias. Flip each input bit one at a time, record which output bits flip, build an N-by-N table of correlations. Ideally, every output bit flips with exactly 50% probability for every input bit — perfect avalanche. The standard deviation from this ideal gives a single bias score. Lower is better.

Wellons initially measured only average avalanche (how many bits flip) and missed a subtlety: some functions flip the right number of bits but always flip the same bits. These pass the average test but produce obvious patterns when hashing a counter. You need the full bias matrix, not just the row sums.

For 32-bit functions, the full bias evaluation requires testing all 2^32 inputs — about an hour and a half. For 64-bit, it's impossible, so you Monte Carlo sample a random subset. This lets you quickly discard terrible candidates and save the exhaustive test for promising ones.

The Multiply-XorShift Construction

After hours of random search, the prospector independently rediscovered a construction that turns out to be well-known: XOR-right-shift, multiply, XOR-right-shift, multiply, XOR-right-shift. The XOR-right-shift diffuses bits rightward, the multiply diffuses bits leftward. Right, left, right, left — "sloshing" the bits back and forth until they're thoroughly mixed.¹

The same structure appears in MurmurHash3's finalizer, in Thomas Mueller's hash function from the H2 SQL database, in SplitMix64. Nobody coordinated this. Multiple people, attacking the problem from different angles, converged on the same five-operation template because it's genuinely optimal for this class of function. The template can be described as a five-tuple: (shift1, multiplier1, shift2, multiplier2, shift3).

Wellons found a function with lower bias than MurmurHash3's finalizer — briefly the least biased 32-bit hash function of this form ever measured:

x ^= x >> 16;
x *= 0x7feb352dU;
x ^= x >> 15;
x *= 0x846ca68bU;
x ^= x >> 16;

Exact bias: 0.17353. For comparison, MurmurHash3 comes in at a fraction higher. With a third multiply-xorshift round, he reached the theoretical bias floor (~0.021) — statistically indistinguishable from a random permutation of all 32-bit integers.

What the Constants Tell You

The interesting thing about the discovered constants is what they aren't. Neither multiplier is prime. Nudging them to the nearest prime increases the bias. The shifts aren't round numbers — 15 bits instead of 16, which feels wrong but measurably isn't. These parameters are local minima in a complicated fitness landscape, and human intuitions about "nice" numbers (primes! powers of two!) are misleading.¹

This is a microcosm of a broader pattern in algorithm design. Human mathematical intuition says primes should be special, round numbers should be natural, symmetry should help. The search landscape says no — the optimal constants are just numbers, with no particular mathematical significance, sitting at the bottom of a bias well that doesn't care about human aesthetics. The multiply-xorshift structure has mathematical justification (complementary diffusion directions), but within that structure, the constants are found empirically, not derived.

The 64-bit case is harder. SplitMix64 (from Java's SplittableRandom) follows the same construction and is roughly optimal at the 64-bit scale, but the search space is too large to exhaustively verify. The prospector found many functions with similar estimated bias but nothing provably better. The landscape at 64 bits seems flatter — there are many good-enough solutions and possibly no dramatic local minimum.

Connections

Hash functions sit at the intersection of several ideas in this wiki. The bias measurement is essentially testing for statistical independence — the same concept that underlies Shannon's Information And Computation framework. A perfect hash function is one where the output has maximum entropy given the input, which is another way of saying the output looks random. The search process itself — generate random candidates, evaluate fitness, iterate — is a simple evolutionary algorithm, connecting to the broader theme of how search processes can discover structure in mathematical spaces.

The multiply-xorshift construction also shows up in PRNG design (SplitMix64 is used to seed other generators), in shader programming (Wellons' functions have been adapted for GLSL noise generation), and in cryptography as capability (where the design criteria differ — constant-time execution matters, and multiplication's variable timing is a liability). The same five operations, with different constants, serve radically different purposes depending on whether you need speed, statistical quality, or cryptographic security. The construction is a chassis; the application determines the tuning.