---

The delete procedure in Open Addressing

---

• Caveat: deletion in Open Address
  • Caveat in removing an entry:

    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:

  ---

  ---

  ---

  ---

  ---

  ---

• Programming note: How to create the special AVAILABLE marker
  • The special AVAILABLE entry is basically a dummy hash table entry object:

    public class HashMap { public Entry AVAILABLE = new Entry(null, null); .... (other variables andmethod) }

    (The class Entry represents the objects stored in the map)

  ---

  ---

  ---

  ---

  ---

  ---

• Modified lookup procedure with AVAILABLE markers
  • Modified lookup procedure:

    Input: key k Output: the value for key k (if found) or null (not found) start = hashValue(k); i = start; // Start the search at "start" do { Entry e; e = bucket[i]; // 3 possibilities: // (1) null, (2) special AVAILABLE, (3) valid entry if ( e == null ) { return null; // key k is not in hash table } else { if ( e == AVAILABLE ) { i = (i + 1) % capacity; // Continue search } else if ( key.equals( e.key ) ) { return e.value; } else { i = (i + 1) % capacity; // Continue search } } } while ( i != start ); // Stop when search wrapped around return null; // Not found after search wrapped around....

    ---

  • Note:

    We will develop a more integrated search method later. This more integrated search method can be used by: get() put() remove()

  ---

  ---

  ---

  ---

  ---

  ---

• Modified insertion (put(key)) procedure
  • The insert method must be modified to insert in an AVAILABLE slot

    ---

  • Example:

    Original content of the map: After remove(23): put(4,X): But: put(22,X) will result in:

    ---

    ---

  • Very important conclusion:

    We must remember the first AVAILABLE slot while we perform a search operation !

  ---

  ---

  ---

  ---

• Important warning in the probe procedure: Stopping the scan when wrap around !
  • Warning:

    The special EMPTY marker can cause the probe procedure to wrap around even when the hash table is not completely full

    ---

  • Example:

    All empty slots are marked as available:

    ---

  • We look up a non-existing key, e.g.: get(1):

    get(1): We will never encounter an empty (null) slot: infinite loop !!!

    ---

    ---

  • Solutions:

    Remember the start location: Return null (not found) when the scan process re-visits the start location Use a counter: Set counter = N (size of the array) Decrement counter for each entry examined Return null (not found) when the counter == 0