Avg. Num. Probes to Insert in Hash Table w/ Random Collision Res. Strat.

[cocoon]

Hi, I'm reading Data Structures and Algorithm Analysis in Java (Second Edition) and I'm on page 178, if anyone owns the book. I know It's a computer science book and this is a math subforum, but the question is largely a mathematical one involving probability. You just need to understand what a Hash Table is. If you don't feel like reading dense prose, a hash table is basically a large array with a function that maps a key, which is usually a string or an integer, to an address (0 ... arraylength - 1). So it's a modulus function: $$hash(x) = g(x) \bmod T$$. T is the length of the array. You simply add T to hash(x) is hash(x) is negative.

It's particulars aren't important; just know that I'm talking about a hash table that implements a random probing collision resolution strategy, with a hash function like: $$hash(x, i) = ( h(x) + f(i) ) \bmod T, f(0) = 0$$

i represents the i'th probe. If you hash a key and the cell is already filled, then you probe a second time (i = 2), and a third time (i = 3), etc... until you find an empty cell to place x in.

It removes the clustering problem of typical linear (where $$f(i) = A*i + B$$) and, to a lesser extent, quadratic probing (where $$f(i) = A*i^2 + B*i + C$$). In random probing, $$f(i)$$ is random, but is still a function. There is only one value for every i. This removes the clustering problem for small $$\lambda$$, the ratio of filled cells to total cells.

The books takes me through the steps to determine the "expected number of probes in an unsuccessful search," which is basically the average number of probes it takes to reach an empty cell (for an insertion or to indicate that the search was unsuccessful).

The author says "the fraction of empty cells is $$1 - \lambda$$." I follow that. Then he concludes that "the number of cells we expect to probe is $$\frac{1}{1 - \lambda}$$". This smells like a probability problem to me. My question, at last, is why?

 

[hamster143]

Suppose you do N inserts, for some large N.

All N inserts require at least one try.

$N*\lambda$ inserts require a second try (because $N*(1-\lambda)$ succeed right away.)

$N*\lambda^2$ inserts require a third try (because $N*\lambda*(1-\lambda)$ hit an empty cell on the second try).

...

The total number of probes is $$N*(1+\lambda+\lambda^2+...) = \frac{N}{1-\lambda}$$.

 

[cocoon]

Oh, ok that wasn't too hard. What if $$\lambda = 2$$? Oh wait $$\lambda <= 1$$ and if $$\lambda = 1$$, that'd be infinity, which is correct. Man... still don't get it. I still think of $$\frac{1}{1-\lambda}$$ as (number of total cells) / (number of empty cells), but I guess I see it as a geometric series too.

 

[hamster143]

You can see it intuitively like this. If only one in ten cells are empty, then any random process would take on average ten steps to hit upon an empty one.