2019/12/17 by Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna · 1 citation
Computer Science · Mathematics · #Advanced Data Storage Technologies #Algorithms and Data Compression #Caching and Content Delivery #Perfect hash function #Hash function #Computer science #Hash table #Key (lock) #Data structure #Theoretical computer science #Dynamic perfect hashing #Function (biology) #Algorithm #Discrete mathematics #Double hashing #Mathematics
paper · pdf · doi:10.1137/1.9781611976007.14
openalex publication_date 2019/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
A minimal perfect hash function bijectively maps a key set S out of a universe U into the first |S| natural numbers. Minimal perfect hash functions are used, for example, to map irregularly-shaped keys, such as strings, in a compact space so that metadata can then be simply stored in an array. While it is known that just 1.44 bits per key are necessary to store a minimal perfect hash function, no published technique can go below 2 bits per key in practice. We propose a new technique for storing minimal perfect hash functions with expected linear construction time and expected constant lookup time that makes it possible to build for the first time, for example, structures which need 1.56 bits per key, that is, within 8.3% of the lower bound, in less than 2 ms per key. We show that instances of our construction are able to simultaneously beat the construction time, space usage and lookup time of the state-of-the-art data structure reaching 2 bits per key. Moreover, we provide parameter choices giving structures which are competitive with alternative, larger-size data structures in terms of space and lookup time. The construction of our data structures can be easily parallelized or mapped on distributed computational units (e.g., within the MapReduce framework), and structures larger than the available RAM can be directly built in mass storage.