Re:Fast Perfect Hashing
by Piezoid on Wednesday February 13, 2019 @03:27PM
(#19156630)
A good blog post about xor-shift-multiply reversible hash functions: https://nullprogram.com/blog/2018/07/31/
The inverse functions are easily found by computing the modular inverses of the odd multiplicative factors.
Real perfect hashing is more about hashing a non contiguous set of elements with no collisions, unlike the set of all integers that fit in n bits.
A different problem is Minimal Perfect Hashing. In addition to being injective, the function should have a minimal image of the input set: the set of keys is mapped to consecutive integers without vacant slots.
The implementations in optimal space are non-practical but some libraries construct such functions with a bit more memory (2-3bits/key), like emphf or BBhash (both on github). The latter use a series of 1-hash bloom filters where keys having collision on one layer are removed to be handled by deeper layers. The overall rank() of the bit where a key ultimately lands gives its hash.
Real perfect hashing is more about hashing a non contiguous set of elements with no collisions, unlike the set of all integers that fit in n bits.
A different problem is Minimal Perfect Hashing. In addition to being injective, the function should have a minimal image of the input set: the set of keys is mapped to consecutive integers without vacant slots.
The implementations in optimal space are non-practical but some libraries construct such functions with a bit more memory (2-3bits/key), like emphf or BBhash (both on github). The latter use a series of 1-hash bloom filters where keys having collision on one layer are removed to be handled by deeper layers. The overall rank() of the bit where a key ultimately lands gives its hash.