occupied the slot but does so no longer if tombstone is encountered when searching through probe sequencethe search procedure is to continue with the search when tombstone is encountered during insertionthat slot can be used to store the new record howeverto avoid inserting duplicate keysit will still be necessary for the search procedure to follow the probe sequence until truly empty position has been foundsimply to verify that duplicate is not in the table howeverthe 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 howeverafter series of intermixed insertion and deletion operationssome slots will contain tombstones this will tend to lengthen the average distance from record' home position to the record itselfbeyond where it could be if the tombstones did not exist typical database application will first load collection of records into the hash table and then progress to phase of intermixed insertions and deletions after the table is loaded with the initial collection of recordsthe first few deletions will lengthen the average probe sequence distance for records (it will add tombstonesover timethe average distance will reach an equilibrium point because insertions will tend to decrease the average distance by filling in tombstone slots for exampleafter initially loading records into the databasethe average path distance might be ( an average of accesses per search beyond the home position will be requiredafter series of insertions and deletionsthis average distance might increase to due to tombstones this seems like small increasebut it is three times longer on average beyond the home position than before deletions two possible solutions to this problem are do local reorganization upon deletion to try to shorten the average path length for exampleafter deleting keycontinue to follow the probe sequence of that key and swap records further down the probe sequence into the slot of the recently deleted record (being careful not to remove key from its probe sequencethis will not work for all collision resolution policies periodically rehash the table by reinserting all records into new hash table not only will this remove the tombstonesbut it also provides an opportunity to place the most frequently accessed records into their home positions further reading for comparison of the efficiencies for various self-organizing techniquessee bentley and mcgeoch"amortized analysis of self-organizing sequential search heuristics[bm the text compression example of section comes from