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.
Interestingly, the classical question regarding the average length of an unsuccessful search sequence for standard double hashing in an open address hash table when the table load is a constant @math has been shown to be, up to lower order terms, @math , showing that double hashing has essentially the same performance as random probing (where each ball would have its own random permutation of the bins to examine, in order, until finding an empty bin) when using traditional hash tables @cite_13 @cite_27 @cite_3 . These results appear to have been derived using different techniques than we utilize here; it could be worthwhile to construct a general analysis that applies for both schemes.
@cite_27 @cite_13 @cite_3
2055754268 2079527850 1981326337 2059271645
Abstract In this paper we analyze the performance of double hashing , a well-known hashing algorithm in which we probe the hash table along arithmetic progressions where the initial element and the increment of the progression are chosen randomly and independently depending only on the key K of the search. We prove that double hashing is asymptotically equivalent to uniform probing for load factors α not exceeding a certain constant α 0 = 0.31…. Uniform hashing refers to a technique which exhibits no clustering and is known to be optimal in a certain sense. Our proof method has a different flavor from those previously used in algorithmic analysis. We begin by showing that the tail of the hypergeometric distribution a fixed percentage away from the mean is exponentially small. We use this result to prove that random subsets of the finite ring of integers modulo m of cardinality am have always nearly the expected number of arithmetic progressions of length k , except with exponentially small probability. We then use this theorem to start up a process (called the extension process) of looking at snapshorts of the table as it fills up with double hashing. Between steps of the extension process we can show that the effect of clustering is negligible, and that we therefore never depart too far from the truly random situation. Abstract We present new, improved algorithms for performing deletions and subsequent searches in hash tables. Our method is based on open addressing hashing extended to allow efficient reclamation of unoccupied space due to deletions which enables dynamic shortening of probe sequence lengths. We present an analysis on the number of table probes required to locate an element in the table. Specifically, we present a formula which bounds the average number of cells visited during searches of a data element over its lifetime assuming a system in equilibrium. The formula is a function of the probability that an accessed element is deleted and is exact at the extreme points when the probability is 0 and 1. In the case that the probability is 0 and the load factor is α, the number of cell visits per search access is − ln (1−α) α , and in the case that the probability is 1 the number of cell visits per search access is 1 (1−α) . A fundamental fact in the analysis of randomized algorithms is that when n balls are hashed into n bins independently and uniformly at random, with high probability each bin contains at most O(log n log(log n)) balls. In various applications, however, the assumption that a truly random hash function is available is not always valid, and explicit functions are required. In this paper we study the size of families (or, equivalently, the description length of their functions) that guarantee a maximal load of O(log n log(log n)) with high probability, as well as the evaluation time of their functions. Whereas such functions must be described using Omega(log n) bits, the best upper bound was formerly O(log^2 n log(log n)) bits, which is attained by O(log n log(log n))-wise independent functions. Traditional constructions of the latter offer an evaluation time of O(log n log(log n)), which according to Siegel's lower bound [FOCS '89] can be reduced only at the cost of significantly increasing the description length. We construct two families that guarantee a maximal load of O(log n log(log n)) with high probability. Our constructions are based on two different approaches, and exhibit different trade-offs between the description length and the evaluation time. The first construction shows that O(log n log(log n))-wise independence can in fact be replaced by & quot; gradually increasing independence & quot;, resulting in functions that are described using O(log n log(log n)) bits and evaluated in time O(log n log(log n)). The second construction is based on derandomization techniques for space-bounded computations combined with a tailored construction of a pseudorandom generator, resulting in functions that are described using O(log^(3 2) n) bits and evaluated in time O(sqrt(log n)). The latter can be compared to Siegel's lower bound stating that O(log n log(log n))-wise independent functions that are evaluated in time O(sqrt(log n)) must be described using Omega(2^(sqrt(log n))) bits. We describe a simple randomized construction for generating pairs of hash functions h 1 ,h 2 from a universe U to ranges V = [m] = (0,1,...,m-1) and W = [m] so that for every key set S ⊆ U with n = |S| ≤ m (1 + e) the (random) bipartite (multi)graph with node set V ∪ W and edge set (h 1 (x),h 2 (x))| x ∈ S exhibits a structure that is essentially random. The construction combines d-wise independent classes for d a relatively small constant with the well-known technique of random offsets. While keeping the space needed to store the description of h 1 and h 2 at O(nζ), for ζ < 1 fixed arbitrarily, we obtain a much smaller (constant) evaluation time than previous constructions of this kind, which involved Siegel's high-performance hash classes. The main new technique is the combined analysis of the graph structure and the inner structure of the hash functions, as well as a new way of looking at the cycle structure of random (multi)graphs. The construction may be applied to improve on Pagh and Rodler's "cuckoo hashing" (2001), to obtain a simpler and faster alternative to a recent construction of Ostlin and Pagh (2002 03) for simulating uniform hashing on a key set S, and to the simulation of shared memory on distributed memory machines. We also describe a novel way of implementing (approximate) d-wise independent hashing without using polynomials.