Balanced Allocations And Double Hashing

Mitzenmacher Michael. Arxiv 2012

[Paper]    
ARXIV Independent

Double hashing has recently found more common usage in schemes that use multiple hash functions. In double hashing, for an item $x$, one generates two hash values $f(x)$ and $g(x)$, and then uses combinations $(f(x)+kg(x))modn$ for $k=0,1,2,\dots$ to generate multiple hash values from the initial two. We first perform an empirical study showing that, surprisingly, the performance difference between double hashing and fully random hashing appears negligible in the standard balanced allocation paradigm, where each item is placed in the least loaded of $d$ choices, as well as several related variants. We then provide theoretical results that explain the behavior of double hashing in this context.

Similar Work

• More Analysis Of Double Hashing For Balanced Allocations
• The Power Of Asymmetry In Binary Hashing
• The Power Of Asymmetry In Binary Hashing
• Cascade Hash Tables A Series Of Multilevel Double Hashing Schemes With O(1) Worst Case Lookup Time