On the Optimal Time/Space Tradeoff for Hash Tables

Michael A. Bender, Martín Farach-Colton, John Kuszmaul +2

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 h…