Given a hash function $h\text{'}(k)=\{0,1,\dots ,m-1\}$. Let $h(k,i)=(h\text{'}(k)+i)\text{mod}m$. There are $O(m)$ probing sequences because there are $m$ different starting points for the probing and any two probes starting from the same point will have the same sequence. While linear probing is simple and takes less time, there is the problem ofprimary clustering.

Let $h(k,i)=(h\text{'}(k)+{c}_{1}i+{c}_{2}{i}^{2})\text{mod}m$. There are $O(m)$ probing sequences because there are $m$ different starting points for the probing and any two probes starting from the same point will have the same sequence. Like linear probing, quadratic probing is simple. However, while it avoids the primary clustering problem, there is a problem ofsecondary clustering.

$h(k,i)=({h}_{1}(k)+i{h}_{2}(k))\text{mod}m$ There are $\Theta ({m}^{2})$ probing sequences because each possible $({h}_{i}(k),{h}_{2}(k)$ pair yields a distinct probe sequence. As we vary the key, the initial probe position and offset may vary independently. Double hashing is an ideal hashing approach. It prevents both primary and secondary clustering problems. However, it is more complicated and requires more running time for hashing.

- Insert element into A[n+1].
- Sift-up from A[n+1]. Call SIFT-UP
$(A,n+1)$.
def sift_up(A, j): i = j while i > 1 and A[i] has priority over A[P(i)]: swap A[i] and A[P(i)] i = P(i)

SIFT-UP has a runtime of $\Theta (\mathrm{lg}n)$. At the swapping step, we do not need to be concerned about the key of the sibling as $P(i)$ has priority over the sibling. Hence, if $i$ has priority over $P(i)$, then $i$ must have priority over its sibling too. - Increment $n$.

File translated from T

On 31 Mar 2006, 18:12.