Editing Double hashing (section)

{{Short description|Computer programming technique}}
'''Double hashing''' is a [[computer programming]] technique used in conjunction with [[open addressing]] in [[hash table]]s to resolve [[hash collision]]s, 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 <math>T</math>.

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 [[Primary_clustering|clustering]].

Given two random, uniform, and independent hash functions <math>h_1</math> and <math>h_2</math>, the <math>i</math>th location in the bucket sequence for value <math>k</math> in a hash table of <math>|T|</math> buckets is: <math>h(i,k)=(h_1(k) + i \cdot h_2(k))\bmod|T|.</math>
Generally, <math>h_1</math> and <math>h_2</math> are selected from a set of [[universal hash]] functions; <math>h_1</math> is selected to have a range of <math>\{0,|T|-1\}</math> and <math>h_2</math> to have a range of <math>\{1,|T|-1\}</math>. Double hashing approximates a random distribution; more precisely, pair-wise independent hash functions yield a probability of <math>(n/|T|)^2</math> that any pair of keys will follow the same bucket sequence.