DoubleHashing

Double hashing is is a technique to resolve hash collisions in a hash table. It is a popular collision-resolution technique in open-addressed hash tables. Double hashing is implemented in many popular libraries.

Like linear probing, it uses one hash value as a starting point 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 decided using a second, independent hash function (hence the name double hashing). Unlike linear probing and quadratic probing, the interval depends on the data, so that even values mapping to the same location have different bucket sequences; this minimizes repeated collisions and the effects of clustering. Wikipedia (opens new window)

R = first prime number <= table.size-1

g(k)= R- (k mod R)

Collided and deleted buckets are marked purple, they need to be included in the collision path