Next:3.4.1
Rehashing MethodsUp:3.
DictionariesPrevious:3.3.1
Open Hashing
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 :
x
{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, m1)

We require that for every key x, the probe sequence
< h(x,0), h(x, 1), h(x,2), . . . , h(x, m1)>
be a permutation of <0, 1, ..., m1>.
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.
Next:3.4.1
Rehashing MethodsUp:3.
DictionariesPrevious:3.3.1
Open Hashing
eEL,CSA_Dept,IISc,Bangalore