A hash is a family, not a function

The probe formula nobody checks measured a hash table’s cost as it filled and found the closed form accurate. It also assumed something it did not examine: that the hash spreads the keys roughly uniformly. Every statement about a hash table’s performance rests on that assumption, it is nearly always left implicit, and it is a statement about the keys rather than about the table.

This essay is about what happens when the assumption fails, and about the standard repair — which is not a better hash function, because there is no such thing as a hash function without a bad input. It is a set of hash functions, and one of them chosen at random.

Every fixed hash has a bad input, by counting #

The reason is not a defect in any particular hash and it is worth getting right, because it explains why the repair has to be structural.

A hash function maps a universe of $U$ keys into $b$ buckets. By the pigeonhole principle some bucket receives at least $U/b$ keys. So for any fixed function there exists a set of $U/b$ keys that all collide — a set that turns the table into a linked list. The set exists for every hash function that has ever been written, including cryptographic ones; the difference between a good hash and a bad one is entirely in how hard the set is to find.

For the low-bits hash it is not hard at all. x & (b - 1) for $b = 256$ depends on the bottom eight bits of the key and nothing else, so the multiples of 256 all map to zero. Nobody has to search: the colliding set is a closed form in the table size.

For multiply-shift it takes one more step and is still a closed form. The function is $h(x) = (a x \bmod 2^{32}) \gg (32 - \ell)$ for an odd multiplier $a$, and $a$ being odd makes it invertible modulo $2^{32}$. So given $a$, compute $a^{-1}$ — five iterations of Newton’s method, $\text{inv} \leftarrow \text{inv}(2 - a \cdot \text{inv})$ — and the keys $x_t = a^{-1}t \bmod 2^{32}$ for small $t$ satisfy $a x_t \equiv t$, which lands them all in bucket zero.

With $a = 332{,}584{,}831$ the inverse is $3{,}605{,}325{,}951$ — their product modulo $2^{32}$ is exactly 1 — and the colliding keys begin 3,605,325,951 · 2,915,684,606 · 2,226,043,261 · 1,536,401,916 · 846,760,571, each one $t$ times the inverse for $t = 1, 2, 3, \ldots$

All 2,048 of them land in bucket zero. Not statistically: by construction, every time.

So the multiply-shift family is not stronger than the low-bits hash against an adversary who knows which function is in use. Its entire strength is that the adversary does not know.

What universality guarantees #

A family $H$ of hash functions is universal if, for any two distinct keys $x \ne y$, choosing $h$ uniformly at random from $H$ gives

$$P[h(x) = h(y)] \le \frac{1}{b}$$

That is the whole definition, and three things about it are worth being exact about because it is routinely over-read.

The probability is over the choice of function, not over the keys. No distribution on the input is assumed. The guarantee holds for the worst pair of keys there is — this is an expected-case guarantee, not an average-case one, and it is the same distinction that separates randomised quicksort from first-element quicksort.

It bounds pairwise collisions and nothing more. Universality says nothing directly about the maximum bucket load, the length of the longest probe sequence, or the distribution’s shape. Those follow, but they follow with extra work and weaker constants.

It does not say collisions are rare in an absolute sense. $1/b$ is exactly the collision probability of a perfectly random map, so a universal family is as good as random on pairs and may be much worse on higher-order structure. Multiply-shift is only 2-approximately universal — its bound is $2/b$ rather than $1/b$ — which costs a factor of two on collision counts and nothing on the asymptotics.

The consequence that makes it useful: with $n$ keys in $b$ buckets, the expected number of colliding pairs is at most $\binom{n}{2}/b$, so the expected number of other keys sharing a bucket with any fixed key is at most $n/b$. That is the load factor, and it is the number every hash table analysis wants — now guaranteed for any key set rather than assumed for a nice one.

The measurement #

Two thousand and forty-eight keys, two hundred and fifty-six buckets, average load 8:

Four readings.

On ordinary keys the two hashes are indistinguishable. 17 against 16 in the worst bucket, 8,334 against 8,059 colliding pairs, both against a uniform-map expectation of $\binom{2048}{2}/256 = 8{,}190$. Any benchmark on ordinary keys reports these as equally good, which is exactly why the low-bits hash gets written and shipped.

The low-bits hash’s bad input is trivially constructible and ordinary. Multiples of the table size are not exotic data: they are pointers, page-aligned addresses, identifiers allocated in blocks, timestamps at a fixed interval. The failure does not require an attacker.

The family survives that same input. Worst bucket 11 against an average of 8, which is an unremarkable table. The keys that destroyed one function have no special relationship to a randomly chosen member of the family.

