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

Area of Science:

• Computer Science
• Algorithms
• Data Structures

Background:

• Minimal perfect hash functions (MPHF) map n keys to n integers collision-free.
• Existing MPHF construction methods often rely on brute-force approaches with high computational costs.
• Optimal space for MPHFs is theoretically bounded by approximately 1.44n bits.

Purpose of the Study:

• Introduce ShockHash, a new method for constructing minimal perfect hash functions.
• Improve upon the efficiency (time and space) of existing MPHF construction algorithms.
• Reduce the number of hash function seeds that need to be tested during construction.

Main Methods:

• ShockHash utilizes two hash functions and a 1-bit retrieval data structure to store a mapping function.
• It models the problem as finding a pseudoforest in an n-edge random graph.
• Employs cuckoo hashing to derive the MPHF from the pseudoforest structure.

Main Results:

• ShockHash reduces the expected number of seeds to test to approximately 1.359^n, a significant improvement over brute-force.
• This leads to an approximate n-bit reduction in seed storage space and a speedup of nearly 2^n.
• Bipartite ShockHash further reduces expected construction time to approximately 1.166^n.
• ShockHash-RS, integrated with RecSplit, achieves construction speeds up to 3 orders of magnitude faster.

Conclusions:

• ShockHash offers a more efficient approach to constructing minimal perfect hash functions.
• The method achieves asymptotically optimal space complexity while drastically reducing construction time.
• ShockHash-RS demonstrates practical efficiency, constructing MPHFs for large datasets rapidly.