# 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.