Java Reference
In-Depth Information
that is not in its home position, a self-organizing list heuristic can be used. For
example, if the linear probing collision resolution policy is used, then whenever a
record is located that is not in its home position, it can be swapped with the record
preceding it in the probe sequence. That other record will now be further from
its home position, but hopefully it will be accessed less frequently. Note that this
approach will not work for the other collision resolution policies presented in this
section, because swapping a pair of records to improve access to one might remove
the other from its probe sequence.
Another approach is to keep access counts for records and periodically rehash
the entire table. The records should be inserted into the hash table in frequency
order, ensuring that records that were frequently accessed during the last series of
requests have the best chance of being near their home positions.
9.4.5 Deletion
When deleting records from a hash table, there are two important considerations.
1. Deleting a record must not hinder later searches. In other words, the search
process must still pass through the newly emptied slot to reach records whose
probe sequence passed through this slot. Thus, the delete process cannot
simply mark the slot as empty, because this will isolate records further down
the probe sequence. For example, in Figure 9.8(a), keys 9877 and 2037 both
hash to slot 7. Key 2037 is placed in slot 8 by the collision resolution policy.
If 9877 is deleted from the table, a search for 2037 must still pass through
Slot 7 as it probes to slot 8.
2. We do not want to make positions in the hash table unusable because of
deletion. The freed slot should be available to a future insertion.
Both of these problems can be resolved by placing a special mark in place
of the deleted record, called a tombstone. The tombstone indicates that a record
once occupied the slot but does so no longer. If a tombstone is encountered when
searching along a probe sequence, the search procedure continues with the search.
When a tombstone is encountered during insertion, that slot can be used to store the
new record. However, to avoid inserting duplicate keys, it will still be necessary for
the search procedure to follow the probe sequence until a truly empty position has
been found, simply to verify that a duplicate is not in the table. However, the new
record would actually be inserted into the slot of the first tombstone encountered.
The use of tombstones allows searches to work correctly and allows reuse of
deleted slots. However, after a series of intermixed insertion and deletion opera-
tions, some slots will contain tombstones. This will tend to lengthen the average
distance from a record's home position to the record itself, beyond where it could
be if the tombstones did not exist. A typical database application will first load a
collection of records into the hash table and then progress to a phase of intermixed
