Many tasks in computer systems could be abstracted as distributing items into buckets, so
that the allocation of items across buckets is as balanced as possible, and furthermore …

It is shown that for cuckoo hashing with a stash as proposed by Kirsch et al.(Proc. 16th
European Symposium on Algorithms (ESA), pp. 611–622, Springer, Berlin, 2008) families of …

Simple tabulation dates back to Zobrist in 1970 who used it for game playing programs.
Keys are viewed as consisting of c characters from some alphabet Φ. We initialize c tables h …

We introduce a new tabulation-based hashing scheme called “twisted tabulation”. It is
essentially as simple and fast as simple tabulation, but has some powerful distributional …

Hashing is a common technique used in data processing, with a strong impact on the time
and resources spent on computation. Hashing also affects the applicability of theoretical …

A random hash function h is ε-minwise if for any set S,| S|= n, and element x∈ S,
\Prh(x)=\minh(S)=(1±ε)/n. Minwise hash functions with low bias ε have widespread …

We study randomness properties of graphs and hypergraphs generated by simple hash
functions. Several hashing applications can be analyzed by studying the structure of $ d …

Randomization is a central technique in the design and analysis of algorithms and data
structures. This thesis investigates the analysis of two fundamental families of randomized …

Randomization is a central technique in the design and analysis of algorithms and data
structures. This thesis investigates the analysis of two fundamental families of randomized …

Many tasks in computer systems could be abstracted as distributing items into buckets, so
that the allocation of items across buckets is as balanced as possible, and furthermore …