chap searching depending on the pattern of record accessesit might be possible to reduce the expected cost of access even in the face of collisions recall the / rule of the accesses will come to of the data in other wordssome records are accessed more frequently if two records hash to the same home positionwhich would be better placed in the home positionand which in slot further down the probe sequencethe answer is that the record with higher frequency of access should be placed in the home positionbecause this will reduce the total number of record accesses ideallyrecords along probe sequence will be ordered by their frequency of access one approach to approximating this goal is to modify the order of records along the probe sequence whenever record is accessed if search is made to record that is not in its home positiona self-organizing list heuristic can be used for exampleif the linear probing collision resolution policy is usedthen whenever record is located that is not in its home positionit can be swapped with the record preceding it in the probe sequence that other record will now be further from its home positionbut hopefully it will be accessed less frequently note that this approach will not work for the other collision resolution policies presented in this sectionbecause swapping 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 orderensuring that records that were frequently accessed during the last series of requests have the best chance of being near their home positions deletion when deleting records from hash tablethere are two important considerations deleting record must not hinder later searches in other wordsthe search process must still pass through the newly emptied slot to reach records whose probe sequence passed through this slot thusthe delete process cannot simply mark the slot as emptybecause this will isolate records further down the probe sequence for examplein figure ( )keys and both hash to slot key is placed in slot by the collision resolution policy if is deleted from the tablea search for must still pass through slot as it probes to slot we do not want to make positions in the hash table unusable because of deletion the freed slot should be available to future insertion both of these problems can be resolved by placing special mark in place of the deleted recordcalled tombstone the tombstone indicates that record once