Hash Functions for Table Indexing: Mixing, Avalanche, and Universal Families

A table hash function has a narrower job than a cryptographic one and a wider job than “return an integer”. It must be cheap, deterministic within a process, and well behaved against the specific bit patterns that real keys produce. Getting this wrong does not produce incorrect results, which is what makes it dangerous: the table still works, and lookups quietly cost ten times what they should.

The requirement is distribution, not randomness

Correctness needs only that equal keys hash equally. Performance needs more. The formal property that makes the analysis work is universality: a family of hash functions H is universal if, for any two distinct keys x and y, the probability over a random choice of h ∈ H that h(x) = h(y) is at most 1/m. Under that condition the expected chain length or probe count bounds derived in separate chaining hold, whatever the input distribution.

Two practical consequences follow. First, a fixed hash function cannot be universal in the useful sense, because an adversary who knows it can choose keys that collide. Second, a hash that is uniform on random input may be badly non-uniform on structured input. Integer keys from a counter, pointers from an allocator, and strings that share a long prefix are all structured, and they are the common case.

The property that measures resistance to structured input is avalanche: changing one input bit should change each output bit with probability close to one half. Perfect avalanche is stronger than needed for table indexing, but the practical target is that no input bit is ignored and no output bit is a simple function of a few input bits.

Why identity hashing collapses on a power-of-two table

Take a table of m = 2^b slots and a hash that returns the key unchanged. The index is the low b bits of the key. If keys are sequential integers, indices are sequential and distinct, which looks acceptable until the keys are pointers: heap allocators align objects to 8 or 16 bytes, so the low 4 bits of every pointer are zero. A table with 16 slots would place every pointer in slot 0.

The failure is not subtle in the aggregate. The high bits of the key, which do vary, are discarded by the modulo, and the low bits, which do not, are all that remain. Even without alignment, keys that differ by a multiple of m collide, so an arithmetic sequence with stride m produces a single chain of length n.

Prime table sizes mitigate this, because a modulo by a prime folds all bits of the key into the result. That is why implementations that cannot afford a good mixing function choose a prime modulus and accept the division cost. When the table size is a power of two, the mixing must happen in the hash function, and it must move high bits downward.

Multiply-shift and Fibonacci hashing

The cheapest way to spread sequential keys is to multiply by a constant and take the high bits. With a 64-bit word and a table of 2^b slots:

/* Fibonacci hashing: the high b bits of k * 2^64/phi */
static inline size_t fib_index(uint64_t k, unsigned b)
{
    return (size_t)((k * 0x9E3779B97F4A7C15ULL) >> (64 - b));
}

The constant is the 64-bit truncation of 2^64/φ, the golden ratio. Multiplication by an odd constant is a bijection on 64-bit words, so distinct keys map to distinct products; taking the top b bits then partitions that space into 2^b buckets. The golden ratio is the continued-fraction convergent that is worst approximated by rationals, which is how Knuth justified it as the multiplier that keeps images of an arithmetic progression of keys as evenly spaced as possible. The operation is a single multiply and shift, no division, and keys that differ by small amounts land far apart in the index space.

The weakness is that the top bits of the product depend on all bits of the key only through the carry chain of the multiplication, and multiplication is not a strong mixer. Keys that differ in a single low bit produce products that differ in a predictable pattern. Multiply-shift is adequate for sequential counters and for pointer values after a shift, less so for arbitrary 64-bit keys.

The family form, due to Dietzfelbinger and others, is h(k) = ((a·k) mod 2^w) >> (w - b) for a random odd a. Choosing a at random per table gives a universal family with the same single-multiply cost, and it removes the adversarial predictability of a fixed constant.

Finalizers for arbitrary words

When keys are already well distributed but correlated, a finalizer is the right tool: a short sequence of multiplies, shifts, and xor-shifts applied to the raw hash. The widely copied MurmurHash3 64-bit finalizer is:

static inline uint64_t fmix64(uint64_t k)
{
    k ^= k >> 33;
    k *= 0xff51afd7ed558ccdULL;
    k ^= k >> 33;
    k *= 0xc4ceb9fe1a85ec53ULL;
    k ^= k >> 33;
    return k;
}

Each xor-shift propagates high bits into low bits; each multiply by a constant with a dense bit pattern spreads them further. Three rounds are enough that every output bit depends on every input bit, and the cost is a handful of cycles. Java’s HashMap applies a weaker variant to String.hashCode results, mixing the top 16 bits into the bottom 16 with a single xor and shift, precisely because string hashes concentrate in the low bits while the table index uses the low bits.

A finalizer does not make a bad hash good. It scrambles the output of a hash that already captures the key’s entropy. Applying it to an identity hash of aligned pointers helps, but applying it to a hash that discarded information cannot recover what was lost.

Strings, and the cost of touching every byte

String keys require reading the whole string, which is the dominant cost for short keys. The classic choices are polynomial hashes and FNV.

A polynomial hash treats the string as coefficients of a polynomial and evaluates it modulo a word: h = h·p + c per byte, with p a small odd constant. Java specifies p = 31 for String.hashCode, which is why the hash of "Aa" equals the hash of "BB": both are 31·65 + 97 and 31·66 + 66. The collision is harmless in a table that mixes the result, and it is a reminder that polynomial hashes over small multipliers have structured collisions.

FNV-1a uses h = (h XOR c) · p with a 64-bit offset basis of 14695981039346656037 and prime 1099511628211 (the 32-bit pair is 2166136261 and 16777619). The xor before the multiply ensures that a zero byte still changes the state, and the large prime gives good dispersion. FNV is fast and simple but has no randomness, so its collisions are computable by anyone who knows the algorithm.

The alternative is to hash with a keyed function, which is the only defence that survives an adversary choosing keys. That design and its cost are the subject of hash flooding.

Distributing one hash across several uses

A 64-bit hash contains enough entropy to derive several independent values, which matters when the table needs an index and a probe stride, or an index and a fingerprint. Splitting the word is cheaper than computing a second hash:

uint64_t h = hash(key);
uint32_t idx  = (uint32_t)h;          /* low half: slot index */
uint32_t step = (uint32_t)(h >> 32) | 1;  /* high half: odd stride */

Reusing bits this way is only safe if the two halves are independent, which a good finalizer ensures and a weak hash does not. For double hashing the derived stride must be coprime with the table size; forcing it odd handles a power-of-two table, and a prime table needs a stride in [1, m-1].

The remaining constraint is stability. A hash used to place keys in an in-memory table may change between runs, and randomized hashing relies on that. A hash used to compute a persisted index, a shard assignment, or a checksum-verified key must be fixed forever, because changing it silently invalidates stored placement. Implementations that need both properties keep the two functions separate and never substitute one for the other.

A table hash is therefore a contract with three clauses: equal keys hash equally, distinct keys distribute according to a family the analysis can bound, and the cost stays within a few cycles per key. Every design choice above trades one clause against another, and the choice is only wrong when it is made by accident.