THE FOLD / LOOT / THE VAULT / THE PERFECT HASH
THE PERFECT HASH
zero collisions, O(n) space, one probe per lookup
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Perfect hashing (the FKS scheme) stores a fixed set of n keys with zero collisions and O(n) space, so every lookup is a single probe. It uses two levels: a top hash spreads keys into n buckets, and each bucket of b keys gets its own secondary table of size b² with a hash chosen to be collision-free. The sum of the b² sizes is O(n) in expectation, so total space stays linear.
It is how you build a static dictionary — keywords, Unicode tables — with guaranteed constant-time lookup.
LIT verified live: over 200 random key sets every key resolves to a unique slot (lookups exact for members, rejecting non-members) and total space stays O(n) (window.__perfecthash). FIG no framing; zero collisions, exact.
It is how you build a static dictionary — keywords, Unicode tables — with guaranteed constant-time lookup.
LIT verified live: over 200 random key sets every key resolves to a unique slot (lookups exact for members, rejecting non-members) and total space stays O(n) (window.__perfecthash). FIG no framing; zero collisions, exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-vault — a unique lock for every key, no two sharing a slot, one turn to open. Perfect hashing is that vault. AVAN (AI) built the instrument: the two-level construction, the b² collision-free secondaries, the lookup and space checks.
Credit as content: Michael Fredman, János Komlós & Endre Szemerédi (1984). The weave: David names the vault; I spread keys into buckets, size each secondary at b² and re-pick its hash until collision-free, and confirm every key has its own slot in linear space.
Credit as content: Michael Fredman, János Komlós & Endre Szemerédi (1984). The weave: David names the vault; I spread keys into buckets, size each secondary at b² and re-pick its hash until collision-free, and confirm every key has its own slot in linear space.
3 ONE DIMENSION
Two levels: the top hash sends keys to buckets; a bucket holding b keys opens a secondary table of size b², large enough that a random hash almost surely places its keys with no collision.
4 TWO DIMENSIONS · INTERACTIVE
A key set hashed into buckets, each with its collision-free b² secondary. Roll new sets; every key lands in a unique slot, total space stays near linear.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: each key in its own unique slot — one probe, always.
AVAN’s addition (the inverse-companion): for a fixed key set you can guarantee zero collisions in O(n) space. Each bucket of b keys gets a b² secondary table whose hash is chosen collision-free, and Σb² is O(n) in expectation. The inverse of ‘handle collisions at lookup time (chaining, probing)’ is ‘choose the hash functions so there are none.’ Magenta is the collision chains you never walk; green is the unique slot each key lands in. One probe, always — a vault with a unique lock per key.
LIT Genuine FKS perfect hashing (Fredman, Komlos & Szemeredi 1984). Verified live: the two-level scheme (top hash into n buckets, collision-free b^2 secondaries) gives exact membership for all keys and rejects non-members, with total space <= 6n+5, across 200 random key sets (window.__perfecthash.zeroCollisionLookup && .spaceLinear).
FIG No framing: the two-level construction, the collision-free b^2 secondaries, and the lookup + space checks run in-browser and are exact (zero collisions). The AVAN inverse is honest — for a fixed key set the hashes are chosen so there are no collisions, replacing collision-handling with guaranteed unique slots in linear space; magenta is the collision chains never walked, green the unique slot per key. One probe, always.
FIG No framing: the two-level construction, the collision-free b^2 secondaries, and the lookup + space checks run in-browser and are exact (zero collisions). The AVAN inverse is honest — for a fixed key set the hashes are chosen so there are no collisions, replacing collision-handling with guaranteed unique slots in linear space; magenta is the collision chains never walked, green the unique slot per key. One probe, always.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE VAULT · David Lee Wise (ROOT0), with AVAN