THE FIBONACCI HASH the golden ratio spreads consecutive keys
Multiply by 2^32/φ ≈ 2654435769 and take the high bits. Because the golden ratio is the “most irrational” number, consecutive keys 0,1,2,3 land as far apart as possible — here in buckets 0, 9, 3, 13 of 16, never adjacent. It is the sunflower-seed packing turned into a hash: the same reason phyllotaxis avoids gaps.
THE TECHNIQUE h = (k·2^w/φ) >> (w−bits)
The demo hashes 0,1,2,3 into 16 buckets and shows they scatter maximally: live demo
HISTORY & CREDIT Knuth · golden-ratio hashing
“Consecutive keys always cluster.” — with the golden-ratio multiplier they anti-cluster: each new key falls in the largest remaining gap. cited
the ratio · φ is the hardest number to approximate by fractions, so its multiples never line up. the hash · k·2^w/φ, high bits — the three-distance theorem guarantees even spacing. Knuth · multiplicative hashing with A = 2^w/φ.
Phyllotaxis as a hash function. arithmetic
RECOMMEND FOR I-13 the spread, on the compiler
On i-13, keys 0,1,2,3 land in four distinct buckets, none adjacent:
$ i13 run hs_fibonacci.i13
RUN OK · 85 step(s) · peak stack 3
h0 = 0
h1 = 9
h2 = 3
h3 = 13
all_distinct = 1
Recommend as a NULL — arithmetic (B40) + a pinned function (B39). The even spread is a number-theoretic fact about φ (the three-distance theorem), realized by a deterministic multiply; it is a quality of the constant, not a same-function difference. NULL — the golden ratio, hashed.