The probability of a given location having x records assigned to it is also the proportion of the locations that have x records assigned to them. So we can predict collisions using the Poisson function. Predicting Collisions for Different Packing Densities Packing density is the ratio of the number of records to the number of places they can be stored. When searching for a record, if it is not found at the home address then start probing. Until we find a location that has never been used.
Tombstones mark locations than have held a record but the record has been deleted.
We must search past tombstones. The probe increment i should be relatively prime to the table size so all locations can be hit during probing. Double Hashing Use a secondary hash function to choose a probe increment. This way different keys have different probe increments. It reduces clustering.