1
$\begingroup$

Theorem: Suppose that a hash function $h$ is chosen from a universal collection of hash functions and is used to hash n keys into a table $ T$ of size $m$, using chaining to resolve collisions. If key $k$ is not in the table, then the expected length $E [n_{h(k)}]$ of the list that key $k$ hashes to is at most $\alpha$. If key $k$ is in the table, then the expected length $E [n_{h(k)}]$ of the list containing key $k$ is at most $1 + \alpha$.

Solution: (Courtesy to Introduction to Algorithms book):

We note that the expectations here are over the choice of the hash function, and do not depend on any assumptions about the distribution of the keys. For each pair $k$ and $l$ of distinct keys, define the indicator random variable $ X_{kl}=I\{h(k) = h(l)\}$. Since by definition, a single pair of keys collides with probability at most 1/m, we have $Pr\{h(k) = h(l)\}\le \frac{1}{m}$, so $E[X_{kl}] \le \frac{1}{m}$.

Next we define, for each key $k$, the random variable $ Y_k$ that equals the number of keys other than $k$ that hash to the same slot as $k$, so that

$$ Y_k=\sum_{\begin{array}{c} i\in T\\ l\ne k\\ \end{array}}{X_{kl}} $$

Thus we have $$ E\left[ Y_k \right] =E\left[ \sum_{\begin{array}{c} i\in T\\ l\ne k\\ \end{array}}{X_{kl}} \right] \le \sum_{\begin{array}{c} i\in T\\ l\ne k\\ \end{array}}{\frac{1}{m}} $$

So, have 2 cases here,

  1. When $k$ is NOT table $T$: If $k \notin T$ , then $n_{h(k)} = Y_k$ and $|{l : l \in T ~and~ l \ne k}| = n$. Thus $ E [n_{h(k)}] = E[Y_k] \le n/m = \alpha$, where $h(k)$ is the hash function that hashes $k$ to a slot. $h(k)$ is a simple division method.
  2. When $k$ in table $T$: If $k \in T$ , then because key $k$ appears in list $T[h_{(k)}]$ and the count $Y_k$ does not include key $k$, we have $n_{h(k)} = Y_k +1$ and $|{l : l ∈ T ~and~ l \ne k}| = n −1$. Thus $E[n_{h(k)}] = E[Y_k]+1 \le (n−1)/m+1 = 1+ \alpha −1/m < 1 + \alpha$.

Problem: I would like to discuss case 1 above please. Why this is the case that we have $ E [n_{h(k)}] = E[Y_k] \le n/m = \alpha$ please?

$\endgroup$
2
  • 1
    $\begingroup$ I think you wrote it wrong. When $k \in T$, $E[n_{h(k)}] = E[Y_k]+1 \leq 1+\alpha$. Please edit your question. $\endgroup$ Aug 31 at 16:39
  • $\begingroup$ @InuyashaYagami. I edited it. Thanks for the reply. $\endgroup$
    – Avra
    Aug 31 at 17:37
1
$\begingroup$

Let $I$ be the set of input keys. We have $|I| = n$.

If $k$ is not in the table, it means that $k \notin I$. If $k$ is in the table it means that $k \in I$.

Let $S_h$ be the slot in the table that key $k$ maps to, if the hash function $h$ is selected. Our aim is to find the expected length of $S_h$. Note that we are taking expectation over the choice of the hash function $h$ picked from the family $\mathcal{H}$, and not the expectation over $I$. The set of input keys $I$ is fixed for this problem.

Consider the case when $k \in I$. In this case, there are $n-1$ other keys in $I$. Whatever be the choice of hash function $h$, key $k$ always maps to $S_{h}$. Therefore, it accounts to a length of $1$ at $S_h$. To find the expected number of keys in $I \setminus \{k\}$ that maps to the same slot as $k$, you simply take the sum of expectation for every key in $I \setminus \{k\}$. It is simply at most $\frac{|I \setminus \{k\} | }{m}$ using linearity of expectation as stated in your question. Therefore, the expected length of $S_h$ is at most $1 + \frac{|I \setminus \{k\} | }{m} = 1 + (n-1)/m \leq 1 + n/m = 1+\alpha$.

Similarly, you can solve for the case when $k \notin I$. There you simply take the sum of expectation for every key in $I \setminus \{k\} = I$. Therefore, the expected length of $S_h$ is at most $\frac{|I| }{m} = n/m = \alpha$.

$\endgroup$
7
  • 1
    $\begingroup$ @Avra I did not understand your comment. You said $n_{h(k)} = Y_k + 1$ when $k \in T$, so what is the issue here? :) $\endgroup$ Aug 31 at 18:12
  • 1
    $\begingroup$ @Avra $1$ should be there because $k$ is in the list $T[h(k)]$. For the remaining keys, we have $Y_k$ term. $\endgroup$ Aug 31 at 18:21
  • 1
    $\begingroup$ @Avra I do not think you are making sense. The argument is not that complicated. When $k \in I$ is equivalent to saying $k \in T$. All keys are mapped at the same time. Initially the table is empty. It is just the case that key $k$ always belongs to the universe $U$ but may or may not belong to the input set $I$. $\endgroup$ Aug 31 at 18:39
  • 1
    $\begingroup$ @Avra Please do not upvote or accept any answer, if you are not convinced with it. We appreciate you clarify the doubts in comments, and even if your doubts are not cleared you should not upvote the answer. $\endgroup$ Aug 31 at 18:42
  • 1
    $\begingroup$ I got it now! Thank you very much. The $1$ comes from $I_{i,i}$, which is the indicator function that the value $k$ hashes to the same slot in case $k \in T$ plus the list already there, $\frac{n}{m}$, so we have $1 + \alpha$. $\endgroup$
    – Avra
    Aug 31 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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