Cuckoo Hashing
European Symposium on AlgorithmsPublished 28 August 2001
Rasmus Pagh, Flemming Friche Rodler
Citations188
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We present a simple and efficient dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. The space usage is similar to that of binary search trees, i.e., three words per key on average. The practicality of the scheme is backed by extensive experiments and comparisons with known methods, showing it to be quite competitive also in the average case.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
Journal of Computer and System SciencesUniversal classes of hash functions
2,573 Citations1979J.Lawrence Carter, Mark N. Wegman
An input independent average linear time algorithm for storage and retrieval on keys that makes a random choice of hash function from a suitable class of hash functions.
Sorting and Searching
1,536 Citations1973Donald E. Knuth
Journal of the ACMStoring a Sparse Table with <i>0</i> (1) Worst Case Access Time
752 Citations1984Michael L. Fredman, János Komlós +1 more
A data structure for representing a set of n items from a universe of m items, which uses space n+o(n) and accommodates membership queries in constant time and is easy to implement.
SIAM Journal on ComputingBalanced Allocations
743 Citations1999Yossi Azar, Andrei Broder +2 more
It is shown that with high probability, the fullest box contains only ln ln n/ln 2 + O(1) balls---exponentially less than before and a similar gap exists in the infinite process, where at each step one ball, chosen uniformly at random, is deleted, and one ball is added in the manner above.
Using multiple hash functions to improve IP lookups
248 Citations2002Arndt Bröder, Michael Mitzenmacher
This work describes an approach for obtaining good hash tables based on using multiple hashes of each input key (which is an IP address), which proves extremely suitable in instances where the goal is to have one hash bucket fit into a cache line.
Journal of AlgorithmsA Reliable Randomized Algorithm for the Closest-Pair Problem
204 Citations1997Martin Dietzfelbinger, Torben Hagerup +2 more
In the course of solving the duplicate-grouping problem, a new universal class of hash functions of independent interest is described, and it is shown that both of the foregoing problems can be solved by randomized algorithms that useO(n) space and finish inO( n) time with probability tending to 1 asngrows to infinity.
SIAM Journal on ComputingMembership in Constant Time and Almost-Minimum Space
143 Citations1999Andrej Brodnik, J. Ian Munro
A data structure is introduced to represent a subset of elements of $\mathcal{M}$ in a number of bits close to the information-theoretic minimum, $B = \left\lceil \lg {M\choose N} \right\rceil$, and use the structure to answer membership queries in constant time.
Lecture notes in computer scienceA new universal class of hash functions and dynamic hashing in real time
136 Citations2005Martin Dietzfelbinger, Friedhelm Meyer auf der Heide
A new universal class of hash functions which have many desirable features of random functions, but can be (probabilistically) constructed using sublinear time and space, and can be evaluated in constant time is presented.
Lecture notes in computer sciencePolynomial hash functions are reliable
110 Citations1992Martin Dietzfelbinger, J. Gil +2 more
It is proved that cubic hash functions are reliable, and it is shown that higher degree of the polynomial hash functions translates into higher reliability, and a new class of hash functions is introduced, which enables to reduce the universe size in an efficient and simple manner.
On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications
99 Citations1989Andrew F. Siegel
A mechanism is provided for constructing log-n-wise-independent hash functions that can be evaluated in O(1) time, and double hashing using these universal functions has (constant factor) optimal performance in time, for suitably moderate loads.
AlgorithmicaEfficient PRAM simulation on a distributed memory machine
86 Citations1996Richard M. Karp, Michael Luby +1 more
Algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM) using several (two or three) hash functions to distribute the shared memory among the memory modules of the PRAM are presented.
On the cell probe complexity of membership and perfect hashing
55 Citations2001Rasmus Pagh
The first space and bit probe optimal worst case upper bound is given for the membership problem and it is established that for sufficiently sparse sets, non-adaptive perfect hashing needs exponentially more bit probes.
DIMACS series in discrete mathematics and theoretical computer scienceA practical perfect hashing algorithm
7 Citations2002Craig Silverstein
Modiications to the previous techniques are developed that result in a fast, space-eecient algorithm that is comparable to hash algorithms used in several popular dictionary libraries but is more exible and has better theoretical performance.