And it does not survive an input computed against it. The last row is the same 2,048-in-one-bucket catastrophe, from keys derived from the multiplier by modular inversion. Universality is a statement about a random choice, and once the choice is known there is nothing random left.

The two plates above are what the attack looks like. The one below is what everything else looks like, and the pair is the reason the defect survives review: a hash is chosen by measuring it on input somebody had lying around, and on that input the broken function and the sound one are the same function.

The obvious response is to reach for a stronger family, and it is worth measuring because it does not work. Multiply–add–shift draws two parameters rather than one and is universal where multiply–shift is only almost so — a strictly better guarantee, bought for one addition.

That is the whole content of the word family. The strength of the guarantee is a statement about an average over members, and an average over one member is that member.

What it costs #

Universality is unusual among the repairs in this phase in costing almost nothing, which is worth quantifying rather than waving at.

Time. Multiply-shift is one multiplication and one shift. The low-bits hash is one bitwise AND. On any processor built in the last thirty years the multiply is three to five cycles and pipelines, and the difference is invisible next to the cache miss that follows it. Multiply-add-shift adds one addition.

Space. One word per table for the multiplier, or two for multiply-add-shift.

Randomness. Thirty-two bits at table creation, once, and never again. Measured against the other consumers in this phase, that is nothing: a skip list spends two bits per key, so a hash table of a thousand keys spends 32 bits where a skip list of the same size spends 2,000.

The guarantee given up. None, relative to a fixed hash — the fixed hash never had a guarantee, it had an assumption about the keys.

So the comparison against the other randomisations here is stark. A treap pays 32 bits per node and a real space cost to get its guarantee; randomised selection pays a factor of variance; a Bloom filter pays 44% over the floor. Universal hashing pays one multiply and one word. It is the cheapest instance of the pattern in this phase, and it is the one most often left out of real code.

What the maximum load actually does #

Universality bounds pairs, and the quantity a program feels is the longest chain. Those are related loosely enough to be worth measuring separately.

For $n$ keys into $n$ buckets under a fully random map, the expected maximum load is $\Theta(\log n / \log\log n)$ — a very slowly growing function that is easy to mistake for a constant. Measured, with a multiply-shift member on ordinary keys:

The worst bucket grows by one each time the table quadruples, which is the shape the formula predicts, and it stays small enough over any practical range that treating it as a constant is defensible — provided the constant is understood to be about six rather than about one.

The empty column is the other half of the same picture and it surprises people: about 37% of buckets are empty when a table has as many keys as buckets. That is $e^{-1}$, and it is the reason a hash table at load factor 1 is not “full” in any useful sense. Both numbers come from the same Poisson approximation and both are properties of randomness rather than of the hash.

The three families, and what separates them #

The site’s library carries three maps from key to bucket, and the differences between them are small in code and large in what they guarantee.

lowBits — x & (b - 1). Not a family at all: there is exactly one function in it, so there is nothing to choose at random and nothing an adversary has to learn. It is here as the control, and it is the one people write when the table size happens to be a power of two and masking looks like the obvious thing.

multiplyShift — $(a x \bmod 2^{32}) \gg (32-\ell)$ for random odd $a$. Dietzfelbinger’s family. Two instructions, 2-approximately universal, and the one a fast hash table actually uses. Its weakness is structural rather than statistical: because the map is linear in $x$, the difference $h(x) - h(y)$ depends only on $x - y$, so keys in arithmetic progression land in buckets in arithmetic progression. That is invisible in a collision count and is exactly what made the Bloom filter measurements go wrong on consecutive keys.

multiplyAddShift — $((a x + b) \bmod 2^{32}) \gg (32-\ell)$ for random odd $a$ and random $b$. One extra addition buys strong universality: the pair $(h(x), h(y))$ is close to uniform over all pairs of buckets, not merely unlikely to be equal. Analyses that need pairwise independence — most load-balancing arguments, and the Bloom filter’s assumption that its $k$ probes behave independently — want this one.

The progression is worth reading as a general shape. Each step costs one instruction and buys one more property, and the property bought is always about higher-order structure in the input rather than about the average case. None of the three differs measurably on keys with no structure, which is why the choice between them cannot be made by benchmarking.

What to do about it #

The practical guidance is short and it is mostly about when.

Choose the member at run time, not at compile time. A family whose multiplier is a named constant in the source is a fixed function. This is the single most common way the repair is applied and undone in the same breath, and it is what the next essay is about.

Choose it per table, not per program. One multiplier used by every hash table in a process means one colliding set breaks all of them. Per-table selection costs one word.

