William Kuszmaul

All-Purpose Hashing

2021 · arXiv (Cornell University)

Despite being one of the oldest data structures in computer science, hash tables continue to be the focus of a great deal of both theoretical and empirical research. A central reason for this is that …

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 …

History-Independent Load Balancing

2026 · Society for Industrial and Applied Mathematics eBooks

We show that there exists a (strongly) history-independent two-choice balls-and-bins algorithm that supports both insertions and deletions on a set of up to \(m\) balls, while guaranteeing a maximum load of \(m/n + O(1)\) with …