Double Hashing

Double Hashing: we use a secondary hash function $h^{\prime }(k)$. If $h$ maps some key $k$ to a cell $A[i]$ with $i=h(k)$, that is already occupied, then we iteratively try the buckets:

$$A[(i+f(j))\text{ mod }N]\text{ for }j=1,2,\dots ,N-1$$

Where $f(j)=j\cdot h^{\prime }(k)$.

The secondary hash function $h^{\prime }(k)$ cannot have zero values. The table size $N$ must be prime to allow probing of all of the cells.

A common choice of compression function for the secondary hash function:

$$h^{\prime }(k)=q-k\text{ mod }q$$

Where $q<N$ and $q$ is prime.