2
$\begingroup$

Given an open-address hash table with $\alpha$ < 1, the expected number of probes in a successful search is at most $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$

I read this in a book and the proof starts by saying

Searching for k follows the same probe sequence as inserting it. If $k$ is the $i+1$th key inserted into the table, then $\frac{1}{1-\frac{i}{m}}$ is the maximum expected number of probes for the search.

However I don't understand how $\frac{1}{1-\frac{i}{m}}$ gives the number of maximum probes needed. Imagine we have $n=5$ and $m=10$ with linear probing. Now if we want to insert the 6th key, based on the fraction above it should take us at most $\frac{1}{1-\frac{5}{10}}=2$ probes. However imagine if slots 0 through 4 were occupied in our table and we start at index 0, then I guess it would take 5 probes to find an empty slot, right?

$\endgroup$
2
  • $\begingroup$ Could you mention the name of the book? $\endgroup$
    – John L.
    Mar 18, 2021 at 5:07
  • $\begingroup$ @JohnL. I'm afraid, I don't think it would be helpful as it's not in English. $\endgroup$
    – Titan
    Mar 18, 2021 at 19:58

2 Answers 2

3
$\begingroup$

You are almost right about "5 probes". It will take, in fact, 6 linear probes to find an empty slot if the probe starts at index 0 of a table with slots 0 through 4 occupied (and slot 5 available). They are 5 failing probes and 1 successful probe at last.

However, you are, apparently, skipping the meaning of the word "expected". That word here means "on average" basically.


While the number of probes can be as big as 4 sometimes, it can be as low as 1 many times as well. So it is not surprising the expected number of probes can be as low as 2.

To be exact and rigorous, the phrase "expected number" as in "the expected number of probes" and "the maximum expected number of probes" has a specific meaning defined in mathematical terms.

The expected value of a discrete random variable $X$ is $E[X]=\sum_xx\cdot \text{pr}\{X=x\}$, where $\text{pr}\{X=x\}$ is the probability of $X$ taking value $x$.

"The expected number of probes" is the shorthand for "the expected value of the discrete random variable that stands for the number of probes." You can understand it simply as "the average number of probes".

I would recommend you read sections in the textbook you are reading that introduce or review related concepts. Or section 3, Discrete random variables in Appendix C of the book CLRS.

$\endgroup$
6
  • $\begingroup$ Thanks for the answer. The exact wording used in my book is "the expected number of probes for searching\inserting $k$ is at most $\frac{1}{1-\frac{i}{m}}$"(where $k$ is the i+1th key). So based on what you say I suppose "expected number of probes" and "expected number of probes at most" are the same thing, right? $\endgroup$
    – Titan
    Mar 17, 2021 at 16:50
  • $\begingroup$ In addition, I tried to calculate the expected value, however I can't seem to get it right. when inserting _i+1_th key, the chance that we get an open slot right away is $\frac{m-i}{m}$, the chance of us getting a filled slot and then an open one is $\frac{i}{m}*\frac{m-i}{m}$. Similarly hitting two filled ones and then an open one would be $\frac{i}{m}^2*\frac{m-i}{m}$. Continuing this and adding all the possibilities and dividing it by the number of possibilities (which I guess is $i+1$) we get $\frac{1}{i+1}\sum_{k=0}^i\frac{i}{m}^k**\frac{m-i}{m}$ which still isn't what the book says. $\endgroup$
    – Titan
    Mar 17, 2021 at 17:10
  • $\begingroup$ One correction, it should be $\frac{1}{i+1}\sum_{k=0}^i(\frac{i}{m})^k*\frac{m-i}{m}$ in the above comment. $\endgroup$
    – Titan
    Mar 17, 2021 at 17:51
  • 1
    $\begingroup$ "the expected number of probes" depends on both the size of all slots and the size of occupied slots, even if, as your textbook probably have done, uniform hashing and equal probability for each key in the table to be searched for are assume. That is, it is not a constant even if the load factor is the same. Hence, the phrase "expected number of probes at most". $\endgroup$
    – John L.
    Mar 17, 2021 at 19:23
  • $\begingroup$ It is non-trivial to calculate the expected number of probes. You can take a look at theorem 11.6 and theorem 11.8 of book CLRS (third edition). $\endgroup$
    – John L.
    Mar 17, 2021 at 19:35
3
$\begingroup$

Most books/notes do not tend to emphasize this point, however when talking about expected values one has to be clear about what exactly is random. Since we're talking about open addressing, we have a hash function $h: U\times [m]\rightarrow [m]$, and we're dealing with a uniformly distributed input. The standard uniform hashing assumption in this context is that every probe sequence is equally likely, i.e. when $X\in U$ is chosen uniformly at random, then $\left(h(X,1),h(X,2),...,h(X,m)\right)$ is uniformly distributed over the set of $m!$ permutations of $[m]$.

Now, if $X$ is chosen uniformly at random, and is inserted to a hash table with load factor $\alpha=n/m$, it makes sense to talk about the expectation of the random variable $T_X$ which denotes the number of probes until finding an empty cell (where again, the source of the randomness is at the choice the element $X\in U$). In Cormen's introduction to algorithms, theorem 11.6, it is proven that under the uniform hashing assumption, $\mathbb{E}[T_X]\le \frac{1}{1-\alpha}$. The word "maximum" is a bit misplaced, this is just an upper bound on the expectation. Your question follows immediately from applying this bound to the $i+1$ element inserted.

$\endgroup$
4
  • 1
    $\begingroup$ Quite interesting. Now that I think about it, inserting a new element in the worst case is similar to doing an unsuccessful search in the worst case. But instead of using the load factor ($\alpha$) we replace it with the number of items inserted so far. $\endgroup$
    – Titan
    Mar 17, 2021 at 19:01
  • 1
    $\begingroup$ This is exactly why said bound is relevant here. $\endgroup$
    – Ariel
    Mar 18, 2021 at 6:41
  • $\begingroup$ So I guess the reason said bound fails in my example in the question (linear probe with initial slots filled), is that linear probing isn't randomly allocating slots to different keys, it's just putting them in order which causes primary clustering, right? $\endgroup$
    – Titan
    Mar 18, 2021 at 20:30
  • $\begingroup$ Well, what you said about linear probing is true, and it's far from satisfying the uniform hashing assumption, but your example does not show that the bound fails. This is a bound on the expectation (which is just a number rather than a random variable). A single outcome cannot testify against a bound on the expectation. $\endgroup$
    – Ariel
    Mar 18, 2021 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.