Collision Resolution Probe Sequence

A method for Collision Resolution. In case of hash collision, gets a next available position using a probe function. Probe index i stored for future retrieval.

Probes

Linear Probing

$A[(h(k)+i)\mathrm{mod}m],i=0,1,2,\dots$

Quadratic Probing

$A[(h(k)+i+c_{1}i+c_2{i}^2)\mathrm{mod}m],i=0,1,2,\dots$

Double Hashing

$A[(h(k)+i+h^{\prime }(k))\mathrm{mod}m],i=0,1,2,\dots$ where $h^{\prime }(k)$ is another Hash Function

Complexity

• Worst case insert $\Theta (n)$ time
• Expected Analysis unsuccessful search: $O(\frac{1}{1-\alpha })$ where $\alpha$ is Load Factor
• Expected Analysis successful search: $O(\frac{1}{a}\ln \frac{1}{1-a})$