Introduction to double hashing

Now that we know how a hash table is implemented using quadratic probing and some of its limitations, we look at another really popular open-addressing collision resolution scheme called double hashing. It is a slight variation of quadratic probing that has all its advantages but reduces the secondary clustering problem by having a different probe sequence for colliding keys.

Like quadratic probing, in a double hashing scheme, the internal array stores the key-value pair. The size of the internal array limits the size of the hash table, and because the array has contiguous memory, it has performance benefits due to the locality of reference.