In linear probing there is a special value called AVAILABLE
which is replaced when items are removed.
And when you are inserting a key you look for a empty cell (this just means the cell is null
?) or one that contains AVAILABLE
, what I don't understand is if the empty cell means null
instead of having the special value AVAILABLE
why not just make the cell null
?
What is the advantage over using AVAILABLE
?
In closed hashing (open addressing) a value is looked up as:
Now, suppose you start looking up in bucket 5 and find your key only in bucket 8. If erasing procedure now marked bucket 6 as unoccupied, you'd never get to bucket 8 due to step 3. Therefore, we need a special value that marks bucket as "occupied", yet still available for insertion. This is probably what your source terms as AVAILABLE
, and null
as unoccupied at all.
EDIT: BTW, with linear probing it is possible to (quite) efficiently get away without this special AVAILABLE
value, but that complicates erasing considerably.