To retrieve a value with key K:

  1. compute P = H(K).
  2. if P is EMPTY: there is no value for key K.
  3. if P is OCCUPIED by a value with key K, return it.
  4. else, compute another P and repeat steps 2-4.

Additional stopping criterion: suppose all positions are marked deleted, then the stopping conditions of steps 2-3 will never be true.

If P == H(K), we have come full circle!

Delete Operation: identical except that in step 3, position P should just be marked DELETED.

Step 4 captures 2 possibilities:

A DELETED position cannot be treated like an EMPTY position.