THE FNV HASH — a dart

THE FNV HASH xor a byte, multiply by a prime

FNV-1a walks the bytes: xor the byte into the accumulator, then multiply by a fixed prime. The xor-before-multiply order gives good avalanche — flip one input bit and the whole hash changes. Simple enough to write from memory, and it is everywhere (DNS, hash tables, checksums). Here “hi” and “hj” — one byte apart — hash to 3864218 and 3863815.

THE TECHNIQUE h = (h ⊕ byte) · prime

The demo runs a 24-bit FNV-1a (reduced so the multiply stays exact in i-13’s f64); the full 32-bit form needs a wider integer: live demo

HISTORY & CREDIT Fowler, Noll & Vo · 1991

“FNV-1 and FNV-1a are the same.” — FNV-1 multiplies then xors; FNV-1a xors then multiplies, and the a-order avalanches better. cited

the xor · h ^ byte folds the byte in first.
the prime · · 16777619 (32-bit) scatters it across the word.
1991 · Glenn Fowler, Landon Curt Noll & Kiem-Phong Vo — a hash you can memorize.

Two operations per byte, and it avalanches. arithmetic

RECOMMEND FOR I-13 avalanche, on the compiler

On i-13 (24-bit FNV-1a), a one-byte change moves the whole hash:

$ i13 run hs_fnv.i13 # 24-bit FNV-1a (exact in f64) RUN OK · 131 step(s) · peak stack 6 hi = 3864218 hj = 3863815 -- one byte apart avalanche = 1

Recommend as a NULL — arithmetic (B40) + a pinned function (B39). Avalanche is a quality of the map, not an invariant two mechanisms can differ on; any correct FNV-1a returns the same digest. The 32-bit width overflows f64, so i-13 runs a 24-bit form or needs bignum — a width limit, not a keeper. NULL.