SicHash - Small Irregular Cuckoo Tables for Perfect Hashing
Hans‐Peter Lehmann, Peter W. Sanders, Stefan Walzer · Society for Industrial and Applied Mathematics eBooks · 2023
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 compact representative of each object in the set. In this paper, we present the PHF construction algorithm SicHash - Small Irregular Cuckoo Tables for Perfect Hashing. At its core, SicHash uses a known technique: it places objects in a cuckoo hash table and then stores the final hash function choice of each object in a retrieval data structure. We combine the idea with irregular cuckoo hashing, where different objects can have a different number of hash functions. Additionally, we use many small tables that we overload beyond their asymptotic maximum load factor. The most space efficient competitors often use brute force methods to determine the PHFs. SicHash provides a more direct construction algorithm that only rarely needs to re-compute parts. Our implementation improves the state of the art in terms of space usage versus construction time for a wide range of configurations. For some configurations, SicHash is up to 4.3 times faster than the next best competitor. At the same time, it provides very fast queries.