- The expected number of probes in a successful search is at most

- assuming that each key in the table is equally likely to be searched
for.

A search for a key *k* follows the same probe sequence as was followed
when the element with key *k* was inserted. Thus, if *k* was
the (*i* + 1)th key inserted into the hash table, the expected number
of probes made in a search for *k* is at most

= | |||

= | H_{m}
- H_{m - n} |

where

(H_{m}
- H_{m - n}) |
lnm
+ 1 - ln(m - n) |
||

= | ln + | ||

= | ln + |