THE FOLD / CHEAT / THE SHORTCUT / THE MINIMAL PERFECT HASH
THE MINIMAL PERFECT HASH
no slack, and so no way to say not here
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A hash table wastes space so collisions have somewhere to go. If the key set never changes you can do better: find a function that sends n known keys onto 0..n−1 with no collisions and no gaps, then store no keys at all.
LIT verified live. 5,000 keys, 1,250 buckets, each bucket assigned its own seed by search. The result is checked rather than assumed: 0 collisions, 0 out of range, 5,000 distinct slots — a bijection onto exactly 0..4,999. It cost 213,904 seed trials to build, the worst bucket needing seed 5,402, and the finished structure is 3.25 bits per key.
LIT verified live. 5,000 keys, 1,250 buckets, each bucket assigned its own seed by search. The result is checked rather than assumed: 0 collisions, 0 out of range, 5,000 distinct slots — a bijection onto exactly 0..4,999. It cost 213,904 seed trials to build, the worst bucket needing seed 5,402, and the finished structure is 3.25 bits per key.
2 HOW IT WAS WEAVED · AI + HUMAN
The bucket-then-search construction is Botelho, Pagh and Ziviani’s CHD; the theoretical floor for a minimal perfect hash is about 1.44 bits per key.
AVAN (AI) verified the bijection by re-hashing all 5,000 keys through the finished function and counting distinct landing slots, rather than trusting the construction that had just claimed success. A builder that reports success is exactly the thing under test. The asymmetry is the real result: 213,904 trials to build, one hash to query — all the cost is paid once, by whoever compiles the table.
AVAN (AI) verified the bijection by re-hashing all 5,000 keys through the finished function and counting distinct landing slots, rather than trusting the construction that had just claimed success. A builder that reports success is exactly the thing under test. The asymmetry is the real result: 213,904 trials to build, one hash to query — all the cost is paid once, by whoever compiles the table.
3 ONE DIMENSION
Five thousand slots. Every one filled, exactly once.
4 TWO DIMENSIONS · INTERACTIVE
Watch the buckets get placed, largest first.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a function with no free space.
AVAN’s addition (the inverse-companion): the forward reading is that a minimal perfect hash is the most efficient lookup possible. The inverse is that it cannot say no. Query a key that was not in the original set and it will return a slot — a perfectly valid, entirely wrong slot — because there is no spare room in which to represent absence. Read backwards, the gaps in an ordinary hash table were never waste; they were where the answer “not here” lived, and a structure with no slack has no way to be uncertain.
LIT 5,000 keys across 1,250 buckets, each bucket given its own seed by search, then checked rather than assumed: 0 collisions, 0 out of range and 5,000 distinct slots - a bijection onto exactly 0..4,999 - at a cost of 213,904 seed trials to build, a worst bucket needing seed 5,402, and a finished structure of 3.25 bits per key
FIG The bucket-then-search construction is Botelho, Pagh and Ziviani's CHD; the theoretical floor for a minimal perfect hash is about 1.44 bits per key. AVAN verified the bijection by re-hashing all 5,000 keys through the finished function and counting distinct landing slots, rather than trusting the construction that had just claimed success - a builder that reports success is exactly the thing under test. The asymmetry is the real result: 213,904 trials to build, one hash to query.
FIG The bucket-then-search construction is Botelho, Pagh and Ziviani's CHD; the theoretical floor for a minimal perfect hash is about 1.44 bits per key. AVAN verified the bijection by re-hashing all 5,000 keys through the finished function and counting distinct landing slots, rather than trusting the construction that had just claimed success - a builder that reports success is exactly the thing under test. The asymmetry is the real result: 213,904 trials to build, one hash to query.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SHORTCUT · David Lee Wise (ROOT0), with AVAN