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

Jul 16, 2026

Upload by Quinn

Minimal perfect hashing maps a static set of n keys into n bins without collisions, and it extends naturally to minimal k-perfect hashing (bins of capacity k) and non-minimal perfect hashing with load factor α<1 by adding spare capacity. Non-minimal k-PHFs are studied here for cache-resident use in accelerating static hash tables via branchless lookups. The work derives tight space lower bounds for all α∈(0,1] and k≥1, showing strong space reductions when α<1 and k≥2. It also develops a tuned PtrHash-based k-PHF with empirical speedups up to 1.5×.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages27

Reading Time1 h 8 min

Introduction

Non-minimal k-perfect hashing

Theory: Tight lower bounds

arXiv :2607 .07257v 1 [ cs .DS] 8 Jul 2026 Non-minimal k-perfect hashing: Tight lower bounds and an application to fast static hash tables Ragnar Groot Koerkamp \# Karlsruhe Institute of Technology, Germany Stefan Hermann \# Karlsruhe Institute of Technology, Germany Peter Sanders \# Karlsruhe Institute of Technology, Germany Stefan Walzer \# Karlsruhe Institute of Technology, Germany ~~ Abstract ~~ 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 where n keys are mapped to n/k bins of capacity k each, and (non-minimal) PHFs with load factor α < 1 where the number of bins is increased by a factor of 1/α, resulting in spare capacity. While there has been a recent surge of interest in perfect hashing generally, non-minimal k-PHFshave not been systematically studied despite a natural use case of speeding up static hash tables: The idea is that a small cache-resident k-PHF maps each key x to a cache-line-sized bin of capacity k where x resides. Ideally, this yields a branchless lookup operation with a single cache miss working at high load factors for positive and negative queries alike. Our main theoretical contribution is to determine tight space lower bounds for k-PHFs for all pairs of α ∈ (0 , 1] and k ≥ 1. It turns out that combining α < 1 and k ≥ 2 drastically reduces the space of k-PHFs, e.g. for (k, α) = (16 , 0.8) the space lower bound is 0.027 bits per key while for (k, α) = (16 , 1.0) and (k, α) = (1 , 0.8) the lower bounds are higher by factors of ≈ 8 and ≈ 32 , respectively. On the practical side, we develop a k-PHF based on PtrHash and tune it for use in static hash tables. Empirically, our implementation produces k-PHFs of size roughly 50% above the lower bound. A static hash set based on this k-PHF is consistently at least as fast as other hash sets for negative and mixed queries. On two of the three tested architectures it achieves up to 1 .5 × speedup for large n ≥ 30M where a 1-PHF does not fit in cache. 2012 ACM Subject Classification Theory of computation → Bloom filters and hashing; Theory of computation → Data structures design and analysis; Information Systems → Point lookups Keywords and phrases Compressed Data Structures, k-Perfect Hashing, Hash Table, Space Lower Bound Related Version Extended version: TODOARXIVLINK [26] Supplementary Material Software: [https://github.com/RagnarGrootKoerkamp/static-hash-sets](https://github.com/RagnarGrootKoerkamp/static-hash-sets) 1 Introduction Given a universe of u keys and an input set of n keys, a k-perfect hash function (PHF) maps the input keys to b bins such that there are at most k keys in each bin. The challenge is to represent the k-PHF as a data structure without storing the input set itself. We refer to α := ~~n~~bk as the load of a k-PHF and call a k-PHF minimal when α = 1 . Table 1, as well as the survey [35], give an overview of construction techniques and lower bounds. In this paper, we initiate the study of the most difficult case of non-minimal k-PHF with k ≥ 2. We derive tight lower bounds on the space of a non-minimal k-PHF for all pairs of α and k (Section 2), extend PtrHash [25] into k-PtrHash, a fast and practical k-PHF with about 50% 2 Non-minimal k-perfect hashing | k = 1 , α = 1 | Bucket Placement [19 , 2 , 47 , 28 , 25 , 4], Recursive Splitting [16 , 38 , 5], Fingerprinting [3, 10 , 40 , 34], Hypergraph / Retrieval [7, 14 , 43 , 6 , 20 , 52 , 36 , 37 , 27] Lower Bound: n · log2 (e) [44] | | --- | --- | | k = 1 , α < 1 | Bucket Placement [19, 2, 47, 28, 25, 4], Hypergraph / Retrieval [11, 36]<br>Lower Bound: n · 􀀀log2 (e) +􀀀 1α − 1􀀁log2 (1 − α)􀀁 [2] | | k ≥ 2 , α = 1 | Bucket Placement & Recursive Splitting & Thresholding [29]<br>Lower Bound: n · 􀀀log2 (e) − log2 (kk /k!)/k 􀀁 [42, 2, 31] | | k ≥ 2 , α < 1 | Bucket Placement [2] and [Section 3]<br>Lower Bound (new): n · 􀀀log2 􀀀 ~

FAQs

What problem does non-minimal k-perfect hashing address in static hash tables?

It provides a compact representation of mappings where each cache-line-sized bin holds at most k keys, enabling fast lookups with low branching and cache-friendly memory access.

How are load factor α and parameter k defined for a k-perfect hash function?

A k-PHF maps n keys into b bins so that each bin contains at most k keys; the load is α := n/b, and the function is minimal when α=1.

What is the paper’s main theoretical contribution?

It determines tight space lower bounds for k-PHFs for every pair α∈(0,1] and k≥1, including cases where combining α<1 with k≥2 substantially reduces required space.

Jul 16, 2026

Upload by Quinn