9.3.6 Deletion from Hash Tables

Deletion in hash tables using separate chaining is straightforward, since it amounts to the deletion of a record from a list. With open-addressing and coalesced chaining, the deletion of a key is not so straightforward, since a key of the table will be needed to reach another key when it is on that key's probe sequence or list. Deleting it would break this path. One solution to this problem is to mark a deleted key location as "deleted," so that the path is not broken. When a significant fraction of keys has been deleted, the actual usage ratio of the resultant table is low, but search times will still reflect the original higher usage ratio. New insertions, when encountering a "deleted" location, may recapture this wasted storage by occupying such "deleted" locations. However, if "deleted" locations build up, without being recaptured by insertions, search times deteriorate to a linear search for unsuccessful searches and are larger than necessary for successful searches. The only remedy is to rebuild the hash table. Although the algorithm is not given here, this may be done in place, by using only storage allocated to the table in order to carry out the creation of a new table. Hash tables can also be expanded or decreased in size, and recreated. Again, this can be done in place.