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].
p_{i} | = | P{}, for i = 0, 1, 2,... |
for i > n, p_{i} = 0 since we can find at most n occupied slots.
Thus the expected number of probes
= 1 + ip_{i}
(*)
To evaluate (*), define
q_{i} = P{at least i probes access occupied
slots}
and use the identity:
ip_{i}
= q_{i}
To compute q_{i}, we proceed as follows:
q_{1} =
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
q_{2} =
since we make a second probe only if the first probe accesses an occupied
slot.
In general,
q_{i} | = | ^{ ... } | |
= since |
Thus the expected number of probes in an unsuccessful search
= | 1 + ip_{i} | ||
1 + + + ^{... } | |||
= |
One probe is always made, with probability approximately a second probe is needed, with probability approximately a third probe is needed, and so on.