BBHash Limasset et al. (2017) uses multiple layers to create a minimal perfect
hashing functions (MPFH), that hashes some input set into
(See also my note on PTHash (Pibiri and Trani 2021).)
Simply said, it maps the
Possible speedup? Link to heading
One bottleneck seems to be that this needs multiple layers of lookups each at different positions in memory. A possible idea:
- Using
, map all items into buckets with elements each. - Hash each of those buckets using the original ‘recursive’ BBhash technique
into a cacheline of
bits.
This way, only two lookups should be needed (apart from the rank operation that follows).
I have no idea how the analysis works out though – maybe the recursive strategy works better on a larger scale and when hashing only so few items there isn’t much benefit to the BBhash approach in the first place.