Double hashing
Double hashing is a computer programming technique used in conjunction with open addressing in hash tables to resolve hash collisions, by using a secondary hash of the key as an offset when a collision occurs. Double hashing with open addressing is a classical data structure on a table formula_1. The double hashing technique uses one hash value as an index into the table and then repeatedly steps forward an interval until the desired value is located, an empty location is reached, or the entire table has been searched; but this interval is set by a second, independent hash  function. Unlike the alternative collision-resolution methods of linear probing and quadratic probing, the interval depends on the data, so that values mapping to the same location have different bucket sequences; this minimizes repeated collisions and the effects of clustering. Given two random, uniform, and independent hash functions formula_2 and formula_3, the formula_4th location in the bucket sequence for value formula_5 in a hash table of formula_6 buckets is: formula_7 Generally, formula_2 and formula_3 are selected from a set of universal hash functions; formula_2 is selected to have a range of formula_11 and formula_3 to have a range of formula_13 . Double hashing approximates a random distribution; more precisely, pair-wise independent hash functions yield a probability of formula_14 that any pair of keys will follow the same bucket sequence. Selection of h(k). The secondary hash function formula_15 should have several characteristics: In practice: Analysis. Let formula_20 be the number of elements stored in formula_1, then formula_1's load factor is formula_23. That is, start by randomly, uniformly and independently selecting two universal hash functions formula_2 and formula_3 to build a double hashing table formula_1. All elements are put in formula_1 by double hashing using formula_2 and formula_3. Given a key  formula_5, the formula_31-st hash location is computed by: formula_32 Let formula_1 have fixed load factor formula_34. Bradford and Katehakis showed the expected number of probes for an unsuccessful search in formula_1, still using these initially chosen hash functions, is formula_36 regardless of the distribution of the inputs. Pair-wise independence of the hash functions suffices. Like all other forms of open addressing, double hashing becomes linear as the hash table approaches maximum capacity. The usual heuristic is to limit the table loading to 75% of capacity. Eventually, rehashing to a larger size will be necessary, as with all other  open addressing schemes. Variants. Peter Dillinger's PhD thesis points out that double hashing produces unwanted equivalent hash functions when the hash functions are treated as a set, as in Bloom filters: If formula_37 and formula_38, then formula_39 and the sets of hashes formula_40 are identical. This makes a collision twice as likely as the hoped-for formula_41. There are additionally a significant number of mostly-overlapping hash sets; if formula_42 and formula_43, then formula_44, and comparing additional hash values (expanding the range of formula_4) is of no help. Triple hashing. Adding a quadratic term formula_46 formula_47 (a triangular number ) or even formula_48 (triple hashing) to the hash function improves the hash function somewhat but does not fix this problem; if: then Enhanced double hashing. Adding a cubic term formula_53 or formula_54 (a tetrahedral number), does solve the problem, a technique known as enhanced double hashing. This can be computed efficiently by forward differencing: struct key; /// Opaque /// Use other data types when needed. (Must be unsigned for guaranteed wrapping.) extern unsigned int h1(struct key const *), h2(struct key const *); /// Calculate k hash values from two underlying hash functions /// h1() and h2() using enhanced double hashing. On return, /// hashes[i] = h1(x) +  i*h2(x) + (i*i*i - i)/6. /// Takes advantage of automatic wrapping (modular reduction) /// of unsigned types in C. void ext_dbl_hash(struct key const *x, unsigned int hashes, unsigned int n) In addition to rectifying the collision problem, enhanced double hashing also removes double-hashing's numerical restrictions on formula_55's properties, allowing a hash function similar in property to (but still independent of) formula_2 to be used.