3.4 Closed Hashing

• All elements are stored in the hash table itself
• Avoids pointers; only computes the sequence of slots to be examined.
• Collisions are handled by generating a sequence of rehash values. 
h : $$\underbrace{U}_{\mbox{universe of primary keys}}^{}\,$$  x$$\underbrace{\{ 0, 1, 2,... \}}_{\mbox{probe number}}^{}\,$$$$\rightarrow$$  {0, 1, 2,..., m - 1}
• Given a key x, it has a hash value h(x,0) and a set of rehash values

                                        h(x, 1), h(x,2), . . . , h(x, m-1)

• We require that for every key x, the probe sequence

                                        < h(x,0), h(x, 1), h(x,2), . . . , h(x, m-1)>

be a permutation of <0, 1, ..., m-1>.

This ensures that every hash table position is eventually considered as a slot for storing a record with a key value x.

Search (x, T)

• Search will continue until you find the element x (successful search) or an empty slot (unsuccessful search).

Delete (x, T)

• No delete if the search is unsuccessful.
• If the search is successful, then put the label DELETED (different from an empty slot).

Insert (x, T)

• No need to insert if the search is successful.
• If the search is unsuccessful, insert at the first position with a DELETED tag.