John Kuszmaul

On the Optimal Time/Space Tradeoff for Hash Tables

2021 · arXiv (Cornell University)

For nearly six decades, the central open question in the study of hash tables has been to determine the optimal achievable tradeoff curve between time and space. State-of-the-art hash tables offer the following guarantee: If …