If the key set is known and fixed, you can find a hash with no collisions at all — O(1) worst-case lookup, guaranteed. The FKS scheme searches multipliers until the set maps injectively (a two-level version squeezes it to O(n) space). Here for keys {10,22,37} into 5 buckets, multiplier a=1 and a=2 collide, but a=3 is perfect: buckets 0, 1, 4.
THE TECHNIQUE find a: ((a·k) mod p) mod m injective on S
The demo searches a for {10,22,37} in 5 buckets and finds the first collision-free one: live demo
HISTORY & CREDIT Fredman, Komlós & Szemerédi · 1984
“Perfect hashing needs huge tables.” — the FKS two-level scheme achieves zero collisions in O(n) space and O(1) worst-case lookup. cited
the search · try multipliers until ((ak) mod p) mod m is injective on the set. two levels · FKS: an outer hash, then a collision-free inner table per bucket — O(n) space. 1984 · Michael Fredman, János Komlós & Endre Szemerédi — O(1) worst case.
No collisions, by construction. data structure
RECOMMEND FOR I-13 the perfect a, on the compiler
On i-13, a=1 and a=2 collide; a=3 maps {10,22,37} to distinct buckets 0,1,4:
$ i13 run hs_perfect.i13
RUN OK · 412 step(s) · peak stack 5
perfect_a = 3 -- a=1,2 collided
bx = 0
by = 1
bz = 4
no_collision = 1
Recommend as a NULL — a search (B40) for a witness + a pinned map (B39). Perfection is a property of the chosen a on a fixed set; finding it is resource, and the resulting map is unique-valued. Different perfect hashers agree on lookups. NULL — zero collisions, by search.