Fibonacci hashing

A hash table with $2^b$ buckets wants a multiplier that scatters consecutive keys. Knuth’s recommendation is the golden ratio’s reciprocal:

mapping key $k$ to $\bigl\lfloor 2^b\,\{k/\varphi\}\bigr\rfloor$, where $\{\cdot\}$ takes the fractional part.1 Successive keys then land as far from each other as the arithmetic allows: the points $\{k/\varphi\}$ always split one of the current largest gaps, a property in which $\varphi$ is essentially unique.

The reason is the continued fraction. $\varphi = [1;1,1,1,\ldots]$ has the smallest possible partial quotients, which makes it the worst-approximable irrational: by Hurwitz’s theorem every irrational $x$ admits infinitely many $p/q$ with $|x-p/q| < 1/(\sqrt5\,q^2)$, and for $\varphi$ the constant $\sqrt5$ cannot be improved. Bad approximability is exactly what a multiplicative hash wants — no denominator $q$ ever gets close enough to fold the key sequence into clumps.

In code

uint64_t fib_hash(uint64_t k, int b) {
    return (k * 11400714819323198485ull) >> (64 - b);
}

The constant is $\lfloor 2^{64}/\varphi\rfloor$, kept odd so the multiplication permutes the odd residues. Its 32-bit sibling $\lfloor 2^{32}/\varphi\rfloor = \texttt{0x9E3779B9}$ appears anywhere keys need cheap mixing — TEA’s round constant, hash combiners, sequence generators. When you meet those hex digits in a codebase, you are looking at $\varphi$, at the catalog’s address ℵ1618, wearing a different base.