Consider the following problem 11.2-6 from CLRS book:

Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, including the length $L$ of the longest chain. Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time $O(L(1+\frac{1}{\alpha}))$.

I found the solution:

Choose one of the $m$ spots in the hash table at random. Let $n_k$ denote the number of elements stored at $T[k]$. Next pick a number $x$ from $1$ to $L$ uniformly at random. If $x < n_j$ , then return the $x^{th}$ element on the list. Otherwise, repeat this process. Any element in the hash table will be selected with probability $\frac{1}{mL}$, so we return any key with equal probability. Let $X$ be the random variable which counts the number of times we must repeat this process before we stop and p be the probability that we return on a given attempt. Then $E[X] = p(1+\alpha)+(1−p)(1+E[X])$ since we’d expect to take $1+\alpha$ steps to reach an element on the list, and since we know how many elements are on each list, if the element doesn’t exist we’ll know right away. Then we have $E[X] = \alpha+ \frac{1}{p}$. The probability of picking a particular element is $\frac{n}{mL} = \frac{\alpha}{L}$, so we have $E[X] = \alpha + \frac{L}{\alpha} = L(\frac{\alpha}{L} + \frac{1}{\alpha}) = O(L(1 + \frac{1}{\alpha})).$

I have two questions:

  1. Why Any element in the hash table will be selected with probability $\frac{1}{mL}$?

  2. why $E[X] = p(1+\alpha)+(1−p)(1+E[X])$ contains $(1+E[X])$ and then $E[X] = \alpha+ \frac{1}{p}$?


1 Answer 1


"Any element in the hash table will be selected with probability $\frac{1}{mL}$" is slightly confusing. It should be "Any pair of $(s, x)$, where $s$ is a slot in the hash table and $x$ is an index, $1\le x\le L$ will be selected with probability $\frac{1}{mL}$".

There are $m$ choices for $s$ and $L$ choices for $x$. Since these two choices are independent, there are $mL$ equally possible choices in total. That means, each pair will be selected with probability $\frac{1}{mL}$.

"$E[X] = p(1+\alpha)+(1−p)(1+E[X])$" is an equation with a single unknown variable, $E[X]$, with all other variables, $p$, $\alpha$ considered as known. Can you solve this linear equation of one unknown?


Your Answer

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

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