Collision Resolution Probe Sequence

A method for Collision Resolution. Stores wherever an element is placed during collision for future retrieval defined by a probe.

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