Non-Minimal $k$-Perfect Hashing: Tight Lower Bounds and an Application to Fast Static Hash Tables

Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders +1

A minimal perfect hash function (minimal PHF) is a data structure mapping a static set of $n$ keys to $n$ bins without collisions. Two natural generalizations are minimal $k$-PHFs…