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 \cdot (1 + 1/\alpha))\).

Start by randomly selecting one of the \(m\) slots in the hash table. Let \(n_k\) indicate the number of elements stored in slot \(T[k]\). Next, pick a random integer \(x\) from between \(1\) and \(L\). If the chosen \(x < n_j\), then we return the \(x^{th}\) element from that list. Otherwise repeat this process. This will ultimately result in selecting some element in the hash table with equal probability across all elements of being selected: \(1/mL\).

Let \(X\) be the random variable which counts the number of times we must repeat this process before we stop and let \(p\) be the probability that we return some value on a given attempt. Then we know that \(E[X] = p(1+ \alpha) + (1 - p)( 1 + E[X])\) since we’d expect to take \(1+\alpha\) attempts 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. So we have \(E[X] = \alpha + \frac{1}{p}\). The probability of picking any particular element of \(T\) is \(\frac{n}{mL} = \frac{\alpha}{L}\). Therefore, we have:

\[\begin{align*} E[X] &= \alpha + \frac{L}{\alpha} \\ &= L(\frac{\alpha}{L} + \frac{1}{\alpha}) \\ &= O(L(1 + \frac{1}{\alpha})) \\ \end{align*}\]

since \(\alpha < L\)