Use a family with the properties the analysis needs, not just any randomisation. Multiply-shift is universal and gives collision bounds. It is not strongly universal — the pairs $(h(x), h(y))$ are not uniform over all pairs of buckets — and analyses that need pairwise independence, such as some load-balancing arguments, want multiply-add-shift or tabulation hashing instead. The difference costs one addition.

Do not confuse a good avalanche with a family. A hash with excellent mixing — one where flipping one input bit changes half the output bits — is still one function, and still has its $U/b$ colliding keys. Avalanche makes them harder to find by hand and does nothing about someone who inverts the function or searches for collisions offline. The two properties are orthogonal, and “the hash has good avalanche” is not an answer to “what happens when the keys are chosen against it”.

And know that none of this is a cryptographic guarantee. An adversary who can observe timing can learn about the multiplier without being told it: a slow response reveals a collision, and enough collisions constrain $a$. Universality defends against an adversary who chooses keys in advance, not against one who probes adaptively and watches the clock. If that is the threat, the answer is a keyed cryptographic hash — SipHash exists for exactly this — and it costs several times more per key.

A fourth family, and why it is the modern answer #

The three families above are a progression in instructions bought and properties gained, and there is a fourth that leaves the progression rather than extending it.

Tabulation hashing. Split the key into $c$ bytes. Keep $c$ tables of 256 random 32-bit words, filled at construction. The hash is the exclusive-or of the $c$ table entries indexed by the key’s bytes — four lookups and three exclusive-ors for a 32-bit key, and no multiplication anywhere.

It is 3-independent, which is one degree more than multiply-add-shift, and its real advantage is not the degree. Properties are provable about it that are not provable about the multiplicative families: bounds on the maximum bucket load, on the behaviour of linear probing, and on Bloom-filter false-positive rates all hold for tabulation hashing and are open or false for multiply-shift. The reason is structural — the multiplicative families are linear in the key, so arithmetic progressions in the input become arithmetic progressions in the output, which is the weakness the third family’s description names and which no amount of extra degree removes.

The costs are a kilobyte of tables per hash and a memory access per byte of key rather than a register operation. On a modern processor the tables are in cache after the first few keys and the whole thing is competitive with a multiply; on a memory-constrained device a kilobyte is not free.

Naming it here rather than measuring it is deliberate: it is a different construction, its advantages are theorems rather than measurements, and quoting somebody else’s numbers beside the ones on this page would be mixing two kinds of statement. What can be said from the sections above is that the choice between families cannot be made by benchmarking on ordinary keys — all four are indistinguishable there — so it has to be made from what is provable, and tabulation is where the provable statements are.

What the load factor is chosen against #

The two numbers at the end of the maximum-load section — a worst bucket of about six and 37% of buckets empty at a load factor of one — invite a question the essay has not answered: why do real tables resize at 0.75 rather than at 1?

Not because of the maximum load. Under chaining the longest chain grows like $\log n / \log\log n$ whatever the load factor is, so 0.75 buys almost nothing there.

It is chosen against the probe formula, and that formula is about open addressing rather than chaining. The expected probes for an unsuccessful linear-probing search is about $\tfrac12\bigl(1 + 1/(1-\alpha)^2\bigr)$, which is 8.5 at $\alpha = 0.75$, 50.5 at $\alpha = 0.9$ and unbounded as $\alpha \to 1$. Three quarters is where that curve is still gentle and just before it turns vertical, and it is the number every implementation inherited.

So a chained hash table resizing at 0.75 is using a threshold derived for a structure it is not, which is a harmless inheritance and an instructive one. The number is right for the wrong reason, nobody re-derives it, and a chained table could comfortably run at a load factor of two — its chains would average two and its longest would still be about six.

That also explains a detail of the essay’s own measurements. Every table here is at a load factor of eight, which no open-addressed table could survive and which a chained one handles without comment, and the reason the plates look unremarkable is that the quantity being stressed is not the one 0.75 was chosen to protect.

The pattern, one level up #

This is the third instance in this phase of one shape, and it is worth stating in the general form because it is a design technique rather than three facts.

An algorithm makes a choice — a pivot, a root, a bucket — and if the input can predict the choice, the input can construct the worst case. Randomising the choice does not make the worst case impossible; it makes it independent of the input, and it moves the guarantee from “true of most data” to “true of all data, most of the time”.

The hashing instance is the cleanest of the three because the adversary’s work is a closed form rather than an argument. Given the function, the colliding keys are $a^{-1}t$ for $t = 1, 2, 3, \ldots$ — no search, no heuristic, five multiplications to get the inverse and one per key after that. That is what “the input can predict the choice” looks like when it is written down completely, and it is why the defence has to be that the choice is genuinely unknown rather than merely complicated.