[ : (*string terminator*search(hwelse texts write(wch)texts read(rchendtexts writeln( )texts writeln( )tabulate(hend end crossref analysis of key transformation insertion and retrieval by key transformation has evidently miserable worst-case performance after allit is entirely possible that search argument may be such that the probes hit exactly all occupied locationsmissing consistently the desired (or freeones actuallyconsiderable confidence in the correctness of the laws of probability theory is needed by anyone using the hash technique what we wish to be assured of is that on the average the number of probes is small the following probabilistic argument reveals that it is even very small let us once again assume that all possible keys are equally likely and that the hash function distributes them uniformly over the range of table indices assumethenthat key has to be inserted in table of size which already contains items the probability of hitting free location the first time is then ( - )/ this is also the probability that single comparison only is needed the probability that excatly one second probe is needed is equal to the probability of collision in the first try times the probability of hitting free location the next time in generalwe obtain the probability pi of an insertion requiring exactly probes as ( - )/ ( /nx ( - )/( - ( /nx ( - )/( - ( - )/( - pi ( /nx ( - )/( - ( - )/( - ( - )/( -( - )the expected number of probes required upon insertion of the + st key is therefore ek+ si < < + pi ( - )/ ( /nx ( - )/( - ( + ( /nx ( - )/( - ( - )/( - /( -( - )( + ( -( - )since the number of probes required to insert an item is identical with the number of probes needed to retrieve itthe result can be used to compute the average number eof probes needed to access random key in table let the table size again be denoted by nand let be the number of keys actually in the table then (sk < < ekm ( + (sk < < /( - + ))/ ( + (hn+ hn- + where is the harmonic function can be approximated as hn ln(ngwhere is euler' constant ifmoreoverwe substitute for /( + )we obtain (ln( + ln( - + ))/ ln(( + )/( - + ))/ -ln( - )/ is approximately the quotient of occupied and available locationscalled the load factora implies