Double hashing has recently found more common usage in schemes that use multiple hash functions. In double hashing, for an item @math , one generates two hash values @math and @math , and then uses combinations @math for @math 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 @math choices, as well as several related variants. We then provide theoretical results that explain the behavior of double hashing in this context.
@cite_33: In this paper, we study the two choice balls and bins process when balls are not allowed to choose any two random bins, but only bins that are connected by an edge in an underlying graph. We show that for @math balls and @math bins, if the graph is almost regular with degree @math , where @math is not too small, the previous bounds on the maximum load continue to hold. Precisely, the maximum load is @math . For general @math -regular graphs, we show that the maximum load is @math and also provide an almost matching lower bound of @math . V "o cking [Voc99] showed that the maximum bin size with @math choice load balancing can be further improved to @math by breaking ties to the left. This requires @math random bin choices. We show that such bounds can be achieved by making only two random accesses and querying @math contiguous bins in each access. By grouping a sequence of @math bins into @math groups, each of @math consecutive bins, if each ball chooses two groups at random and inserts the new ball into the least-loaded bin in the lesser loaded group, then the maximum load is @math with high probability.
Another related work in the balls and bins setting is the paper of Kenthapadi and Panigrahy @cite_33 , who consider a setting where balls are not allowed to choose any two bins, but are forced to choose two bins corresponding to an edge on an underlying random graph. In the same paper, they also show that two random choices that yield @math bins are sufficient for similar @math bounds on maximum loads that one obtains with @math fully random choices, where in their case each random choice gives a contiguous block of @math bins.