Monotone Minimal Perfect Hashing Searching a Sorted Table with O(1) Accesses

Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) AccessesDjamal Belazzougui∗ Paolo Boldi† Rasmus Pagh‡ Sebastiano Vigna†Abstract A minimal perfect hash function maps a set S of n keys into the set { 0, 1, . . . , n − 1 } bijectively. Classical results state that minimal perfect hashing is possible in constant time us- ing a structure occupying space close to the lower bound of log e bits per element. Here we consider the problem of monotone minimal perfect hashing, in which t