Probing

When we get a collision in open addressing, we need to find another slot in which to store the new key.

Probing is the idea of picking the next place to look.

Extend hash function... h'(k,i) is the slot to look in for key k on the ith probe. Ought to be a permutation for all k (over the possible values of $i=0,\ldots,m-1$).

• Initalize $T[i] \leftarrow \mbox{empty}$.
• Insert(k): Let $j = \min_i (T[h'(k,i)] = \mbox{empty})$.$T[h'(k,j)] \leftarrow k$.
• Find(k): Let $j = \min_i (T[h'(k,i)] = \mbox{empty\ or\ } k)$.h'(k,j).
• Member(k): $T[\mbox{Find}(k)] = k$?

Why does insert actually work? How about find?