hashmap and probing - AVAILABLE and null?

Question

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?

Answer 1

In closed hashing (open addressing) a value is looked up as:

1. Compute key hash and from it determine the "perfect" bucket;
2. If the bucket is occupied and has key equal to the one looked up, return the value;
3. If the bucket is not occupied, abort the lookup with a failure;
4. Go to the next bucket (with linear probing just increment bucket index) and step 2.

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.