4 papers · 1 filter
Modern Minimal Perfect Hashing: A Survey
Hans-Peter Lehmann, Thomas Mueller, Rasmus Pagh +4
Given a set of keys, a perfect hash function for maps the keys in to the first integers without collisions. It may return an arbitrary result for any key…
Engineering Minimal k-Perfect Hash Functions
Stefan Hermann, Sebastian Kirmayer, Hans-Peter Lehmann +2
Given a set S of n keys, a k-perfect hash function (kPHF) is a data structure that maps the keys to the first m integers, where each output integer can be hit by at most k input ke…
Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer +1
Randomised algorithms often employ methods that can fail and that are retried with independent randomness until they succeed. Randomised data structures therefore often store indic…
SicHash -- Small Irregular Cuckoo Tables for Perfect Hashing
Hans-Peter Lehmann, Peter Sanders, Stefan Walzer
A Perfect Hash Function (PHF) is a hash function that has no collisions on a given input set. PHFs can be used for space efficient storage of data in an array, or for determining a…