sec hashing insert delete figure growth of expected record accesses with the horizontal axis is the value for athe vertical axis is the expected number of accesses to the hash table solid lines show the cost for "randomprobing ( theoretical lower bound on the cost)while dashed lines show the cost for linear probing ( relatively poor collision resolution strategythe two leftmost lines show the cost for insertion (equivalentlyunsuccessful search)the two rightmost lines show the cost for deletion (equivalentlysuccessful searchfull beyond that point performance will degrade rapidly this requires that the implementor have some idea of how many records are likely to be in the table at maximum loadingand select the table size accordingly you might notice that recommendation to never let hash table become more than half full contradicts the disk-based space/time tradeoff principlewhich strives to minimize disk space to increase information density hashing represents an unusual situation in that there is no benefit to be expected from locality of reference in sensethe hashing system implementor does everything possible to eliminate the effects of locality of referencegiven the disk block containing the last record accessedthe chance of the next record access coming to the same disk block is no better than random chance in well-designed hash system this is because good hashing implementation breaks up relationships between search keys instead of improving performance by taking advantage of locality of referencehashing trades increased hash table space for an improved chance that the record will be in its home position thusthe more space available for the hash tablethe more efficient hashing should be