Double hashing

Article summary

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 T . 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 h_1 and h_2 , the i th location in the bucket sequence for value x in a hash table of |T| buckets is: h(i,x)=(h_1(x) + i \cdot h_2(x))\bmod|T|. The locations can be conveniently calculated by incrementing the previous hash by h_2(x) , i.e. h(i+1,x)=(h(i,x) + h_2(x))\bmod|T|. Generally, h_1 and h_2 are selected from a set of universal hash functions; h_1 is selected to have a range of \{0,|T|-1\} and h_2 to have a range of \{1,|T|-1\} .…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.