hash data structure | Why deletion is difficult in open addressing scheme ? | Lazy deletion

Why deletion is difficult in open addressing scheme?

Assume hash(x) = hash(y) = hash(z) = i. And assume x was inserted first, then y and then z.
In open addressing: table[i] = x, table[i+1] = y, table[i+2] = z.

Now, assume you want to delete x, and set it back to NULL.

When later you will search for z, you will find that hash(z) = i and table[i] = NULL, and you will return a wrong answer: z is not in the table.

To overcome this, you need to set table[i] with a special marker indicating to the search function to keep looking at index i+1, because there might be element there which its hash is also i.

You cannot remove an entry and leave an "open" slot This can cause not-found errors for some existing entries

Example:

Content of the Map using Linear probing: After remove(13) by real deletion: get(4) results in not-found: Notes: The slot at h(4) is empty. We will conclude that the key 4 is not found in the map

Solving the deleting problem in Open Addressing

• Solution to the deletion problem:
  

  Do not remove an entry physically Instead, store a special EMPTY marker in its place: This special EMPTY marker (named: AVAILABLE) means "does not match"

Example:

After remove(13) by replacing (13,C) with the available marking: When get(4) lands in an AVAIL slot, it must continue with the linear scan:

Modified lookup procedure with AVAILABLE markers

• Modified lookup procedure: