## January 22, 2016:

#
More Analysis of Double Hashing with Balanced Allocations

##
Michael Mitzenmacher

*Abstract:*

With double hashing, for a key $x$, one generates two hash values
$f(x)$ and $g(x)$, and then uses combinations $(f(x) +i g(x)) \bmod n$
for $i=0,1,2,\ldots$ to generate multiple hash values in the range
$[0,n-1]$ from the initial two. For balanced allocations,
keys are hashed into a hash table where each
bucket can hold multiple keys, and each key is placed in the least
loaded of $d$ choices. Here we extend a coupling argument used by
Lueker and
Molodowitch to show that double hashing and ideal uniform hashing are
asymptotically equivalent in the setting of open address hash tables
to the balanced allocation setting. We also discuss the potential for
and bottlenecks
limiting the use this approach for other multiple choice hashing
schemes.

A preliminary
version of this paper was presented at ANALCO 2016.

*About the speaker:*

Michael Mitzenmacher is a Professor of Computer Science in the School
of Engineering and Applied Sciences at Harvard University. He
has authored or co-authored over 150 conference and journal
publications on a topics including algorithms for the
Internet, efficient hash-based data structures, erasure and
error-correcting codes, power laws, and compression. His work on
low-density parity-check codes shared the 2002 IEEE Information Theory
Society Best Paper Award and won the 2009 ACM SIGCOMM Test of Time
Award. His textbook on randomized algorithms and probabilistic
techniques in computer science was published in 2005 by Cambridge
University Press. He currently serves as SIGACT Chair.

Mitzenmacher graduated summa cum laude with a B.A. in
mathematics and computer science from Harvard in 1991. After studying
mathematics for a year in Cambridge, England, on the Churchill
Scholarship,
he obtained his Ph. D. in computer science at U.C. Berkeley in 1996.
He then worked at Digital Systems Research Center until joining the
Harvard faculty in 1999.