# All-Purpose Hashing

@article{Bender2021AllPurposeH, title={All-Purpose Hashing}, author={Michael A. Bender and Alex Conway and Martin Farach-Colton and William Kuszmaul and Guido Tagliavini}, journal={ArXiv}, year={2021}, volume={abs/2109.04548} }

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 many of the fundamental properties that one desires from a hash table are difficult to achieve simultaneously; thus many variants offering different trade-offs have been proposed. This paper introduces Iceberg hashing, a hash table that simultaneously offers the strongest known guarantees on a… Expand

#### One Citation

On the Optimal Time/Space Tradeoff for Hash Tables

- Computer Science
- ArXiv
- 2021

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

#### References

SHOWING 1-10 OF 53 REFERENCES

Cache-Oblivious Hashing

- Computer Science
- Algorithmica
- 2013

This paper shows that linear probing, a classical collision resolution strategy for hash tables, can be easily made cache-oblivious but it only achieves tq=1+Θ(α/b) even if a truly random hash function is used, and demonstrates that the block probing algorithm achieves t q=1-1/2Ω(b), thus matching the cache-aware bound. Expand

Uniform Hashing in Constant Time and Optimal Space

- Computer Science, Mathematics
- SIAM J. Comput.
- 2008

This paper presents an almost ideal solution to this problem: a hash function h: U: Uarrow V that, on any set of $n$ inputs, behaves like a truly random function with high probability, can be evaluated in constant time on a RAM and can be stored in $(1+\epsilon)n\log |V| + O(n+\log \log |U|)$ bits. Expand

Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps

- Computer Science
- ArXiv
- 2011

This work designs hashing-based indexing schemes for dictionaries and multimaps that achieve worst-case optimal performance for lookups and updates, with a small or negligible probability the data structure will require a rehash operation. Expand

Optimality in External Memory Hashing

- Mathematics, Computer Science
- Algorithmica
- 2007

This paper presents an algorithm that, in an asymptotic sense, achieves the best possible I/O and space complexities. Expand

Optimal Hashing in External Memory

- Computer Science, Mathematics
- ICALP
- 2018

A new external memory data structure is presented, the BOT, that matches the performance of the IP hash table, while retaining some of the simplicity of the BOAs. Expand

De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results

- Computer Science, Mathematics
- ICALP
- 2009

The theoretical analysis and experimental results indicate that the scheme is highly efficient, and provides a practical alternative to the only other known approach for constructing dynamic dictionaries with such worst case guarantees, due to Dietzfelbinger and Meyer auf der Heide. Expand

Space Efficient Hash Tables with Worst Case Constant Access Time

- Mathematics, Computer Science
- Theory of Computing Systems
- 2004

This is the first dictionary that has worst case constant access time and expected constant update time, works with (1 + ε)n space, and supports satellite information. Expand

Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation

- Mathematics, Computer Science
- 2010 IEEE 51st Annual Symposium on Foundations of Computer Science
- 2010

This paper construction is a two-level variant of cuckoo hashing, augmented with a ``backyard'' that handles a large fraction of the elements, together with a de-amortized perfect hashing scheme for eliminating the dependency on $\boldsymbol{n}$ memory words, and guarantees constant-time operations in the worst case with high probability. Expand

Analysis of Uniform Hashing

- Computer Science
- JACM
- 1983

Earlier analyses of umform hashing are extended here to multlrecord buckets and three different situations are analysed: initial loadmg assuming uniform access frequencies, frequency loading assuming nonuniformAccess frequencies, and the dynamic behavior when msertions and deletions occur. Expand

Uniform deterministic dictionaries

- Mathematics, Computer Science
- TALG
- 2008

A new analysis of the well-known family of multiplicative hash functions, and improved deterministic algorithms for selecting “good” hash functions are presented, for realization of deterministic dictionaries with fast lookups and reasonably fast updates. Expand