## Closed Hashing

A closed hash table keeps the members of the set in the bucket table rather than using that table to store list headers. Consequently only one element is in any bucket. So, what happens if hash(x) = hash(y) when x and y are different? That is, what happens when we have a collision? We have a "rehash strategy". A "collision" occurs when we have i = hash(x) and the ith element of the table is already occupied (by something other than x). The rehash strategy chooses a sequence of alternative locations, hash-1(x), hash-2(x), hash-3(x), ..., within the table. We try each one of these locations in turn until we encounter an empty (unoccupied) location. If none exists, and we have exhausted the rehash strategy, we assume that the table is full and that we cannot insert x.

A simple rehashing strategy, called "linear rehashing" is as follows:

hash-i(x) = (hash(x) + i) mod B

where there are B buckets in the hash table.

Initially the table is empty, and each bucket holds a special value "empty", ie a value different from any value that we might insert into the table.