ShockHash: Near Optimal-Space Minimal Perfect Hashing Beyond Brute-Force

A perfect hash function (PHF) maps a set of N keys to the first M integers without collisions. If M = N , the hash function is called minimal perfect (MPHF) and is a bijection between the keys and the first N integers [N ]. Minimal perfect hashing has many applications. For example, it can be used to implement static hash tables with guaranteed constant access time [28]. Storing only payload data in the hash table cells, we obtain an updatable retrieval data structure [45], and storing only fingerprints [7, 22], we obtain an approximate membership data structure. The hashes can also be used as small identifiers of the input keys [10], which are more efficient to deal with than large and complex keys. Finally, there is a range of applications in bioinformatics [1, 13–15] and text indexing [3, 5, 59].