hashing unsuccessful searchesand ( /( )for successful searches the calculations are somewhat involved it is easy to see from the code that insertions and unsuccessful searches require the same number of probes moment' thought suggests thaton averagesuccessful searches should take less time than unsuccessful searches the corresponding formulasif clustering is not problemare fairly easy to derive we will assume very large table and that each probe is independent of the previous probes these assumptions are satisfied by random collision resolution strategy and are reasonable unless is very close to firstwe derive the expected number of probes in an unsuccessful search this is just the expected number of probes until we find an empty cell since the fraction of empty cells is lthe number of cells we expect to probe is /( lthe number of probes for successful search is equal to the number of probes required when the particular element was inserted when an element is insertedit is done as result of an unsuccessful search thuswe can use the cost of an unsuccessful search to compute the average cost of successful search the caveat is that changes from to its current valueso that earlier insertions are cheaper and should bring the average down for instancein the table in figure but the cost of accessing is determined when is inserted at that pointl since was inserted into relatively empty tableaccessing it should be easier than accessing recently inserted elementsuch as we can estimate the average by using an integral to calculate the mean value of the insertion timeobtaining ( dx ln - - these formulas are clearly better than the corresponding formulas for linear probing clustering is not only theoretical problem but actually occurs in real implementations figure compares the performance of linear probing (dashed curveswith what would be expected from more random collision resolution successful searches are indicated by an sand unsuccessful searches and insertions are marked with and irespectively if then the formula above indicates that probes are expected for an insertion in linear probing if then probes are expectedwhich is unreasonable this compares with and probes for the respective load factors if clustering were not problem we see from these formulas that linear probing can be bad idea if the table is expected to be more than half full if howeveronly probes are required on average for insertionand only probes are requiredon averagefor successful search quadratic probing quadratic probing is collision resolution method that eliminates the primary clustering problem of linear probing quadratic probing is what you would expect--the collision function is quadratic the popular choice is (ii figure shows the resulting hash table with this collision function on the same input used in the linear probing example when collides with the next position attempted is one cell away this cell is emptyso is placed there next collides at position then the cell one away is