On the optimal time/space tradeoff for hash tables

DOI10.1145/3519935.3519969MaRDI QIDQ6083583zbMATH OpenOpenAlexFDO

Authors Michael A. Bender, Martin Farach-Colton, William Kuszmaul, Mingmou Liu

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.00602, https://hdl.handle.net/1721.1/146419

zbMATH Keywords

balls and binsdata structureshash tablessuccinct

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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 keys/values are Theta(log n) bits each, then it is possible to achieve constant-time insertions/deletions/queries while wasting only O(loglog n) bits of space per key when compared to the information-theoretic optimum. Even prior to this bound being achieved, the target of O(loglog n) wasted bits per key was known to be a natural end goal, and was proven to be optimal for a number of closely related problems (e.g., stable hashing, dynamic retrieval, and dynamically-resized filters). This paper shows that O(loglog n) wasted bits per key is not the end of the line for hashing. In fact, for any k in [log* n], it is possible to achieve O(k)-time insertions/deletions, O(1)-time queries, and O(log^{(k)} n) wasted bits per key (all with high probability in n). This means that, each time we increase insertion/deletion time by an emph{additive constant}, we reduce the wasted bits per key emph{exponentially}. We further show that this tradeoff curve is the best achievable by any of a large class of hash tables, including any hash table designed using the current framework for making constant-time hash tables succinct.

Cited in

(10)

• Optimality in external memory hashing
• Two time-space tradeoffs for element distinctness
• An implicit data structure for searching a multikey table in logarithmic time
• Uniform Hashing in Constant Time and Optimal Space
• scientific article; zbMATH DE number 7051248 (Why is no real title available?)
• Towards an analysis of quadratic probing
• Daisy Bloom filters
• Tiny pointers
• Online sorting and online TSP: Randomized, stochastic, and high-dimensional
• Optimal static fully indexable dictionaries

This page was built for publication: On the optimal time/space tradeoff for hash tables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083583)