   Next:3.6.2 Result 2: InsertionUp:3.6 Analysis of Closed HashingPrevious:3.6 Analysis of Closed Hashing

## 3.6.1 Result 1: Unsuccessful Search The expected number of probes in an unsuccessful search  Proof: In an unsuccessful search, every probe but the last accesses an occupied slot that does not contain the desired key and the last slot probed is empty.

Let the random variable X denote the number of occupied slots probed before hitting an empty slot. X can take values 0, 1,..., n. It is easy to see that the expected number of probes in an unsuccessful search is 1 + E[X].

 pi = P{ }, for i = 0, 1, 2,...

for i > n, pi = 0 since we can find at most n occupied slots.

Thus the expected number of probes
= 1 + ipi                                                 (*)
To evaluate (*), define

qi = P{at least  i  probes access occupied slots}
and use the identity: ipi qi
To compute qi, we proceed as follows:
q1 since the probability that the first probe accesses an occupied slot is n/m.

With uniform hashing, a second probe, if necessary, is to one of the remaining m - 1 unprobed slots, n - 1 of which are occupied. Thus
q2      since we make a second probe only if the first probe accesses an occupied slot.

In general,

 qi =      ...       = since   Thus the expected number of probes in an unsuccessful search

 = 1 + ipi 1 + + + ... =  Intuitive Interpretation of the above:

One probe is always made, with probability approximately a second probe is needed, with probability approximately a third probe is needed, and so on.   Next:3.6.2 Result 2: InsertionUp:3.6 Analysis of Closed HashingPrevious:3.6 Analysis of Closed Hashing
eEL,CSA_Dept,IISc,Bangalore