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.