3.6.3 Result 3: Successful Search

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

                                                                                $${\frac{1}{\alpha}}$$ ln$${\frac{1}{1 -\alpha}}$$  + $${\frac{1}{\alpha}}$$

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 

$${\frac{1}{1 -\frac{i}{m}}}$$ = $${\frac{m}{m-i}}$$ Averaging over all the n keys in the hash table gives us the expected # of probes in a successful search:

$${\frac{1}{n}} \sum_{i=0}^{n-1} {\frac{m}{m-i}} {\frac{m}{n}} \sum_{i=0}^{n-1} {\frac{1}{m-i}}$$ =

$${\frac{1}{\alpha}} \left(\vphantom{H_m - H_{m-n}}\right. \left.\vphantom{H_m - H_{m-n}}\right)$$ =

where 

H_i = $$\sum_{j=1}^{i}$$$${\frac{1}{j}}$$  is the  i th Harmonic number. Using the well known bounds,  lni$$\leq$$H_i$$\leq$$ ln i + 1, we obtain

$${\frac{1}{\alpha}} \leq {\frac{1}{\alpha}} \left[\vphantom{\ln m + 1 - \ln(m-n)}\right. \left.\vphantom{\ln m + 1 - \ln(m-n)}\right]$$

$${\frac{1}{\alpha}} {\frac{m}{m-n}} {\frac{1}{\alpha}}$$ =

$${\frac{1}{\alpha}} {\frac{1}{1 -\alpha}} {\frac{1}{\alpha}}$$ =