Engineering k-perfect Hashing

A minimal k-perfect hash function on a key set S is a function h : S → {0, ..., |S| / k − 1} which maps no more than k keys to the same output. We design and implement four schemes for constructing minimal k-perfect hash functions: RecSplit and Hash and Displace are based on existing schemes for minimal perfect hash functions, and perform especially well for small k. Threshold-based Bumping is an improvement and generalization of an existing scheme for minimal k-perfect hashing which provides especially fast queries on a wide range of values of k. PaCHash is based on an external hashing technique and achieves very fast construction time for a wide range of values of k.