Double hashing is a technique used for avoiding collisions in hash tables.
A collision occurs when two keys are hashed to the same index in a hash table. Collisions are a problem because every slot in a hash table is supposed to store a single element.
A normal hashing process consists of a hash function taking a key and producing the hash table index for that key.
In double hashing, there are two hash functions. The second hash function is used to provide an offset value in case the first function causes a collision.
The following function is an example of double hashing:
(firstHash(key) + i * secondHash(key)) % tableSize
In the computation above, the value of i
will keep incrementing (the offset will keep increasing) until an empty slot is found.
Double hashing is useful if an application requires a smaller hash table since it effectively finds a free slot.
Although the computational cost may be high, double hashing can find the next free slot faster than the linear probing approach.